\section{Introduction}

Let $\overline G$ be a group acting properly and cocompactly on
a $2$-dimensional CAT(0) complex $X$. In \cite{BB} Ballmann and Brin proved \emph{Rank Rigidity} for $\overline G$, saying that if each edge of $X$ is in at least two 2-cells, then either $\overline G$ has an element of rank~$1$, or $X$ is a Euclidean building. Two other strong\-ly related questions on CAT(0) groups have remained open even in the same $2$-dimensional setting. The first one is the \emph{Tits Alternative} stating that subgroups of $\overline G$ are either virtually abelian or contain free subgroups. The second one
is even more basic (as it might be seen as a first step for proving the Tits Alternative):

\begin{center}
	\textbf{Question.} \emph{Does $\overline G$ have an {infinite torsion subgroup} $G$?}
\end{center}
(See e.g.\ \cite{Swe}, \cite[Quest 2.11]{BestvinaProblemOLD}, \cite[Quest 8.2]{BridsonProblem}, \cite[Prob 24]{KapovichProblems}, \cite[\S~IV.5]{Cap} for appearances of the problem.)
Surprisingly, prior to our work the answer was not known even in the otherwise very well understood case of lattices
in isometry groups of Euclidean buildings of type $\widetilde A_2$. Swenson \cite{Swe} proved that for $1$-ended $\overline G$, negative answer to the Question is equivalent to no cut points in the CAT(0) boundary of $X$. Moreover, he answered the Question in the negative for $G=\overline G$. (Both independent of the dimension of the CAT(0) space.)
Furthermore, if $G$ is finitely presented, then it also acts properly and cocompactly on a $2$-dimensional CAT(0) complex \cite[\S 1.1]{HMP}, so the answer stays negative.

\medskip

Generalising the Question by discarding $\overline G$ one can ask if there is an infinite torsion group $G$ acting nontrivially on a $2$-dimensional CAT(0) complex. It is natural to ask that for $G$ finitely generated, since infinitely generated torsion groups can act properly on trees (see \cite[II.7.11]{BH}).
We answer that, as well as the Question, in the negative in Corollaries~\ref{cor:proper} and~\ref{cor:subgroup}.
This is one consequence of a more general result, our main Theorem~\ref{thm:torsion}, concerning
more general actions of groups on $2$-dimensional CAT(0) complexes. Under mild assumptions, it states that locally elliptic actions are trivial, confirming \cite[Conj~1.2]{Mar} in the case of $2$-dimensional buildings.
Note that finite-dimensionality assumption is important, since there are infinite torsion Grigorchuk groups that are amenable \cite{Gri}, and hence they act properly on a Hilbert space, which is CAT(0).

\medskip

We now pass to discussing the general setup for Theorem~\ref{thm:torsion}.
Let $X$ be a 2-dimensional simplicial complex, which we will call a \emph{triangle complex}.
We assume additionally that $X$ has a \emph{piecewise smooth Riemannian metric}, which is a family of smooth Riemannian metrics $\sigma_T, \sigma_e$ on the triangles and edges such that $\sigma_T$ restricts to $\sigma_e$ for each $e\subset T$. Riemannian metrics $\sigma_T, \sigma_e$ induce metrics $d_T,d_e$ on triangles and edges. We then equip $X$ with the \emph{quotient pseudometric}~$d$ (see \cite[I.5.19]{BH}).

We assume that the triangles containing each vertex $v$ of $X$ belong to only finitely many isometry classes of $\sigma_T$.
We also assume that $(X,d)$ is a complete length space. This holds for example:
\begin{itemize}
\item
if there are only finitely many isometry classes of $\sigma_T$ (see \cite[I.7.13]{BH} for $X$ an \emph{$M_\kappa$ complex}, meaning that each $\sigma_T$ has Gaussian curvature $\kappa$ and geodesic sides; the general case follows using a bilipschitz map from $X$ to an $M_\kappa$ complex), or
\item
if $X$ is the space $\bf X$ for the tame automorphism group (\cite[Prop 5.4, Lem 5.6]{LP}). Some cells of $\bf X$ are polygons instead of triangles, but we can easily transform $\bf X$ into a triangle complex by subdividing.
\end{itemize}

We consider an action of a group $G$ on $X$ by \emph{automorphisms}, i.e.\ simplicial automorphisms that preserve the metrics $\sigma_T$. Consequently, they are isometries of $(X,d)$. Such an action is \emph{nontrivial} if $G$ does not have a global fixed point.

See Section~\ref{sec:spaces} for the discussion of the CAT(0) property and the definition of having \emph{rational angles}. For example, if the triangles of $X$ have all angles commensurable with $\pi$, then $X$ has rational angles.

\begin{thm}
\label{thm:torsion}
Let $(X,d)$ be a $\mathrm{CAT}(0)$ triangle complex.
Let $G$ be a finitely generated group acting
nontrivially on $X$.
Assume that
\begin{enumerate}[(i)]
\item each element of $G$ fixing a point of $X$ has finite order, or
\item $X$ is locally finite, or
\item $X$ has rational angles.
\end{enumerate}
Then $G$ has an
element with no fixed point in $X$.
\end{thm}

While we believe that Theorem~\ref{thm:torsion} holds also without (i),(ii), and (iii), this does not seem to be trackable with our methods. For example, one of them would require in particular the existence of periodic trajectories in triangular biliards, which is a major open problem (see e.g.\ \cite{M}).

Applying Theorem~\ref{thm:torsion} and then \cite[Thm~1.1]{CL} to the family of fixed point sets for all finitely generated subgroups $G$ of $\overline G$ below gives:

\begin{cor}
\label{cor:bdry}
Let $(X,d)$ be a $\mathrm{CAT}(0)$ triangle complex.
Let $\overline G$ be a group acting on $X$ such that each element of $\overline G$ fixes a point of $X$.
Assume that (i),(ii), or (iii) holds. Then the action of $\overline G$ on $X\cup \partial X$ is trivial.
\end{cor}

Theorem~\ref{thm:torsion} under condition (i) can be rephrased in the following way.

\begin{cor}
\label{cor:proper}
Let $(X,d)$ be a $\mathrm{CAT}(0)$ triangle complex. Let $G$ be a finitely generated group acting nontrivially on $X$. Then $G$ has an element of infinite order.
\end{cor}

The following corollary answers the Question. Note that the finite generation assumption is removed here.

\begin{cor}
\label{cor:subgroup}
Let $(X,d)$ be a $\mathrm{CAT}(0)$ triangle complex.
Let $\overline G$ be a group acting properly and cocompactly on $X$. Then any subgroup $G$ of $\overline G$ is finite or has an element of infinite order.
\end{cor}

\begin{proof}
Suppose that all elements of $G$ have finite order. By \cite[II.2.8(2)]{BH}, there is a finite bound on the size of all finite subgroups of $\overline G$. Let then $H$ be a maximal finite subgroup of $G$. We will prove that $H=G$. Otherwise, there is $g\in G-H$. Then $\langle H, g\rangle$ is finitely generated and thus by Corollary~\ref{cor:proper} it is finite. This contradicts the maximality of $H$.
\end{proof}

In view of the Question and Corollary~\ref{cor:proper} we state the following conjecture, which we could not
find elsewhere in the literature. Observe that, as in the proof of Corollary~\ref{cor:subgroup}, the conjecture implies negative answer to the Question in the setting of finite-dimensional CAT(0) complexes.

\begin{conj}
	\label{conj:torsion}
	Every finitely generated group acting nontrivially on a finite-dimen\-sio\-nal $\mathrm{CAT}(0)$ complex contains an element
	of infinite order.
\end{conj}

In the proof of Theorem~\ref{thm:torsion} under conditions (i) or (ii) we will need the following graph-theoretic result of independent interest.

Below, by a \emph{graph} we mean a (possibly infinite) metric graph with finitely many possible edge lengths.
A closed edge-path embedded in a graph $\Lambda$ is a \emph{cycle of $\Lambda$}. An embedded edge-path $P$ in $\Lambda$ is a \emph{segment of $\Lambda$} if the endpoints of $P$ have degree at least three in $\Lambda$, but every internal vertex of $P$ has degree two.

\begin{thm}\label{thm:graph+}
Let $\Gamma$ be a graph, and let $\Gamma'$ be its finite subgraph with all vertices of degree at least two.
Assume that
\begin{itemize}
\item the girth of $\Gamma$ is $\geq 2\pi$, and
\item each $x,y$ in $\Gamma'$ are at distance $\leq \pi$ in $\Gamma$.
\end{itemize}
Then all cycles and segments of $\Gamma'$ have length commensurable with~$\pi$.
\end{thm}

\begin{cor}
\label{thm:graph}
Let $\Gamma$ be a graph, and let $\gamma\colon C\to \Gamma$ be a closed edge-path immersed in $\Gamma$. Assume that
\begin{itemize}
\item the girth of $\Gamma$ is $\geq 2\pi$, and
\item each $x,y$ in $\gamma(C)$ are at distance $\leq \pi$ in $\Gamma$.
\end{itemize}
Then the length of $\gamma$ is commensurable with $\pi$.
\end{cor}

Interestingly, Theorem~\ref{thm:graph+} will follow from a generalisation of a classical theorem of Dehn~\cite{Dehn} stating that a rectangle tiled by finitely many squares has commensurable side lengths.

\medskip

\noindent \textbf{Idea of proof of Theorem~\ref{thm:torsion}.} Suppose by contradiction that for each $f\in G$ the set $\mathrm{Fix}(f)$ of fixed points of $f$ is nonempty. We wish to prove inductively that for any finite set of elements $f_1,\ldots, f_n\in G$ (ultimately becoming the generating set) the intersection $\mathrm{Fix}(f_1)\cap \cdots \cap \mathrm{Fix}(f_n)$ is nonempty. Here we illustrate the induction step from $n=2$ to $n=3$. Suppose that $\mathrm{Fix}(f_1),\mathrm{Fix}(f_2),\mathrm{Fix}(f_3)$ pairwise intersect but their triple intersection is empty. We then find a simplicial disc $\Delta$ with decomposition of its boundary into three paths $\partial \Delta=P\cup Q\cup R$ together with a simplicial map $\psi$ from $\Delta$ to $X$ that sends $P,Q,R$ into $\mathrm{Fix}(f),\mathrm{Fix}(g),\mathrm{Fix}(h),$ respectively. We suppose that~$\Delta$ has minimal possible area. We then look for a periodic billiard trajectory $\omega$ in~$\Delta$ outside its $0$-skeleton $\Sigma$. Then $\psi(\omega)$ develops to an axis in $X$ of a loxodromic element of $G$ and leads to contradiction. However, sometimes we are only able to find a periodic geodesic going through a vertex $v$ in~$\Sigma$. Then we need to study in more detail the relation between the link of $v$ in $\Delta$ and the link of $\psi(v)$ in~$X$.

\medskip

\noindent \textbf{Organisation.} In Section~\ref{sec:spaces} we discuss CAT(0) spaces and rational angles property. In Section~\ref{sec:2} we outline the proof of Theorem~\ref{thm:torsion} for $2$-generated $G$. In Sections~\ref{sec:surface} and~\ref{sec:loxodromic} we fill in the details of that outline. In Section~\ref{sec:3} we complete the proof of Theorem~\ref{thm:torsion}. The proof of Theorem~\ref{thm:graph+} is postponed till Section~\ref{sec:graph}.

\medskip

\noindent \textbf{Acknowledgements.} We thank Werner Ballmann, Martin Bridson, Pierre-Emma\-nuel Caprace,
Jingyin Huang, St\'ephane Lamy, Timoth\'ee Marquis, and Eric Swenson
for introducing us to the state of affairs in the subject, for their comments and encouragement.
This paper was written while D.O.\ was visiting McGill University.
We would like to thank the Department of Mathematics and Statistics of McGill University
for its hospitality during that stay.

\section{Rational angles}
\label{sec:spaces}

Let $v$ be a vertex of the triangle complex $X$. By $\mathrm{lk}_v$ we denote the \emph{space of directions} at $v$, which is the set of geodesic rays issuing from $v$, where we identify rays at Alexandrov angle $0$ (see \cite[II.3.18]{BH}). Note that $\mathrm{lk}_v$ has an obvious structure of a graph. We treat $\mathrm{lk}_v$ as a length metric space $(\mathrm{lk}_v,d_v)$ where the length of each edge is the angle in an appropriate triangle of $X$. Since we assumed that triangles containing $v$ belong to only finitely many isometry classes of $\sigma_T$, there are only finite many possible edge lengths in a given $\mathrm{lk}_v$.

For a piecewise smooth simplicial map $\phi \colon X\to X'$ we keep the notation $\phi$ for all the maps $\mathrm{lk}_v\to \mathrm{lk}_{\phi(v)}$ induced by $\phi$.

For $X$ to be CAT(0) it is necessary that
\begin{itemize}
\item the girth of each $\mathrm{lk}_v$ is $\geq 2\pi$,
\item the Gaussian curvature of $\sigma_T$ at any interior point of $T$ is $\leq 0$,
\item the sum of geodesic curvatures in any two distinct triangles at any interior point of a common edge is $\leq 0$, and
\item $X$ is simply connected.
\end{itemize}

While it seems that these conditions are also sufficient (one would need to couple the ideas from \cite{Babu} and \cite{BH}), only under the following conditions this has been verified in the literature.

\begin{itemize}
\item $X$ is locally finite \cite[Thm 7.1]{Babu}, or
\item $X$ is an $M_\kappa$ complex with $\kappa\leq 0$ and there are only finitely many isometry classes of $\sigma_T$ \cite[II.5.2 and~II.5.4]{BH}, or
\item $X$ is the space $\bf{X}$ for the tame automorphism group \cite[Thm~A]{LP}.
\end{itemize}

\begin{defin}
\label{def:rational}
We say that $X$ has \emph{rational angles} with respect to an action of a group $G$, if for each vertex $v$ of $X$ we have a discrete set $\Lambda\subset \mathrm{lk}_v$, invariant under the stabiliser $G_v$, and with the following property.
Consider an immersed edge-path $\gamma$ in $\mathrm{lk}_v$ that is disjoint from $\Lambda$ except possibly at the endpoints. We call $\gamma$ \emph{flat} if
\begin{enumerate}[(i)]
\item
each edge of $\gamma$ corresponds to a triangle $T$ of $X$ with Gaussian curvature $0$ at any interior point, and
\item
the sum of geodesic curvatures in any two such consecutive triangles at any interior point of the common edge is $0$.
\end{enumerate}
We require that each flat $\gamma$ is
\begin{itemize}
\item
finite, and
\item
if it has endpoints in $\Lambda$, then its length is commensurable with $\pi$.
\end{itemize}
\end{defin}

For example, if all triangles of $X$ with $\sigma_T$ of constant Gaussian curvature $0$ have only angles commensurable with $\pi$, then $X$ has rational angles, since we can take for $\Lambda$ all the vertices of $\mathrm{lk}_v$. This includes all $\widetilde{A}_2, \widetilde{C}_2$, and $\widetilde{G}_2$ buildings.

\begin{lem}
\label{lem:Lamy}
The space $\bf X$  for the tame automorphism group constructed in \cite{LP} has rational angles.
\end{lem}
\begin{proof}
The proof is aimed at readers familiar with \cite{LP}. Let $\rho_+\colon \bf{X}\to \nabla_+$ be the folding from \cite[Cor 2.4]{LP}.
Let $P\subset \mathrm{lk}_{\rho_+(v)}$ be the directions determined by the \emph{principal lines}: through $\rho_+(v)$ and $[1,0,0],[0,1,0],$ or $[0,0,1]$. Let $\Lambda=\rho_+^{-1}(P)$. These are the only possible directions of edges from $\rho_+(v)$ that are geodesics, since all edges lie in admissible lines (see \cite[\S 4.A]{LP}) and the only admissible lines that are geodesics are principal (equality case in \cite[Lem~5.1]{LP}). Thus by Definition~\ref{def:rational}(ii), the image of $\gamma$ under $\rho_+$ in $\mathrm{lk}_{\rho_+(v)}$ might not be immersed only at $P$. Since consecutive points of~$P$ are at distance~$\frac{\pi}{3}$ (see \cite[Rm~5.2]{LP}), the length of~$\gamma$ is bounded by $\frac{\pi}{3}$ with equality if and only if $\gamma$ has endpoints in $\Lambda$.
\end{proof}

\section{Pairs of generators}
\label{sec:2}

In this section we prove Theorem~\ref{thm:torsion} for 2-generated $G$.
For an automorphism $f$ of $X$, $\mathrm{Fix}(f)\subset X$ denotes the set of fixed points of $f$.

\begin{prop}
\label{prop:pairs}
Let $f,g$ be automorphisms of a $\mathrm{CAT}(0)$ triangle complex $X$ satisfying condition (i),(ii), or (iii) of Theorem~\ref{thm:torsion}. Suppose that both $\mathrm{Fix}(f), \mathrm{Fix}(g)$ are nonempty. Then $\mathrm{Fix}(f)$ intersects $\mathrm{Fix}(g)$, or
$\langle f,g\rangle$ contains an element with no fixed point in $X$.
\end{prop}

In the proof we will need the following terminology. We say that an automorphism $f$ of $X$ acts \emph{without inversions}, if whenever $f$ stabilises a triangle $T$ or an edge $e$, then it fixes $T$ or $e$ pointwise.

\begin{defin}
Let $S$ be a sphere with three marked points $p,q,r$. Let $f_S,g_S$ and $h_S=g^{-1}_S\circ f_S$ be the elements of the fundamental group of $S- \{p,q,r\}$ corresponding to the punctures $p,q,r,$ respectively. Let $\widetilde S$ be the branched cover of $S$ over $p,q,r$ corresponding to $\pi_1(S- \{p,q,r\})$. For a pair $(f,g)$ of automorphisms of $X$, an \emph{equivariant triangulation} of $\widetilde {S}$ \emph{w.r.t.\ $(f,g)$} is the following object.

First of all, it consists of a structure on $S$ of a \emph{$\Delta$-complex} (as defined in \cite[\S 2.1]{H}), which is a generalisation of a simplicial complex allowing the simplices not to be embedded, and allowing several simplices with the same boundary. We require that $p,q,$ and $r$ are vertices. This induces a $\Delta$-complex structure on $\widetilde S$.

Secondly, an equivariant triangulation consists of a simplicial map $\phi$ from $\widetilde S$ to $X$ that is equivariant with respect to the homomorphism defined by $f_S\to f, g_S\to g$, which we will denote by $\phi_*$.
\end{defin}

A simplicial map is \emph{nondegenerate} if it does not collapse an edge to a vertex. A nondegenerate simplicial map is a \emph{near-immersion} if it is a local embedding at edge midpoints.

We begin with listing a lemma and a proposition that piece together to a proof of Proposition~\ref{prop:pairs}.

\begin{lem}
\label{lem:min surface}
Let $f,g,h=g^{-1}\circ f$ be automorphisms of a simply connected triangle complex~$X$ acting without inversions. Suppose that all $\mathrm{Fix}(f),\mathrm{Fix}(g),\mathrm{Fix}(h)$ are nonempty and pairwise disjoint. Then there exists an equivariant triangulation of $\widetilde S$ w.r.t.\ $(f,g)$ with $\phi$ a near-immersion.
\end{lem}

Lemma~\ref{lem:min surface} will be proved in Section~\ref{sec:surface}.

If $X$ is a CAT(0) space, an element $g\in G$ is \emph{loxodromic} if there is a geodesic $\omega\subset X$ (called an \emph{axis}) such that $g$ preserves $\omega$ and acts on it as a translation. A loxodromic element does not have a fixed point in $X$.

\begin{prop}
	\label{prop:loxodromic}
	Let $X$ be a $\mathrm{CAT(0)}$ triangle complex satisfying condition (i),(ii), or (iii) of Theorem~\ref{thm:torsion}.
	Suppose that for some automorphisms $f,g$ of $X$ we have an equivariant triangulation of $\widetilde S$ w.r.t.\ $(f,g)$ with $\phi$ a near-immersion. Then $\langle f,g\rangle$ contains a loxodromic element.
\end{prop}

Proposition~\ref{prop:loxodromic} will be proved in Section~\ref{sec:loxodromic}.

\begin{proof}[Proof of Proposition~\ref{prop:pairs}]
After possibly subdividing the triangles of $X$, we can assume that $f,g$ act without inversions. Let $h=g^{-1}\circ f$.
If $h$ does not have a fixed point in $X$, then the proof is complete, so we can assume that $\mathrm{Fix}(h)$ is nonempty.
Similarly, we can suppose that $\mathrm{Fix}(f)$ is disjoint from $\mathrm{Fix}(g)$.
Then $\mathrm{Fix}(h)$ is disjoint from both $\mathrm{Fix}(f)$ and $\mathrm{Fix}(g)$. By Lemma~\ref{lem:min surface}, there exists an equivariant triangulation of $\widetilde S$ w.r.t.\ $(f,g)$ with $\phi$ a near-immersion. By Proposition~\ref{prop:loxodromic}, $\langle f,g\rangle$ contains a loxodromic element.
\end{proof}

\section{Existence of nearly immersed triangulations}
\label{sec:surface}

The \emph{area} of a finite $2$-dimensional $\Delta$-complex is the number of its triangles. We say that an equivariant triangulation of $\widetilde S$ w.r.t.\ $(f,g)$ has \emph{minimal area} if the corresponding $\Delta$-complex structure on $S$ has minimal area among all equivariant triangulations of $\widetilde S$ w.r.t.\ $(f,g)$.

\begin{proof}[Proof of Lemma~\ref{lem:min surface}]

\smallskip
\noindent \textbf{Step 1.} \emph{There exists an equivariant triangulation.}
\smallskip

Since $f,g$ act without inversions, $\mathrm{Fix}(f),\mathrm{Fix}(g),\mathrm{Fix}(h)$ are subcomplexes. Consider any vertices $a\in \mathrm{Fix}(f) ,b\in \mathrm{Fix}(g),c\in \mathrm{Fix}(h),$ and any nontrivial edge-paths $\alpha$ (resp.\ $\beta$) from $c$ to $a$ (resp.\ $b$) in $X$. Let $\gamma$ be the closed edge path $\alpha^{-1}\beta g(\beta^{-1})f(\alpha)$, which passes through $a,c,b,g(c)=f(c)$. By the relative simplicial approximation \cite{Z}, there is a disc $D$ with a structure of a simplicial complex and a simplicial map $\psi\colon D \to X$ that restricts to $\gamma$ on $\partial D$.

Gluing the parts of $\partial D$ mapping to $\alpha$ and $f(\alpha)$, and the parts mapping to $\beta$ and $g(\beta)$, and labelling the points mapping to $a,b,c$ by $p,q,r,$ equips $S$ with a structure of a $\Delta$-complex. This defines an equivariant triangulation of $\widetilde S$, since there exists an obvious equivariant map $\phi$ extending $\psi$ viewed as a map from the fundamental domain $D\subset \widetilde{S}$ for the action of $\langle f_S, g_S\rangle$.

\smallskip
\noindent \textbf{Step 2.} \emph{A minimal area equivariant triangulation has nondegenerate $\phi$.}
\smallskip

Suppose that there is an edge $\widetilde e\subset \widetilde S$ with $\phi(\widetilde e)$ a vertex.
We will find an equivariant triangulation with strictly smaller area, which contradicts minimality.
Let~$e$ be the projection of $\widetilde e$ to $S$.
Let $u,v$ be the endpoints of $e$.

\textbf{Case $u=v$.} In that case, assume for the moment that $u$ is distinct from $p,q,r$. Since $u=v$, we have that $e$ is an embedded closed path.
Let $B\subset S$ be the open disc bounded by $e$ containing at most one of $p,q,r$. Let $T$ be the triangle of $S$ adjacent to $e$ outside~$B$, and let $t,t'$ be the edges of $T$ distinct from $e$. Note that $t\neq t'$ since otherwise $T$ would form the entire outside of $B$, which would contradict the assumption that there are at least two of $p,q,r$ outside $B$.

If $B$ does not contain a puncture, then we can remove $T\cup B$ from $S$ and glue along $t$ and $t'$ (independent of whether all the vertices of $T$ coincide or not). This does not change the homeomorphism type of $S$ and decreases its area. If $B$ contains a puncture, say $p$, then we perform the same operation and additionally relabel $u$ by $p$. Note that it is clear how to modify $\phi$ on modified $\widetilde{S}$.

Going back to the possibility that $u$ is one of $p,q,r,$ say, $q$, we still perform the same operation, except that now $B$ will not contain $p$ (or $r$), since otherwise $\mathrm{Fix}(f)$ would intersect $\mathrm{Fix}(g)$.
Consequently we still have $t\neq t'$ and we can proceed as before.

\textbf{Case $u\neq v$.} Let $T,T'$ be the triangles of $S$ adjacent to $e$, and let $y,y'$ be the vertices opposite to $e$ in $T,T'$. If $T=T'$, then any lift $\widetilde T$ of $T$ to $\widetilde S$ is collapsed to a single vertex of $X$. Let $\widetilde {e}'$ be the edge of $\widetilde T$ that does not project to $e$. Then the projection $e'$ of $\widetilde {e}'$ has coinciding endpoints, which brings us back to Case $u=v$.

Thus we can assume that $T\neq T'$. We want to remove $T\cup T'$ from the triangulation and glue the resulting square in the boundary so that $u$ is identified with $v$. This amounts to collapsing segments of a foliation in $T\cup T'$, with leaves parallel to $e$. This does not change the homeomorphism type of~$S$, as long as the leaves do not combine to circles.

Indeed, a single leaf (or a pair of leaves in a common triangle) cannot close up to a circle since the edges $yu$ and $yv$ are distinct, because $S$ does not contain a M\"obius band, and analogously the edges $uy',vy'$ are distinct. Furthermore, a pair of leaves in distinct triangles does not form a circle since otherwise $S$ would have only two triangles and consequently both $u,v$ would be in $\{p,q,r\}$, forcing some $\mathrm{Fix}(f),\mathrm{Fix}(g),\mathrm{Fix}(h)$ to intersect.

Removing $T\cup T'$ decreases the area of $S$. Note that as a result of this operation, vertices $p,q,r$ cannot become identified, since this again would mean that some $\mathrm{Fix}(f),\mathrm{Fix}(g),\mathrm{Fix}(h)$ intersect.

\smallskip
\noindent \textbf{Step 3.} \emph{A minimal area equivariant triangulation has $\phi$ a near immersion.}
\smallskip

By Step~2, $\phi$ is nondegenerate. Suppose that there is an edge $\widetilde e\subset \widetilde S$ with midpoint $\widetilde m$ where $\phi$ is not a local embedding. Again, we will reach a contradiction by showing that
the area can be decreased. Let $e$ and $m$ be the projections of $\widetilde e$ and $\widetilde m$ to $S$. Let $T,T'\subset S$ be the triangles containing $e$ and let $y,y'$ be the vertices opposite to~$e$ in $T,T'$.

To start with, note that $T\neq T'$. Indeed, if $T=T'$, then let $\tau$ be the segment in~$T$ starting and ending at the distinct copies of $m$ in $\partial T$. Let $\widetilde\tau, w\widetilde{\tau}$ for $w\in \langle f_S, g_S\rangle$ be the two lifts of $\tau$ to $\widetilde S$ at $\widetilde m$, and let $\widetilde T$ be the lift of $T$ containing $\widetilde{\tau}$. Then $\phi(\widetilde T)$ is stabilised by $\phi_*(w)$, but not fixed pointwise, which is a contradiction.

\textbf{Case $y\neq y'$.} In that case removing $T\cup T'$ from the triangulation and gluing the resulting square in the boundary so that $y$ is identified with $y'$ is equivalent to the following. We collapse intervals of a foliation in $T\cup T'$ with leaves parallel to the union $\delta$ of segments $ym\subset T,my'\subset T'$. Similarly as in Step~2 these leaves do not form circles, and thus collapsing them does not change the homeomorphism type of~$S$, while it decreases its area. Again as a result of this operation, vertices $p,q,r$ cannot become identified, since this would mean that some $\mathrm{Fix}(f),\mathrm{Fix}(g),\mathrm{Fix}(h)$ intersect.

\textbf{Case $y=y'$.} In that case, assume for the moment that $y$ is distinct from $p,q,r$. Then $\delta$, defined as in Case $y\neq y'$, is an embedded closed path. Let $B\subset S$ be the open disc bounded by $\delta$ containing at most one of $p,q,r$. Let $t,t'$ be the edges of $T,T'$ outside $B$.
Note that $t\neq t'$ since otherwise halves of $T$ and $T'$ would form the entire outside of $B$, which would contradict the assumption that there are at least two of $p,q,r$ outside $B$. We can thus remove $T\cup T'\cup B$ and glue along $t,t'$ to decrease the area of $S$. If $B$ contained one of $p,q,r$, say, $p$, then we relabel $y$ by~$p$. If $y=y'$ is one of $p,q,r,$ say, $q$, then we define $B$ in the same way and we note that $B$ does not contain $p$ (or $r$) since otherwise $\mathrm{Fix}(f)$ would intersect $\mathrm{Fix}(g)$. Consequently we still have $t\neq t'$ and we can proceed as before.
\end{proof}

\section{Constructing axes}
\label{sec:loxodromic}

To prove Proposition~\ref{prop:loxodromic} we will need the following famous theorem of Masur.

\begin{defin}
A \emph{translation surface} $S$ is a surface obtained from identifying sides of finitely many polygons in $\mathbb{R}^2$ by translations.
This equips $S$ with a Riemannian metric of Gauss curvature $0$ outside a finite set $\Sigma$.
\end{defin}

\begin{rem}
\label{rem:hol}
Assume that a sphere $S$ has a piecewise smooth Riemannian metric that is smooth of Gauss curvature $0$ outside a finite set $\Sigma$.
Suppose that for each $v\in \Sigma$ the length of $\mathrm{lk}_{v}$ is commensurable with $\pi$. Since $\pi_1(S-\Sigma)$ is generated by the peripheral curves, the image of the holonomy map $\pi_1(S-\Sigma)\to O(2)$ is finite. Consequently, its kernel corresponds to a finite branched cover of $S$ over~$\Sigma$ that has trivial holonomy and is thus a translation surface. Similarly, each finite branched cover of $S$ over $\Sigma$ has a further cover that is a translation surface.
\end{rem}

\begin{thm}[{\cite[Thm~2]{M}}]
\label{thm:masur}
Let $S$ be a translation surface. Then there is a closed local geodesic in $S-\Sigma$.
\end{thm}

We will also need the following results of Ballmann and Brin.

\begin{lem}[{\cite[Lem 7.1]{BB}}]
\label{lem:BB1}
Let $S$ be a compact triangle complex that is locally $\mathrm{CAT}(0)$ and in which each edge belongs to at least two triangles.
Suppose that there is
\begin{itemize}
\item
a point in the interior of a triangle with negative Gauss curvature, or
\item
a point in the interior of an edge with negative sum of geodesic curvatures in a pair of incident triangles.
\end{itemize}
Then there is a closed local geodesic in $S$ that is disjoint from the vertices.
\end{lem}

\begin{lem}[{compare \cite[Lem 7.3]{BB}}]
\label{lem:BB2}
Let $S$ be a compact triangle complex that is locally $\mathrm{CAT}(0)$ and in which each edge belongs to at least two triangles. Assume that there is a vertex $v$ and points $\xi,\eta$ in $\mathrm{lk}_v$ with $d_v(\xi,\eta)=\pi$. Then for any $\varepsilon>0$ there is a closed path $\beta_1\beta_2\beta_3$ in $S$ such that
\begin{itemize}
\item paths $\beta_i$ are local geodesics,
\item the angles at the breakpoints between $\beta_2$ and $\beta_1,\beta_3$ are $>\pi-\varepsilon$,
\item $\beta_i$ do not pass through vertices except that $\beta_1$ starts at $v$ and $\beta_3$ ends at $v$, and
\item the starting direction $\xi'$ of $\beta_1$ and ending direction $\eta'$ of $\beta_3$ satisfy $d_v(\xi,\xi')<\frac{\varepsilon}{2}, d_v(\eta,\eta')<\frac{\varepsilon}{2}$.
\end{itemize}
\end{lem}

\begin{proof} We refer to the proof of \cite[Lem 7.3]{BB}, where the authors work in the universal cover of $S$ (which they call $X$). Once they construct their geodesic $\sigma$, define $\omega_2$ as the subpath of $\sigma$ between $P$ and $\varphi (P)$, and $\omega_1, \omega_3$ as the geodesics joining the endpoints of $\omega_2$ to $v,\varphi v$ in $P, \varphi(P)$. The projection of $\omega_1\omega_2\omega_3$ to $S$ is the required path $\beta_1\beta_2\beta_3$.
\end{proof}

\begin{proof}[Proof of Proposition~\ref{prop:loxodromic}.]
We equip $\widetilde S$ and $S$ with the piecewise smooth Riemannian metric pulled back from $X$ via $\phi$.
Since $\phi$ is a near-immersion, $S-\{p,q,r\}$ is locally CAT(0). After replacing $S$ with a finite branched cover over $\{p,q,r\}$, we can assume that $S$ (which is no longer a sphere) is locally CAT(0) at every point. Let $\Sigma$ be the vertex set of $S$.

Assume first that a point in the interior of a triangle of $S$ has negative Gauss curvature, or a point in the interior of an edge of $S$ has negative sum of its two geodesic curvatures. Then by Lemma~\ref{lem:BB1}, there is a closed local geodesic $\omega$ in $S-\Sigma$.
Let $\widetilde{\omega}$ be an elevation of $\omega$ to $\widetilde{S}$, which is an axis for some $w\in \langle f_S, g_S\rangle$. Since $\phi$ is a near-immersion, $\phi(\widetilde{\omega})$ is a local, hence global, geodesic in $X$. Thus $\phi_*(w)\in \langle f,g\rangle$ is loxodromic.

It remains to consider the case where $S-\Sigma$ is smooth with Gauss curvature~$0$. Suppose first that for each $v\in \Sigma$, the length of $\mathrm{lk}_{v}$ is commensurable with $\pi$. By Remark~\ref{rem:hol}, there is a finite branched cover $S'$ of $S$ over $\Sigma$
that is a translation surface. By Theorem~\ref{thm:masur}, $S'$ has a closed local geodesic $\omega'$
outside the vertex set. Projecting $\omega'$ to $\omega$ in $S$ we can now find a loxodromic element in $\langle f,g\rangle$ as before.

Assume now that for some $v\in\Sigma$ the length of $\mathrm{lk}_{v}$ is not commensurable with~$\pi$.
Let $\widetilde v$ be a lift of $v$ to $\widetilde S$. If $\mathrm{lk}_{\widetilde{v}}$ is a circle, consider the closed immersed edge-path $\gamma\colon\mathrm{lk}_{\widetilde{v}})\to\mathrm{lk}_{\phi(\widetilde{v})}$ induced by $\phi$. This path fails the conclusion of Corollary~\ref{thm:graph}. Thus there are points $\widetilde{\xi},\widetilde{\eta}\in \mathrm{lk}_{\widetilde{v}}$ such that their images in $\mathrm{lk}_{\phi(\widetilde{v})}$ are at distance $>\pi+\delta$ for some $\delta>0$.

If $\mathrm{lk}_{\widetilde{v}}$ is a line, we construct $\widetilde{\xi},\widetilde{\eta}$ in the following way.
Assume without loss of generality that $\widetilde{v}$ is fixed by $f_S$. First, we claim that $X$ does not have rational angles with respect to the action of $G$. Otherwise, let $\Lambda\subset \mathrm{lk}_{\phi(\widetilde{v})}$ be the discrete set from Definition~\ref{def:rational}. Then the complementary components in $\mathrm{lk}_{\widetilde{v}}$ of $\phi^{-1}(\Lambda)$ are finite, and of length commensurable with $\pi$. Moreover, since $f$ preserves $\Lambda$, we have that $f_S$ preserves $\phi^{-1}(\Lambda)$. This contradicts the assumption that the length of $\mathrm{lk}_{v}$ is not commensurable with $\pi$, justifying the claim.

According to our hypotheses this means that either $X$ is locally finite, or each element of $G$ fixing a point of $X$ has finite order.
In both cases there is a directed edge $e$ in $\mathrm{lk}_{\widetilde{v}}$ and $k\geq 1$ such that $\phi(e)=\phi(f_S^ke)$. Thus the path in $\mathrm{lk}_{\widetilde{v}}$ from the endpoint of $e$ to the endpoint of $f^k_Se$ maps under $\phi$ to a closed edge-path failing the conclusion of Corollary~\ref{thm:graph}, and we obtain $\widetilde{\xi},\widetilde{\eta}$ as before.

Let $\xi,\eta$ be the projections of $\widetilde{\xi},\widetilde{\eta}$ to $\mathrm{lk}_{v}$. Orbits of an irrational rotation on a circle are dense. Thus in $\mathrm{lk}_{v}$ we can find $\xi_1=\xi, \xi_2, \ldots, \xi_{2n}$ with $d_{v}(\xi_i,\xi_{i+1})=\pi$ and $d_{v}(\xi_{2n},\eta)<\frac{\delta}{2}$. Inspired by \cite[Lem 7.4]{BB}, we construct the following path $\widetilde{\omega}=\omega_1\cdots \omega_{6n}$ in $\widetilde{S}$.
To start with, we put $\varepsilon=\frac{\delta}{12n}$ and apply Lemma~\ref{lem:BB2} to $\xi_1,\xi_2$. We define $\omega_1\omega_2\omega_3$ to be the lift of $\beta_1\beta_2\beta_3$ starting in the direction at distance $<\frac{\varepsilon}{2}$ from $\widetilde{\xi}$. Let $\widetilde v_2$ be the endpoint of $\omega_3$ and let $\widetilde{\xi}_2$ in $\mathrm{lk}_{\widetilde {v}_2}$ be the lift of $\xi_2$ at distance $<\frac{\varepsilon}{2}$ from the ending direction of $\omega_3$. Since $d_{v'}(\xi_2,\xi_{3})=\pi$, there is a lift $\widetilde{\xi}_3$ of $\xi_3$ in $\mathrm{lk}_{\widetilde v_2}$ with $d_{\widetilde v_2}(\widetilde{\xi}_2,\widetilde{\xi}_{3})=\pi$. Apply now Lemma~\ref{lem:BB2} to $\xi_3,\xi_4$ and define $\omega_4\omega_5\omega_6$ to be the lift of the resulting $\beta_1\beta_2\beta_3$ starting in the direction at distance $<\frac{\varepsilon}{2}$ from $\widetilde{\xi}_3$ etc. The endpoint of $\omega_{6n}$ has the form $w\widetilde {v}$ for some $w\in \langle f_S,g_S\rangle$, and since $d_{v}(\xi_{2n},\eta)\leq\frac{\delta}{2}$, we can choose $w$ so that the ending direction of $\omega_{6n}$ is at distance $<\frac{\varepsilon}{2}+\frac{\delta}{2}$ from $w\widetilde \eta$.

Let $x,y=\phi_*(w)x\in X$ be the endpoints of $\phi(\widetilde{\omega})$, and denote by $\xi'$ and $\eta'$ the starting and ending directions of $\phi(\widetilde{\omega})$. Then $d_x(\phi(\widetilde{\xi}),\xi')< \frac{\varepsilon}{2}$ and $d_y(\phi(w\widetilde{\eta}), \eta')< \frac{\varepsilon}{2}+\frac{\delta}{2}$. Let $\alpha$ be the geodesic from $x$ to $y$ in $X$, and denote by $\xi''$ and $\eta''$ the starting and ending directions of $\alpha$. Note that the angles at all the breakpoints of $\phi(\widetilde{\omega})$ are $> \pi-\varepsilon$.
By \cite[Lem~2.5]{BB} we have $d_x(\xi',\xi'')+d_y(\eta',\eta'')< (6n-1)\varepsilon$. We thus have:
\begin{align*}
d_y(\phi_*(w)\xi'',\eta'')&\geq  d_y(\phi_*(w)\xi',\eta')-d_y(\phi_*(w)\xi'',\phi_*(w)\xi')-d_y(\eta',\eta'')\\
&>d_y(\phi_*(w)\xi',\eta')-(6n-1)\varepsilon\\
&\geq  d_y\big(\phi(w\widetilde {\xi}),\phi(w\widetilde {\eta})\big)-d_y\big(\phi_*(w)\xi',\phi(w\widetilde {\xi})\big) -d_y\big(\phi(w\widetilde {\eta}),\eta'\big)-(6n-1)\varepsilon\\
&>
(\pi+\delta)-\frac{\varepsilon}{2}-\Big(\frac{\varepsilon}{2}+\frac{\delta}{2}\Big)-(6n-1)\varepsilon=\pi.
\end{align*}
Consequently the concatenation of $\phi^k_*(w)\alpha$, for $k\in \mathbb{Z}$ is a local (hence global) geodesic, and thus $\phi_*(w)$  is loxodromic.
\end{proof}

\section{Triples of generators}
\label{sec:3}

In this Section we complete the proof of Theorem~\ref{thm:torsion}.

\begin{prop}
	\label{prop:triples}
	Let $f,g,h$ be automorphisms of a $\mathrm{CAT}(0)$ triangle complex $X$ satisfying condition (i),(ii), or (iii) of Theorem~\ref{thm:torsion}. Suppose that all $\mathrm{Fix}(f)\cap \mathrm{Fix}(g), \mathrm{Fix}(f)\cap\mathrm{Fix}(h),$ and $\mathrm{Fix}(g)\cap\mathrm{Fix}(h)$ are nonempty. Then $\mathrm{Fix}(f)\cap\mathrm{Fix}(g)\cap\mathrm{Fix}(h)$ is nonempty or
	$\langle f,g,h\rangle$ contains a loxodromic element.
\end{prop}

In the proof we will need the following notion. Let $\Delta$ be a disc with decomposition of its boundary into three paths $\partial \Delta=P\cup Q\cup R$. An \emph{admissible triangulation} of $\Delta$ w.r.t.\ $(f,g,h)$ is a structure on $\Delta$ of a  $\Delta$-complex, with $P\cap Q, Q\cap R, P\cap R$ among the vertices, together with a simplicial map $\psi$ from $\Delta$ to $X$ that sends $P,Q,R$ into $\mathrm{Fix}(f),\mathrm{Fix}(g),\mathrm{Fix}(h),$ respectively.

\begin{lem}
\label{lem:min surface2}
Let $f,g,h$ be automorphisms of a $\mathrm{CAT}(0)$ triangle complex~$X$ acting without inversions. Suppose that $\mathrm{Fix}(f),\mathrm{Fix}(g),\mathrm{Fix}(h)$ pairwise intersect but their triple intersection is empty. Then there exists an admissible triangulation of $\Delta$ with $\psi$ a near-immersion.
\end{lem}

\begin{proof}
Since $f,g,h$ act without inversions, their fixed point sets are subcomplexes. Thus an admissible triangulation of $\Delta$ exists by the relative simplicial approximation \cite{Z}. Suppose now that $\Delta$ has minimal area among admissible triangulations w.r.t.\ $(f,g,h)$.
We first prove that $\psi$ is nondegenerate. Indeed, suppose that there is an edge $e\subset \Delta$ with $\psi(e)$ a vertex, and let $u,v$ be the endpoints of $e$. If $e$ lies in $\partial \Delta$, then let $T$ be the triangle containing $e$. We then remove $e$ and $T$ from $\Delta$ and we identify the two remaining sides of $T$. This decreases the area of $\Delta$, which contradicts minimality. Suppose then that $e$ is contained in two triangles $T$ and $T'$. If $u=v$, then we modify $\Delta$ as in the proof of Lemma~\ref{lem:min surface}. If $u\neq v$ and $T=T'$ we land back in Case $u=v$. Otherwise, we wish to remove $T\cup T'$, or more precisely to collapse intervals of the foliation in $T\cup T'$ parallel to $e$. Unless $e$ has both endpoints on $\partial \Delta$, this does not change the homeomorphism type of~$\Delta$. If both $u$ and $v$ are on the path $P$ (resp.\ $Q,R$), then together with $T$ and $T'$ we remove the entire disc bounded by $e$ and a subpath of $P$ (resp.\ $Q,R$), and we identify the two remaining edges of $T$ or $T'$. If the endpoints of $e$ lie on two distinct paths, say $P$ and $Q$, then we do the same using a subpath of $P\cup Q$ ($P\cap Q$ is replaced here by $u$ identified with $v$).

Finally, we prove that $\psi$ is a near-immersion. Suppose that there is an edge $e\subset \Delta$ with midpoint $m$ where $\psi$ is not a local embedding. Let $T,T'\subset \Delta$ be the triangles containing $e$ and let $y,y'$ be the vertices opposite to $e$ in $T,T'$. As in the proof of Lemma~\ref{lem:min surface}, we have $T\neq T'$. Consider the path $\delta$ as in the proof of Lemma~\ref{lem:min surface}. If $y=y'$, then we can modify $\Delta$ as in the proof of Lemma~\ref{lem:min surface}. If $y\neq y'$, then we collapse intervals of appropriate foliation in $T\cup T'$. Unless $\delta$ has both endpoints on $\partial \Delta$, this does not change the homeomorphism type of~$\Delta$.
If both endpoints of $\delta$ are on the path $P$ (resp.\ $Q,R$), then together with $T$ and $T'$ we remove the entire disc bounded by $\delta$ and a subpath of $P$ (resp.\ $Q,R$), and we identify the two remaining edges of $T,T'$. If the endpoints of $\delta$ lie on two distinct paths, say $P$ and $Q$, then we do the same using a subpath of $P\cup Q$ ($P\cap Q$ is replaced here by $v$ identified with $v'$). After finitely many such operations we will arrive at a near-immersion.
\end{proof}

\begin{proof}[Proof of Proposition~\ref{prop:triples}]
After possibly subdividing the triangles of $X$, we can assume that $f,g,h$ act without inversions. Suppose that $\mathrm{Fix}(f)\cap\mathrm{Fix}(g)\cap\mathrm{Fix}(h)=\varnothing$. Then by Lemma~\ref{lem:min surface2}, there is an admissible triangulation of $\Delta$ with $\psi$ a near-immersion.
Moreover, by possibly passing to a subcomplex of $\Delta$, we can assume that we have the following property.

\begin{description}
\item[($\star$)]
 For any edge $e$ of $P$ (resp.\ $Q,R$), the triangle containing $e$ is not mapped by $\psi$ to $\mathrm{Fix}(f)$ (resp.\ $\mathrm{Fix}(g),\mathrm{Fix}(h)$).
\end{description}

Let $D$ be obtained from $\Delta$ by attaching its second copy along the side $R$. Extend $\psi$ to a map from $D$ to $X$ defined as $h\circ \psi$ on the attached copy of $\Delta$. Let $f'=h\circ f, g'=h\circ g$. Denote $\alpha=\psi(P), \beta=\psi(Q)$ to be directed paths starting at $\psi(P\cap Q)$. Then $\psi$ restricts on $\partial D$ to $\alpha^{-1}\beta g'(\beta^{-1})f'(\alpha)$. As in the first paragraph of the proof of Lemma~\ref{lem:min surface}, we can extend $D$ and $\psi$ to an equivariant triangulation of $\widetilde S$ w.r.t.\ $(f',g')$, with equivariant map $\phi \colon \widetilde S \to X$. Since $\psi$ was a near-immersion and satisfied property {\bf ($\star$)}, $\phi$ is a near-immersion.
Thus by Proposition~\ref{prop:loxodromic}, $\langle f',g'\rangle$ contains a loxodromic element.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:torsion}]
Suppose by contradiction that for each $f\in G$ the set $\mathrm{Fix}(f)$ is nonempty. We will prove that for any finite set of elements $f_1,\ldots, f_n\in G$ the intersection $\mathrm{Fix}(f_1)\cap \cdots \cap \mathrm{Fix}(f_n)$ is nonempty. Case $n=2$ follows from Proposition~\ref{prop:pairs}. Consequently, case $n=3$ follows from Proposition~\ref{prop:triples}.
Since the fixed point sets are convex, the cases $n\geq 4$ follow from Helly's Theorem \cite[Thm~1.1]{I}. Setting $f_1,\ldots, f_n$ to be the generators of $G$ we obtain that the action of $G$ on $X$ is trivial, which is a contradiction.
\end{proof}

\section{Irrational loops have diameter $>\pi$}
\label{sec:graph}
In this section we prove Theorem~\ref{thm:graph+}.

The key ingredient in the proof is a reformulation of a theorem of Dehn~\cite{Dehn}, which states that a rectangle can be tiled by finitely many squares if and only if its sides are commensurable.

Let $(X,\mu_X)$, $(Y,\mu_Y)$ be measure spaces of finite measure. We will write $\mu$ instead of $\mu_X$ and $\mu_Y$ for brevity. We say that a pair $(A,B)$, such that $A \subseteq X$, $B \subseteq Y$ are measurable, is a \emph{rectangle in $X \times Y$} with \emph{side lengths $\mu(A)$ and $\mu(B)$}. A rectangle is a \emph{square} if its side lengths are equal.
We say that a  collection  $(A_1,B_1),(A_2,B_2), \ldots, (A_k,B_k)$ of rectangles is a \emph{rectangle tiling of $X \times Y$} if
\begin{itemize}
	\item $\bigcup_{i=1}^{k}A_i \times B_i = X \times Y$, and
	\item $\mu(A_i \cap A_j)\mu(B_i \cap B_j)=0$ for $1 \leq i < j \leq k$.
\end{itemize}
We say that a rectangle tiling is \emph{a square tiling} if it consists of squares.

\begin{thm}\label{thm:Dehn}
		Let $(A_1,B_1),$ $(A_2,B_2), \ldots, (A_k,B_k)$ be a square tiling of $X \times Y$. Then $\mu(X)$, $\mu(Y)$, $\mu(A_1),\ldots,\mu(A_k)$ are all commensurable.
\end{thm}

While it is not hard to see that Theorem~\ref{thm:Dehn} is equivalent to the theorem of Dehn stated above we include a proof both for completeness, and because we will need a technical modification of the result. The proof we give is essentially the one used by Hadwiger~\cite{Hadwiger} to prove a multidimensional generalization of Dehn's theorem, except that we follow the presentation from Aigner and Ziegler~\cite[Chap 29]{AZ}, which avoids the reliance on the existence of Hamel basis of $\bb{R}$ over $\bb{Q}$ and thus the dependence on the Axiom of Choice.

\begin{proof}[Proof of Theorem~\ref{thm:Dehn}]
	We start by showing that it suffices to consider the case when $X$ and $Y$ are finite. The reduction is fairly straightforward.
	 Define an equivalence relation $\sim$ on $X$, by setting $x_1 \sim x_2$ if for every $1 \leq i \leq k$ either $\{x_1,x_2\} \in A_i$ or $\{x_1,x_2\} \cap A_i =  \emptyset$. Clearly there are finitely many equivalence classes of elements of $X$ with respect to this relation, and we can identify the elements of $X$ lying in the same equivalence class. Thus we can assume that $X$ and, symmetrically, $Y$ are finite. Further, we may assume without loss of generality that every element of $X$ and $Y$ has a positive measure. It follows that for every $x \in X$ and $y \in Y$ there exists a unique index $i$ such that $x \in A_i$ and $y \in B_i$.

	 Let $V$ be a vector space over $\bb{Q}$ spanned by $\{\mu(x)\}_{x \in X} \cup \{\mu(y)\}_{y \in Y}$.
  Suppose first that $\mu(X)$ and $\mu(Y)$ are not commensurable. Then there exists a linear function $f: V \to \bb{Q}$ such that $f(\mu(X))=1$ and $f(\mu(Y))=-1$. By linearity we have
   \begin{align}\label{e:Dehn}
   	 -1 &= f(\mu(X))f(\mu(Y))= \sum_{x \in X}f(\mu(x))\sum_{y \in Y}f(\mu(y)) \notag \\ &=\sum_{i=1}^k f(\mu(A_i))f(\mu(B_i)) =  \sum_{i=1}^k f^2(\mu(A_i)) \geq 0,
   \end{align}
	 yielding the desired contradiction.

	 Suppose finally that $\mu(A_j)$ is not commensurable with $\mu(X)$ for some $0 \leq j \leq k$. Define a linear function $g: V \to \bb{Q}$ such that $g(\mu(X))=0$ and $g(\mu(A_j))=1$. Substituting $g$ instead of $f$ in (\ref{e:Dehn}) yields
$$
	0 = g(\mu(X))g(\mu(Y))=\sum_{i=1}^k g^2(\mu(A_i)) \geq g^2(\mu(A_j)) =1,
$$
 a contradiction.
\end{proof}

We will also need a technical variant of Theorem~\ref{thm:Dehn}.

\begin{lem}\label{lem:Dehn+}
	Let $(A_1,B_1),$ $(A_2,B_2), \ldots, (A_k,B_k)$ be a rectangle  tiling of $X \times Y$, such that for some $q,r \in \bb{R}_+$ and $a \in \bb{Q}$ we have
	\begin{itemize}
		\item $\mu(X)=2q+ar$, $\mu(Y)=q + (a/2-1)r$,
		\item  $(A_1,B_1)$ and $(A_2,B_2)$ are rectangles with sides $r$ and $q+r$,
		\item $(A_3,B_3), \ldots, (A_k,B_k)$ are squares,
		\item $\mu(A_3),\ldots,\mu(A_j)$ are commensurable with $r$ for some $3 \leq j \leq k$, and $\sum_{i=3}^j\mu^2(A_j) > (a-4)r^2$
	\end{itemize}
	Then $q$ and $r$ are commensurable.
\end{lem}

\begin{proof}
The proof parallels the proof of Theorem~\ref{thm:Dehn} above with minor modification to the calculation (\ref{e:Dehn}). We
define the vector space $V$ as in the proof of Theorem~\ref{thm:Dehn}, and assume for a contradiction that $q$ and $r$ are not commensurable. Then there exists a  linear function $f: V \to \bb{Q}$ such that $f(q)=a/2-1$ and $f(r)=-1$. Thus $f(\mu(X))= -2$, $f(\mu(Y))= 0$, and $f(\mu(A_i))f(\mu(B_i))=2-a/2$ for $i=1,2$, while $$\sum_{i=3}^j f(\mu(A_j))f(\mu(B_j)) = \sum_{i=3}^j\left(\frac{\mu(A_j)}{r}\right)^2 f^2(r)>  a-4.$$
Combining these estimates as in (\ref{e:Dehn}) we obtain
\begin{align*}
0 &= f(\mu(X))f(\mu(Y)) = \sum_{i=1}^{k}f(\mu(A_i))f(\mu(B_i)) \\ &= \sum_{i=1}^{2}f(\mu(A_i))f(\mu(B_i)) +
\sum_{i=3}^{j}f(\mu(A_i))f(\mu(B_i)) + \sum_{i=j+1}^{k}f^2(\mu(A_i)) \\ &> (4-a)+(a-4) =0,
\end{align*}
the desired contradiction.
\end{proof}

Let us now outline the proof of Theorem~\ref{thm:graph+}. As a first step (Claim~\ref{c:cycle} below) we prove that every cycle $C$ of $\Gamma'$ has length commensurable with $\pi$. We do so by examining the structure of shortest paths in $\Gamma$ between the pairs of points in $C$. The paths joining the pairs of points which lie at distance greater than $\pi$ in $C$ must take ``shortcuts'' which we refer to as \emph{chords}. We  construct a square tiling of a cylinder, where the squares correspond to the chords and apply Theorem~\ref{thm:Dehn}.

Next we prove in Claim~\ref{c:dumbbell} that certain paths of $\Gamma'$, called bars, also have length commensurable with $\pi$. We say that a path $B$ in $\Gamma'$ with endpoints $u$ and $v$ is a \emph{bar in $\Gamma'$ joining cycles $C_1$ and $C_2$}, if $C_1$ and $C_2$ are disjoint cycles of $\Gamma'$, and, moreover, $u \in C_1$, $v \in C_2$ and $C_1$ and $C_2$ are otherwise disjoint from $B$. Note that for every bar $B$ there exists a closed edge-path immersed in $\Gamma'$ that traverses $B$ twice and each of $C_i$ once. The existence of such an immersion allows us to adapt the argument we used for cycles to bars, but there are multiple technical hurdles to overcome, making this the most technical part of the proof. It is here, in particular, that we use Lemma~\ref{lem:Dehn+} and we additionally need extra information about the structure of chords of a cycle and between pairs of cycles, which we obtain in Claims~\ref{c:cycle} and~\ref{c:bicycle}.

To unify the argument for cycles and bars we start the proof of Theorem~\ref{thm:graph+} in the setting of Corollary~\ref{thm:graph} by considering closed edge-paths immersed in $\Gamma$.

Finally, in Claim~\ref{c:reduction}, we show that every segment  of $\Gamma'$ has length commensurable with $\pi$ by proving that it can be expressed as a rational linear combination of bars and cycles.

\begin{proof}[Proof of Theorem~\ref{thm:graph+}] We follow the steps outlined above, starting by considering immersed circles in $\Gamma'$.

	 Let $\gamma: C \to \Gamma'$ be a local isometry mapping a circle $C$ of length $l$ into $\Gamma'$.  We identify $C$ with $\mathbb{R}/l\mathbb{Z}$. This identification defines a natural $\mathbb{R}$-action on $C$.

	For $x,y \in C$, let $d(x,y)$ denote the distance between points $\gamma(x)$ and $\gamma(y)$ in $\Gamma$. As the girth of $\Gamma$ is at least $2\pi$, if  $0<d(x,y) < \pi$ then there exists a unique path from $\gamma(x)$ to $\gamma(y)$ in $\Gamma$ of length $d(x,y)$. We denote such a path by $P_{xy}$.

	Let $S$ be the set of points in $s \in C$  such that $\gamma(s)$ has degree at least three in~$\Gamma$. For $s,t \in S$ we say that $(s,t)$ is a \emph{chord of $\gamma$ of length $d_0$} if $0<d_0=d(s,t) < \pi$, and $P_{st}$
is disjoint  from $\gamma([s-\varepsilon,s) \cup (s,s+\varepsilon] \cup [t-\varepsilon,t) \cup (t,t+\varepsilon])$ for some $\varepsilon >0$. Note that our chords are directed, that is we distinguish between the chords $(s,t)$ and $(t,s)$.

	For $x,y \in C$ we say that $(x,y)$ \emph {uses a chord $(s,t)$} if there exists a path $P$ from $\gamma(x)$ to $\gamma(y)$ in $\Gamma$ of length $d(x,y)$ such that $P$ is obtained by concatenating paths $\gamma([x,s])$, $P_{st}$ and $\gamma([t,y])$, where we denote by $[a,b]$ for $a,b \in C$ the shortest of the two intervals in $C$ with endpoints $a$ and $b$. Clearly, $(x,y)$ uses a chord $(s,t)$ of length $d_0$ if and only if there exists $\sigma,\tau \in \mathbb{R}$ such that $x = s+\sigma$, $y =t + \tau$, and $|\sigma|+|\tau| \leq \pi - d_0$. Moreover, if the last inequality is strict, then $(s,t)$ is the unique chord used by $(x,y)$.

	Note further that for every $(x,y) \in C^2$ if $(x,y)$ uses no chord, then there exist $z,z' \in C$ such that $\gamma(z)=\gamma(z')$, and there exists a path from $\gamma(x)$ to $\gamma(y)$ in $\Gamma$ of length $d(x,y)$ obtained by concatenating paths $\gamma([x,z])$  and $\gamma([z',y])$. Moreover, if $d(x,y)<\pi$ then the converse also holds. If $(x,y)$ uses no chord and the distance between $x$ and $y$ in $C$ is larger than $\pi$ then we say that $(x,y)$ is a \emph{spliced pair}. We denote the set of spliced pairs by $Spl(\gamma)$.

	We now describe the square tiling to which we apply Theorem~\ref{thm:Dehn} and Lemma~\ref{lem:Dehn+}. Let $R=R(\gamma)\subset C^2$ be the annulus consisting of points $(x,y)$ with $x$ and $y$ at distance at least $\pi$ in $C$. Note that $R$ is isometric to the product of a circle of length $l\sqrt{2}$ and an interval of length $l\frac{\sqrt{2}}{2}-\pi\sqrt{2}$. Let $\mc{K}=\mc{K}(\gamma)$ denote the set of all chords, and let $S(K)$ for $K \in \mc{K}$ denote the set of pairs $(x,y) \in C^2$ which use~$C$. For a chord $K=(s,t)$ of length $d_0$, let $z=\pi - d_0$. As noted above, $$S(K) = \{(s+\sigma,t + \tau ) \: | \: -z \leq \sigma + \tau \leq z,  -z \leq \tau - \sigma \leq z \},$$ which is a square in $R$ with side length $z\sqrt 2$ and one side pair parallel to $\partial R$. Moreover, for distinct $K$ the squares $S(K)$ have disjoint interiors. Finally note that $Spl(\gamma)=\mathrm{int}(R)-\bigcup_{K \in \mc{K}}S(K)$ by definition.

	We will also use some of the terminology introduced above when considering a subgraph $\Lambda$ of $\Gamma$, rather than an immersion. For vertices $s,t$ of $\Lambda$ we say that $(s,t)$ is a \emph{chord of $\Lambda$ of length $d_0$ and area $2(\pi-d_0)^2$} if
	$0<d_0=d_{\Gamma}(s,t) < \pi$ and the first and last edge of the unique path $P$ from $s$ to $t$ in $\Gamma$ of length $d_0$ do not lie in~$\Lambda$.
Note that if $\gamma:C \to \Gamma$ is an immersion as above, and $s,t \in C$ are such that $(\gamma(s),\gamma(t))$ is a chord of $\gamma(C)$ of length $d_0$ then $(s,t)$ is a chord of $\gamma$ of length $d_0$. If $\gamma$ is injective then the converse also holds.

	We are now ready for the first major claim, which in particular establishes the theorem in the case when $\Gamma'$ is a cycle.

	\begin{claim}\label{c:cycle}
		Let $C$ be a cycle in $\Gamma'$ of length $l$. Then
		\begin{description}
			\item[a)] $l$ is commensurable with $\pi$,
			\item[b)] the length of every chord of $C$ is commensurable with $\pi$,
			\item[c)] for every point $p \in C$ the total area of chords of $C$ with both endpoints in $C-\{p\}$ is at least $2\pi(l-2\pi)$.
		\end{description}
	\end{claim}

    \begin{proof} Let $\gamma$ be an isometry from a circle of length $l$ onto $C$. For simplicity of notation we identify the domain of $\gamma$ with $C$.

    	Note that
 $Spl(\gamma)= \emptyset$. Thus  $\mathrm{int}(R(\gamma)) \subseteq \bigcup_{K \in \mc{K}(\gamma)}S(K) \subseteq R(\gamma)$. As $\mc{K}(\gamma)$ is finite, it follows that $R(\gamma) =\bigcup_{K \in \mc{K}(\gamma)}S(K) $, and Theorem~\ref{thm:Dehn} implies that   $l\sqrt{2}$ and $l\frac{\sqrt{2}}{2}-\pi\sqrt{2}$ are commensurable. Thus a) holds, and  Theorem~\ref{thm:Dehn} similarly implies that b) holds.

	It remains to establish c). First note that the total area of all chords of $C$ is equal to the area of $R(\gamma)$, which is $l(l-2\pi)$. It remains to upper bound the area of chords of $C$ with at least one end in $p$, i.e.\ chords of $\gamma$ with at least one end in $s = \gamma^{-1}(p)$. Let $K_1=(s,t_1),K_2=(s,t_2),\ldots,K_n=(s,t_n)$ be all the chords starting at $s$.
	Suppose that $K_i$ has length $\pi - z_i$. Then the area of $S(K_i)$ is equal to $2z_i^2 $, and $S(K_i)$ intersects the line $(\{s\} \times C) \cap R$ in an interval of length $2z_i$.  As $(\{s\} \times C) \cap R$ has length $l-2\pi$, we have $\sum_{i=1}^n z_i \leq l/2 -\pi$, and so the sum of the areas of the chords starting at $s$ is at most $2(\sum_{i=1}^n z_i)^2 \leq 2(l/2 -\pi)^2.$ It follows that the area of chords of $C$ with at least one end in $p$, is at most $(l-2\pi)^2$. As $l(l-2\pi) - (l-2\pi)^2 = 2\pi(l-2\pi)$, c) follows. \end{proof}

	Next we need to extend Claim~\ref{c:cycle} b) to a pair of disjoint cycles.

	\begin{claim}\label{c:bicycle}
		Let $C_1$, $C_2$ be disjoint cycles of $\Gamma'$. Then every chord of $C_1 \cup C_2$ has length commensurable with $\pi$.
	\end{claim}

    \begin{proof} Let $l_i$ be the length of $C_i$ for $i=1,2$.
    	By Claim~\ref{c:cycle} a) and b) the lengths $l_1$ and $l_2$ are commensurable with $\pi$ and so is the length of every chord of $C_1$ and $C_2$. It remains to establish the claim for chords with one endpoint in $C_1$ and another in~$C_2$.

    	To do so we parallel the proof of Claim~\ref{c:cycle} and the preceding construction of the square tiling. Let $\mc{K}$ be the set of chords $(s,t)$ of $C_1 \cup C_2$ with $s \in C_1$, $t \in C_2$. We say that a pair $(x,y) \in C_1 \times C_2$ \emph{uses a chord  $(s,t) \in \mc{K}$} if there exists a path of length $d_{\Gamma}(x,y)$ from $x$ to $y$ in $\Gamma$ obtained by concatenating a path in $C_1$, the minimal length path from $s$ to $t$, and a path in $C_2$. Let $S(K) \subseteq C_1 \times C_2$ be the set of pairs of points using  the chord $K$ of length $\pi-z$. Then analogously to the earlier observations we have that $S(K)$ is a square with side  length $\sqrt 2 z$, the squares $\{S(K)\}_{K \in \mc{K}}$ cover
    	$C_1 \times C_2$ and have disjoint interiors.

To apply Theorem~\ref{thm:Dehn} we need to transform the tiling  of $C_1 \times C_2$ into a tiling of a product set, where the squares inherit the product structure.
We do it as follows. Let $n_1,n_2$ be positive integers such that $n_1l_1=n_2l_2$. By lifting our tiling of $C_1 \times C_2$ to the product of the $n_1$-fold cover of $C_1$ and the $n_2$-fold cover of $C_2$ we may assume without loss of generality that $C_1$ and $C_2$ have the same length $l$.

  Let $\gamma_1: \bb{R} /l\bb{Z}\to C_1$ and $\gamma_2: \bb{R} /l\bb{Z}\to C_2$ be isometries. Let $\psi: \bb{R} /l\bb{Z}\times \bb{R} /l\bb{Z}\to  C_1 \times C_2$ be defined by $\psi(x,y)=(\gamma_1(x+y),\gamma_2(x-y))$. Consider a chord $K=(s,t) \in \mc{K}$ of length $\pi-z$. Then $\psi^{-1}(S(K))$ consists of two squares of the form $[x-z/2,x+z/2] \times [y-z/2,y+z/2]$, where $(x,y)\in (\bb{R}/l\bb{Z})^2$ is either one of the two pairs satisfying $\gamma_1(x+y)=s,\gamma_2(x+y)=t$. Thus the preimage of our tiling of $C_1 \times C_2$ is a square tiling of  $(\bb{R}/l\bb{Z})^2$ satisfying the conditions of Theorem~\ref{thm:Dehn}, and by this theorem if $K \in \mc{K}$ is a chord of length $\pi-z$, then $z$ is commensurable with $l$. As $l$ is commensurable with $\pi$, the claim follows.
  \end{proof}

We are now ready to establish that the conclusion of the theorem holds for bars.

	\begin{claim}\label{c:dumbbell}
		The length of every bar of $\Gamma'$ is commensurable with $\pi$.

	\end{claim}

	\begin{proof}
		Let $B$ be a bar in  $\Gamma'$ with endpoints $u$ and $v$, of length $b$, joining cycles $C_1$ and $C_2$ of length $l_1$ and $l_2$ respectively such that $u \in C_1$, $v \in C_2$. Let $\gamma: C \to \Gamma'$ be a local isometry from a circle $C$ of length $l=l_1+l_2+2b$, traversing $B$ twice, and each of $C_1$ and $C_2$ once.
		Our goal is to apply Lemma~\ref{lem:Dehn+} to a tiling of $R(\gamma)$ defined in the beginning of the proof.

		 Unlike in Claim~\ref{c:cycle}, the set $Spl(\gamma)$ of spliced pairs is not empty, but it is not hard to analyze. Let $\gamma^{-1}(B)=[s_1,s_1+b] \cup [s_2-b,s_2]$ for some $s_1,s_2 \in C$.
		  Then $Spl(\gamma) $ consists of two rectangles: one with corners $(s_1-\pi,s_2),(s_1,s_2+\pi),(s_1+b+\pi,s_2-b),(s_1+b,s_2-b-\pi)$, and the other obtained  from it by permuting the coordinates.

		  Let $r =\pi \sqrt 2$, and let $q = b \sqrt 2$. Let $a=(l_1+l_2)/\pi$. Then $l\sqrt 2 = 2q+ar$, and thus $R(\gamma)$ can be considered as a product of a circle $\bd R$ of length $2q+ar$ and an interval of length $q+(a/2-1)r$.
		  Each of rectangles in $Spl(\gamma)$ has a side of length $r$ parallel to $\bd R(\gamma)$, and a side of length $q+r$ orthogonal to it.  The cylinder $R(\gamma)$ is tiled by the rectangles in $Spl(\gamma)$ and squares in $\{S(K)\}_{K \in \mc{K}(\gamma)}$, and the first three conditions of Lemma~\ref{lem:Dehn+} are satisfied for this tiling. Note that Lemma~\ref{lem:Dehn+} would immediately imply the claim.

		  Thus to prove the claim it remains to verify the last condition of Lemma~\ref{lem:Dehn+}, i.e.\ to show that the total area of the squares corresponding to the chords of $\gamma$ with length commensurable with $\pi$ is strictly greater than $(a-4)r^2 = 2\pi(l_1+l_2)-8\pi^2$.

		  By Claims~\ref{c:cycle} b) and~\ref{c:bicycle}, every chord of $C_1 \cup C_2$ has length commensurable with $\pi$, and if such a chord has no endpoint in $\{u,v\}$ then it corresponds to a chord of $\gamma$ of the same length.
		  By Claim~\ref{c:cycle} c) the total area of the chords of $C_i$ with no endpoint in $\{u,v\}$ is at least  $2\pi l_i-4\pi^2$.
	It remains to find at least one chord of $C_1 \cup C_2$ with one endpoint in $C_1 - \{u\}$ and another in $C_2 - \{v\}$. Indeed, consider a point $x \in C_1$ at distance at least $\pi$ from $u$ in $C_1$, and a point $y \in C_2$ at distance at least $\pi$ from $u$ in $C_2$. Then the chord used by $(x,y)$ cannot have an endpoint in $\{u,v\}$ and so is as required.
	  		\end{proof}

Let $V(\Gamma'), E(\Gamma')$ denote the vertex and edge set of the graph $\Gamma'$.
We finish the proof of the theorem by reducing it to Claims~\ref{c:cycle} a) and~\ref{c:dumbbell}. For the reduction it will be convenient for us to think of subgraphs of $\Gamma'$ as elements of $\bb{Q}^{E(\Gamma')}$, the vector space of formal linear combinations of edges of $\Gamma'$ with rational coefficients. Thus we identify every subgraph $\Lambda$ of $\Gamma'$ with $\sum_{e \in E(\Lambda)}e$. The theorem immediately follows from Claims~\ref{c:cycle} a) and~\ref{c:dumbbell} and the next claim, which uses the above convention.

\begin{claim}\label{c:reduction}
Every segment of $\Gamma'$ is a rational linear combination of cycles and bars of $\Gamma'$.
\end{claim}

\vskip10pt \noindent \emph{Proof.}
	Let $P$ be a segment of $\Gamma'$. We assume without loss of generality that $\Gamma'$ is chosen minimal subject to the conditions that the minimum degree of $\Gamma'$ is at least two, and $P$ is a segment of $\Gamma'$. We further assume by suppressing vertices of degree two in $\Gamma'$ that every vertex of $\Gamma'$ has degree at least three. In particular, every segment of $\Gamma'$ is an edge. Subject to these assumptions there are only a few isomorphism types of graphs to consider, and the proof proceeds by exhaustive case analysis.

	Note first that every non-loop edge $e \in E(\Gamma')$ shares at least one endpoint with $P$, as otherwise $\Gamma' - e$ contradicts the minimality of $\Gamma'$. Similarly, if $w \in V(\Gamma') -V(P)$ is incident to a loop then $\deg(w)=3$. (We use $\deg(x)$ to denote the degree of a vertex $x$ in $\Gamma'$.)  By the previous observation the non-loop edge incident to $w$ shares an endpoint with $P$. We call such a vertex $w$ a \emph{pseudoleaf} of $\Gamma'$.

	Let $u$ and $v$ be the endpoints of $P$. Suppose first that $\deg(u) \geq 4$. Let $e \in E(\Gamma')-E(P)$ be any edge incident to $u$. By minimality of $\Gamma'$, either $u$ or $v$ has degree at most two in $\Gamma'- e$. Thus either $e$ is a loop and $\deg(u) = 4$, or $e$ joins $u$ and $v$ and $\deg(v) = 3$. As one of these outcomes holds for every edge in $E(\Gamma')-E(P)$ incident to $u$, we conclude that $\Gamma'$ consists of $P$, a loop incident to $u$, an edge parallel to $P$, a pseudoleaf adjacent to $v$, which we denote by $w$, and loop incident to $w$.

	It is not hard to verify that the claim holds in this case, and we do so using the following notation, which  will also be used in all the remaining cases.  We  denote the edge with endpoints $x$ and $y$ by $xy$, and in the case when there are several such edges in $\Gamma'$ we denote them by $xy_1$, $xy_2$,\ldots. In particular, let $P=uv_1$.

	Returning to our case, note that $wv$ is a bar joining a loop at $w$ and a cycle $P + uv_2$, while $wv+P$ is a bar joining loops at $w$ and $u$. Thus $P=(wv+P)-wv$ is a difference of two bars, and the claim holds in this case. The case $\deg(v) \geq 4$ is symmetric.

    It remains to consider the case $\deg(u)=\deg(v)=3$. Suppose next that there exists $w \in V(\Gamma')-\{u,v\}$ such that $w$ is not a pseudoleaf. As every non pseudoleaf vertex in  $V(\Gamma')-\{u,v\}$ is incident to at least three edges which have $u$ or $v$ as their second endpoint, every vertex in $V(\Gamma')$  except $u,v$ and $w$ is a pseudoleaf.

    If $\deg(w)\geq 4$, then $w$ is joined to each of $u$ and $v$ by a pair of parallel edges.
    In this case each of $wv_1+wv_2$, $wu_1+wu_2$, $wv_1+wu_1+P$, $wv_2+wu_2+P$ is a cycle, and
    $P$ is a rational linear combination of these cycles. Thus the claim holds.

    If $\deg(w)=3$, we suppose without loss of generality that $w$ is joined to $u$ by a pair of parallel edges, and to $v$ by an edge. Then the remaining edge incident to $v$ must have a pseudoleaf, which we denote by $x$, as its second endpoint. In this case, $xv$ is a bar joining the loop at $x$ to the cycle $P+uw_1+wv$, and $xv+P$ is a bar joining the loop at $x$ and the cycle $uw_1+uw_2$. Therefore, $P$ is the difference of two bars, and the claim holds.

    We reduced our analysis to the case when $\deg(u)=\deg(v)=3$ and every vertex in $V(\Gamma')-\{u,v\}$ is a pseudoleaf. We now consider subcases depending on the number of edges joining $u$ to $v$.

    If there are three such edges, then $P+uv_2$, $P+uv_3$ and $uv_2+uv_3$ are each cycles, and $P$ is their rational linear combination. If exactly two edges join $u$ to $v$, then there is a pseudoleaf adjacent to each of $u$ and $v$. Denote these pseudoleafs by $u'$ and $v'$ respectively.  Then $uu'$ is a bar joining the loop at $u'$ and $P+uv_2$, and similarly $vv'$ is a bar. The path $uu'+P+vv'$ is also a bar, joining the loops at $u'$ and $v'$, and $P$ is a rational linear combination of the above three bars.

    It remains to consider the case when $P$ is the unique edge between $u$ and $v$. In this case each of $u$ and $v$ is either incident to a loop, or adjacent to two pseudoleafs. Up to symmetry there are three final cases to consider.

    If both $u$ and $v$ are incident to a loop then $P$ is a bar. If $u$ is incident to a loop and $v$ is adjacent to pseudoleafs $v'$ and $v''$, then each of the paths $v'v+P$, $v''v+P$ and $v'v+v''v$ is a bar joining the loops at its endpoints, and $P$ is a rational linear combination of these bars. Finally, suppose that $v$ is adjacent to pseudoleafs $v'$ and $v''$, and $u$ is adjacent to pseudoleafs $u'$ and $u''$. Then $P$ is a rational combination of bars $v'v+v''v$, $u'u+u''u$, $v'v+P + u'u$, $v''v+P+u''u$. Thus the claim holds in this last case.
 \end{proof}

\begin{bibdiv}
\begin{biblist}

\bib{AZ}{book}{
	title={Proofs from the Book},
	author={Aigner, Martin}
	author={Ziegler, G{\"u}nter M.},
	volume={274},
	year={2018},
	publisher={Springer}
}

\bib{BB}{article}{
   author={Ballmann, Werner},
   author={Brin, Michael},
   title={Orbihedra of nonpositive curvature},
   journal={Inst. Hautes \'{E}tudes Sci. Publ. Math.},
   number={82},
   date={1995},
   pages={169--209 (1996)}}

\bib{Babu}{article}{
   author={Ballmann, Werner},
   author={Buyalo, Sergei},
   title={Nonpositively curved metrics on $2$-polyhedra},
   journal={Math. Z.},
   volume={222},
   date={1996},
   number={1},
   pages={97--134}}

\bib{BestvinaProblemOLD}{article}{
	AUTHOR = {Bestvina, Mladen},
	TITLE = {Questions in Geometric Group Theory},
	date = {2000},
	eprint = {https://www.math.utah.edu/~bestvina/eprints/questions.pdf}
}

\bib{BridsonProblem}{article}{
	AUTHOR = {Bridson, Martin R.},
	TITLE = {Problems concerning hyperbolic and ${\rm CAT}(0)$ groups},
	date = {2007},
	eprint = {https://docs.google.com/file/d/0B-tup63120-GVVZqNFlTcEJmMmc/edit}
}

\bib{BH}{book}{
   author={Bridson, Martin R.},
   author={Haefliger, Andr\'e},
   title={Metric spaces of non-positive curvature},
   series={Grundlehren der Mathematischen Wissenschaften [Fundamental
   Principles of Mathematical Sciences]},
   volume={319},
   publisher={Springer-Verlag},
   place={Berlin},
   date={1999}
   }

\bib{Cap}{article}{
	author={Caprace, Pierre-Emmanuel},
	title={Lectures on proper $\rm CAT(0)$ spaces and their isometry groups},
	conference={
		title={Geometric group theory},
	},
	book={
		series={IAS/Park City Math. Ser.},
		volume={21},
		publisher={Amer. Math. Soc., Providence, RI},
	},
	date={2014},
	pages={91--125}}

\bib{CL}{article}{
   author={Caprace, Pierre-Emmanuel},
   author={Lytchak, Alexander},
   title={At infinity of finite-dimensional ${\rm CAT}(0)$ spaces},
   journal={Math. Ann.},
   volume={346},
   date={2010},
   number={1},
   pages={1--21}}

\bib{Dehn}{article} {
	title = {{\"U}ber zerlegung von rechtecken in rechtecke},
	author = {Dehn, Max},
	journal = {Math. Ann.},
	volume = {57},
	number = {3},
	pages = {314--332},
	year = {1903},
}

\bib{Gri}{article}{
	AUTHOR = {Grigorchuk, Rostislav I.},
	TITLE = {Degrees of growth of finitely generated groups and the theory
		of invariant means},
	JOURNAL = {Izv. Akad. Nauk SSSR Ser. Mat.},
	VOLUME = {48},
	YEAR = {1984},
	NUMBER = {5},
	PAGES = {939--985},
}

\bib{Hadwiger}{book}{
	title={Vorlesungen {\"u}ber Inhalt, Oberfl{\"a}che und Isoperimetrie},
	author={Hadwiger, Hugo},
	year={1957}
	publisher={Springer}
}

\bib{HMP}{article}{
	author={Hanlon, Richard Gaelan},
	author={Mart\'{i}nez-Pedroza, Eduardo},
	title={Lifting group actions, equivariant towers and subgroups of
		non-positively curved groups},
	journal={Algebr. Geom. Topol.},
	volume={14},
	date={2014},
	number={5},
	pages={2783--2808},
}

\bib{H}{book}{
   author={Hatcher, Allen},
   title={Algebraic topology},
   publisher={Cambridge University Press, Cambridge},
   date={2002},
   pages={xii+544}}

\bib{I}{article}{
   author={Ivanov, Sergei},
   title={On Helly's theorem in geodesic spaces},
   journal={Electron. Res. Announc. Math. Sci.},
   volume={21},
   date={2014},
   pages={109--112}}

\bib{KapovichProblems}{article}{
	AUTHOR = {Kapovich, Michael},
	TITLE = {Problems on boundaries of groups and Kleinian groups},
	date = {2008},
	eprint = {https://docs.google.com/file/d/0B-tup63120-GOC15RW8zMDFZZjg/edit}
}

\bib{LP}{article}{
   author={Lamy, St\'ephane},
   author={Przytycki, Piotr},
   title={Presqu'un immeuble pour le groupe des automorphismes mod\'er\'es},
   eprint={arXiv:1802.00481},
   status={sumbitted},
   date={2018}}

\bib{Mar}{article}{
	author={Marquis, Timoth\'{e}e},
	title={A fixed point theorem for Lie groups acting on buildings and
		applications to Kac-Moody theory},
	journal={Forum Math.},
	volume={27},
	date={2015},
	number={1},
	pages={449--466}}

\bib{M}{article}{
   author={Masur, Howard},
   title={Closed trajectories for quadratic differentials with an
   application to billiards},
   journal={Duke Math. J.},
   volume={53},
   date={1986},
   number={2},
   pages={307--314}}

\bib{Swe}{article}{
	author={Swenson, Eric L.},
	title={A cut point theorem for ${\rm CAT}(0)$ groups},
	journal={J. Differential Geom.},
	volume={53},
	date={1999},
	number={2},
	pages={327--358}}

\bib{Z}{article}{
   author={Zeeman, E. Christopher},
   title={Relative simplicial approximation},
   journal={Proc. Cambridge Philos. Soc.},
   volume={60},
   date={1964},
   pages={39--43}}

\end{biblist}
\end{bibdiv}

\end{document}


\section{Introduction}
\label{sec:intro}

One of the main problems mobile developers face when building apps is the
need to run tests under a number of different settings (e.g., mobile device
models, operative system
version)~\citep{moran2017automated,muccini2012software}. For instance, the
appearance of the user interface may change in devices with different screen
sizes and resolutions. This problem is also evident when testing energy
consumption.

Moreover, measuring energy consumption with power tools is a cumbersome task.
Developers need to create a setup that often requires disassembling the
device and acquire specialized power tools, as shown in
Fig.~\ref{fig:monsoon}. Such setup is expensive, time-consuming and requires
skills out of the domain of most practitioners. Nevertheless, this setup ends up
being unused most of the time, since developers do not need to run energy
measurements continuously during development.

\begin{figure}
  \centering
\includegraphics[width=0.6\linewidth]{figures/monsoon}
\caption{\emph{Monsoon} power monitor connected to the Nexus 5X smartphone.}
\label{fig:monsoon}
\vspace{-1.5em}
\end{figure}

To overcome these issues, tools have been proposed to measure
energy consumption using software-based
estimators~\citep{hao2013estimating,di2017petra,chowdhury2018greenscaler,zhang2010accurate}. These tools are able to provide accurate estimations within the
context in which they were trained~\citep{di2017software}. However, when they
are used against new settings --- for instance, different devices, operative
system (OS) versions, or API methods --- one cannot be sure about the reliability
of those measurements. Thus, there is a need to continuously collect energy
measurement data in order to have accurate energy models.

Although energy models are very handy, practitioners cannot be sure of whether
a model is trained for a given use case. A developer should not rely on a model
that was trained for different scenarios. However, this information is not
always accessible to developers. This is critical when developers need to
make design decisions based on the energy efficiency of their code.

There is a tradeoff between using hardware and software-based energy
estimators. None of these approaches is ready to be adopted by the community of
mobile developers on a global scale. In this paper, we address the
aforementioned issues by proposing a hybrid system that provides the
best of these two approaches. The system provides energy measurements as a
service and is able to switch between software and hardware-based measurements,
depending on the app under test and its running environment.

In this paper, we propose EMaaS, a peer-to-peer cloud-based system that delivers
energy measurements as a service for mobile applications. In particular, the
system addresses the following issues:

\begin{enumerate}

  \item Power monitor tools are complex and impractical in a
real mobile development scenario.

  \item Reliable energy models need to be
continuously updated with new data, collected using hardware-based power monitors.

  \item The context in which a given energy model can provide reliable
  measurements is not always clear.

\end{enumerate}

\section{The Vision}

We envisage a crowd-sourced system to deliver lightweight energy tests as a
service. It combines energy models with power monitors to provide the most
accurate energy measurements without requiring a cumbersome setup of power
tools. Moreover, the system allows developers to measure their apps in mobile
devices from different manufacturers.

Developers only need to provide an executable package with (1) the application
build (e.g. an \emph{APK}\footnote{APK is the package file format used by the
Android OS for distribution and installation of mobile apps and middleware.} in
the case of the Android OS) and (2) the instrumentation build with the test
cases to be measured (e.g., the instrumentation \emph{APK} for \emph{Espresso}
test cases on Android).

Fig.~\ref{fig:arch} outlines the high-level architecture of the system.
It features three types of users:

\begin{itemize}

 \item\textbf{Developers} use the system to collect energy consumption
measurements for their apps.

 \item\textbf{Providers} allow other users to use their mobile devices to run
energy measurements. In this case, energy consumption is estimated using an
energy model.

 \item\textbf{Super-Providers} are special \textbf{providers} that provide
energy measurements using a hardware-based power monitor.

\end{itemize}

The same user can act as a developer, provider, or super-provider,
simultaneously. When super-providers are not available to run a given
measurement, providers take their place using energy models.

As an example, Fig.~\ref{fig:arch} highlights three connected peers, marked
with green thick lines: one developer, one provider, and one super-provider. The
same developer asks the system to run energy tests in two different device
models, X and Y. The system assigns a super-provider for device model X but no
super-provider was available for device Y. Although a super-provider for Y
exists in the system, it is busy dealing with another measurement task. Thus,
since the system had a reliable energy estimator for device model Y, it
assigned the task to a provider, as depicted in the illustration. If the system
did not have a suitable energy model for the given scenario, the task would
wait until a super-provider for model Y would become available.

In this setting, the developer does not own any mobile device or power monitor
tool. They are being provided by other users in the system. With this approach,
it delivers 1) a better use of resources, 2) access to a bigger set of
devices and tools, and 3) a simple/affordable setup to measure energy
consumption.

\begin{figure}
\includegraphics[width=\linewidth]{figures/arch}
\caption{High-level vision of the system for energy measurements as a service.}
\vspace{-1.5em}
\label{fig:arch}
\end{figure}

Under the hood, the system integrates two modules to bring the best of both
hardware and software-based power monitors: the \textbf{Energy Model} and the
\textbf{Reliability Consultant}.

The \textbf{Energy Model} is based on approaches from previous work, which uses
data collected from hardware-based power monitors to train models of power
consumption. The main limitation of current state-of-the-art solutions is the
lack of data to train energy models~\citep{chowdhury2018greenscaler}. We
mitigate this limitation by continuously updating models using data collected
from hardware-based power monitors (i.e., super-providers). Thus, in this
solution, providers always estimate energy consumption using up-to-date energy
models.

Another limitation is the fact that these solutions rely on in-vitro data to
train their models. Extrapolating these estimators to different devices can
compromise measurements. On contrary, this solution can virtually scope any
execution environment, given that it is available from a
\textbf{super-provider}. In addition, since the power model is continuously
improving every time developers run their energy tests, it is able to adapt to
new paradigms, devices, or OS versions when they come to market. Going back to
the example given by Fig.~\ref{fig:arch}, if a reliable energy model for the
given test cases was not available for device Y, the system would collect data
from super-providers over time. Eventually, the system would have enough data
to learn a new energy model that could provide reliable estimations for the new
scenario.

Although energy models can provide very accurate estimations, one needs to
assess whether they are ready to be used in a given context. I.e., a given
energy model might not be ready yet to measure the energy consumption of apps that
use specific libraries. The system needs to assess whether, for a given
developer request, it is acceptable to return an energy estimation. If not, the
system has to alert the developer or wait for a super-provider to be available.
We propose the module \textbf{Reliability Consultant} to solve this problem.

In parallel with the \textbf{Energy Model}, the \textbf{Reliability Consultant}
module will inspect the reliability of the estimator. Super-providers will run
simultaneously hardware and software-based measurements. The reliability of
energy models is assessed using results from hardware as ground-truth. We then
construct reliability as a metric that is negatively correlated to the power
error ($\epsilon$), given by the following equation:

\begin{equation}
  \epsilon = \frac{E_{measured} - E_{estimated}}{\Delta t}
\end{equation}

\noindent where $E_{measured}$ and $E_{estimated}$ are the energy consumption
measured by the power monitor and the estimator, respectively, and $\Delta t$
is the duration of execution of the energy test. For high reliability,
$\epsilon$ should be close to zero.

In addition, we use static analysis to collect data regarding the app and its
execution environment --- for instance, frequency of library/API calls,
complexity metrics, framework, API level, OS version, etc. This data will be
used to train a regression model that estimates the power error of the
software-based estimator.

As a side contribution we propose to answer the following research questions:

\highlight{RQ1: Can static analysis be used to assess the reliability of energy
models for different running environments? }

\highlight{RQ2: What is the improvement of using hybrid energy measurements
over software-based measurements? }

\highlight{RQ3: What is the proportion of software vs. hardware measurements? }

\begin{figure}
  \centering
\includegraphics[width=0.9\linewidth]{figures/decision}

\caption{How a normal energy measurement request is processed, starting from the
perspective of a developer.}

\label{fig:decision}
\vspace{-1.5em}
\end{figure}

The combination of the modules \textbf{Reliability Consultant}, \textbf{Energy
Model}, and \textbf{Hardware-based Power Monitor} is depicted in
Fig.~\ref{fig:decision}. Upon a measurement request from the developer, the
system asks the \textbf{Reliability Consultant} whether the measurement needs
to use a \textbf{Hardware-based Power Monitor}. If not, the estimation provided
by the \textbf{Energy Model} is returned to the developer. On contrary, if the
\textbf{Reliability Consultant} does not consider the \textbf{Energy Model}
reliable for the given mobile app, an hardware-based measurement is provided,
and the \textbf{Energy Model} and \textbf{Reliability Consultant} are updated
with new data.

\section{Why is it New?}

Very interesting tools have been proposed by researchers to measure energy
consumption. However, given the ever-changing nature of the mobile application
world, keeping them up-to-date and ready to use for developers can be
challenging. This system is able to be continuously updated and to adapt its
energy model to new settings.

Moreover, this will help researchers having more valuable contributions in the
field of energy efficiency of mobile applications. Recent contributions are
using energy models to estimate
energy consumption~\citep{li2014empirical,li2015optimizing,sahin2014code,chowdhury2018exploratory}.
However, the validity of these measurements is not easily assessed. In
addition, most contributions have their experiments limited to a small set of
environments, providing a relevant threat to the validity.

This work bridges the gap between industry and academia in terms of energy
measurements for mobile applications. To the best of our knowledge, this is the
first time reliable energy measurements can be deployed to the industry without
requiring an expensive setup. Furthermore, no prior work has leveraged a tool
to assess the compatibility between an energy model and its running environment.

\section{Risks}

The main risks that can affect this system are related to \emph{Security} and
\emph{Privacy}.

\paragraph{Security}

The system has to account for malware mobile software that can affect the
devices of providers.

\paragraph{Privacy}

Developers do not want to disclosure their apps before deployment. Mechanisms
need to be deployed to prevent mobile applications from being collected by
malicious providers or super-providers. Furthermore, the mobile devices
available in the system need to be protected from mal-intended developers. The
data stored in the devices should not be accessed by the system or the mobile
application under test.

\paragraph{Measurement best practices}

Typically, energy measurements require rigorous approaches to mitigate
potential bias on measurements. For instance, the app under analysis should be
running in isolation on the phone while no other apps are running in
parallel~\citep{cruz2017performance}.

To address these issues, energy tests have to be executed in a closed
environment, instantiated in the mobile device. In some cases, the device may
have to be restored. Thus, providers may not be able to use their own personal
devices. For safety reasons, the system may be limited to devices exclusively
acquired for app development.

\section{Next Steps}

In this paper, we present the idea of using peer-to-peer cloud computing to
deliver reliable energy measurements as a service. We are interested in
improving the way researchers and developers are profiling the energy
consumption of their mobile software. By making it available as service, we aim
to help developers make informed design decisions regarding the energy
efficiency of their code.

In the early stages, EMaaS will require a considerable software development
effort. Thus, we divide the implementation into three steps. In the first step,
we will be interested in delivering a system that yields hardware-based
measurements. This will serve as a base system to add more sophisticated energy
measurement techniques in the following steps.

The second step will consist of including the \textbf{Energy Model}. In particular,
we will be looking at how to improve existing models for energy estimation. One
big advantage of our approach is the access to real measurement data collected
from a wide variety of devices and OSs.

Finally, in the third step, we will be adding the \textbf{Reliability
Consultant}. We will use measurements collected from both energy models and
power monitors to train a regression model of the reliability of energy
estimators in a particular execution scenario.

For an initial proof-of-concept, the system will support Android apps
instrumented with \emph{Espresso} test cases, since it has been the most
suitable UI test framework for energy
measurements~\citep{cruz2018measuring,cruz2019attention}. In order to initially
avoid privacy and security risks, the system will be exclusively available to
invited users.

\section{Acknowledgments}

Luis Cruz is sponsored by the ERDF -- European Regional Development Fund through
the Operational Programme for Competitiveness and Internationalisation -
COMPETE 2020 Programme and by National Funds through the Portuguese funding
agency, FCT -- Fundação para a Ciência e a Tecnologia, within project
POCI-01-0145-FEDER-016718, and by the FCT scholarship grant
number PD/BD/52237/2013.

Rui Abreu is sponsored by the ERDF through the COMPETE 2020 Program and by
National Funds through the Portuguese funding agency FCT with reference
UID/CEC/50021/2019, and within the project FaultLockerRef
(PTDC/CCI-COM/29300/2017).

\balance
\bibliographystyle{IEEEtranN}