# Rigidity phenomena and the statistical properties of group actions on
$\text{CAT}(0)$ cube complexes

Stephen Cantrell and Eduardo Reyes

###### Abstract.

We compare the marked length spectra of some pairs of proper and cocompact
cubical actions of a non-virtually cyclic group on ${\rm CAT}(0)$ cube
complexes. The cubulations are required to be virtually co-special, have the
same sets of convex-cocompact subgroups, and admit a contracting element.
There are many groups for which these conditions are always fulfilled for any
pair of cubulations, including non-elementary cubulable hyperbolic groups,
many cubulable relatively hyperbolic groups, and many right-angled Artin and
Coxeter groups.

For these pairs of cubulations, we study the Manhattan curve associated to
their combinatorial metrics. We prove that this curve is analytic and convex,
and a straight line if and only if the marked length spectra are homothetic.
The same result holds if we consider invariant combinatorial metrics in which
the lengths of the edges are not necessarily one. In addition, for their
standard combinatorial metrics, we prove a large deviation theorem with
shrinking intervals for their marked length spectra. We deduce the same result
for pairs of word metrics on hyperbolic groups.

The main tool is the construction of a finite-state automaton that
simultaneously encodes the marked length spectra of both cubulations in a
coherent way, in analogy with results about (bi)combable functions on
hyperbolic groups by Calegari-Fujiwara [11]. The existence of this automaton
allows us to apply the machinery of thermodynamic formalism for suspension
flows over subshifts of finite type, from which we deduce our results.

##  1\. Introduction

In this work we study rigidity phenomena and the statistical properties of
group actions on ${\rm CAT}(0)$ cube complexes and the methods we use exploit
the interplay between geometric group theory and dynamics. Group actions on
${\rm CAT}(0)$ cube complexes are nowadays a central object of study. Since
the influential work of Sageev [60], we have known that many groups admit
proper and cocompact cubical actions on ${\rm CAT}(0)$ cube complexes (in the
sequel, referred to as _cubulations_), such as small cancellation groups [49,
70], many 3-manifold groups [2, 35, 56, 57, 69], Coxeter groups [50], many
Artin groups [18, 32], random groups at low density [51, 52], 1-relator groups
with torsion [46, 68, 71], hyperbolic free-by-cyclic groups [36, 37], and so
on. In particular, the fundamental groups of (compact) _special cube
complexes_ introduced by Haglund and Wise [39] form a very rich class of
convex-cocompact subgroups of right-angled Artin groups, and they played a key
role in the resolution of the Virtual Haken and Virtual Fibering Conjectures
[1, 71].

In general, when non-empty, the space of geometric actions of a given group on
${\rm CAT}(0)$ cube complexes is quite large. For example, each filling
multicurve on a closed hyperbolic surface is dual to a cubulation of its
fundamental group [60]. Similarly, cubulations for fundamental groups of
cusped hyperbolic 3-manifolds can be obtained from their vast sets of
(relatively) quasiconvex surface subgroups [2, 20, 42]. Moreover, cubulations
can be used to define deformation spaces, such as the classical Culler-
Vogtmann outer space [21] that encodes geometric actions of free groups on
trees. This perspective has been extended to right-angled Artin groups, for
which outer spaces have been constructed using cubulations with some
particular special cube complexes as quotients [7, 19].

Under some reasonable irreducibility assumptions, actions on ${\rm CAT}(0)$
cube complexes are _marked length-spectrum rigid_ [3, 4]. More precisely, let
$\mathcal{X}$ be a cubulation of a group $\Gamma$ and let ${\bf conj}={\bf
conj}(\Gamma)$ denote the set of conjugacy classes of $\Gamma$. The _(stable)
translation length_ of this action is the function $\ell_{\mathcal{X}}:{\bf
conj}\rightarrow{\mathbb{R}}$ given by

$\ell_{\mathcal{X}}[g]=\lim_{n\to\infty}{\frac{d_{\mathcal{X}}(g^{n}x,x)}{n}},$

where $d_{\mathcal{X}}$ denotes the combinatorial metric on the 1-skeleton of
$\mathcal{X}$ and the limit above is independent of the representative
$g\in[g]$ and the vertex $x\in\mathcal{X}$.

For two cubulations $\mathcal{X},\mathcal{X}_{\ast}$ of $\Gamma$ on ${\rm
CAT}(0)$, marked length-spectrum rigidity states that the equality of
translation length functions $\ell_{\mathcal{X}}=\ell_{\mathcal{X}_{\ast}}$
implies the existence of a $\Gamma$-equivariant cubical isometry from
$\mathcal{X}$ onto $\mathcal{X}_{\ast}$. Since in general the translation
length functions $\ell_{\mathcal{X}}$ and $\ell_{\mathcal{X}_{\ast}}$ will not
coincide, it is natural to ask about the behavior of
$\ell_{\mathcal{X}_{\ast}}[g]$ when $\ell_{\mathcal{X}}[g]$ is large. The goal
of this paper is to address this question for “compatible” pairs of virtually
co-special cubulations i.e., those having quotients with a special cube
complex as a finite cover. Such compatibility is described in Definition 5.1,
and is guaranteed for any group in the following class.

######  Definition 1.1.

Let $\mathfrak{G}$ be the class of non-virtually cyclic groups $\Gamma$
satisfying the following:

  1. (1)

$\Gamma$ admits a proper, cocompact and virtually co-special action on a ${\rm
CAT}(0)$ cube complex.

  2. (2)

The class of convex-cocompact subgroups of $\Gamma$ is the same with respect
to any proper and cocompact action on a ${\rm CAT}(0)$ cube complex.

  3. (3)

Some (equivalently, any) proper and cocompact action of $\Gamma$ on a ${\rm
CAT}(0)$ cube complex has a contracting element.

By Agol’s theorem [1, Thm. 1.1] and the characterization of convex-cocompact
subgroups in terms of quasiconvexity [39, Prop. 7.2], we see that every
cubulable non-elementary hyperbolic group belongs to $\mathfrak{G}$. Moreover,
the class $\mathfrak{G}$ is closed under relative hyperbolicity, in the sense
that a cubulable relatively hyperbolic group belongs to $\mathfrak{G}$ as long
as its peripheral subgroups belong to $\mathfrak{G}$. In particular, any
$C^{\prime}(1/6)$ small cancellation quotient of the free product of finitely
many groups in $\mathfrak{G}$ belongs to $\mathfrak{G}$ [49]. However, this
class is much larger since it contains some infinite families of right-angled
Artin and Coxeter groups, most of them not being relatively hyperbolic with
respect to any collection of proper subgroups. For instance, any right-angled
Artin group with finite outer automorphism group belongs to $\mathfrak{G}$.
See Proposition 5.2 for the precise statement.

###  1.1. Manhattan curves

Let $\mathcal{X},\mathcal{X}_{\ast}$ be two cubulations of the group $\Gamma$.
We endow these cubulations with $\Gamma$-invariant orthotope structures
$\mathfrak{w},\mathfrak{w}_{\ast}$ respectively, consisting of (non-
necessarily integer) positive lengths assigned to the hyperplanes which are
invariant under the action of $\Gamma$. This induces isometric actions of
$\Gamma$ on the cuboid complexes
$\mathcal{X}^{\mathfrak{w}}=(\mathcal{X},\mathfrak{w})$ and
$\mathcal{X}_{\ast}^{\mathfrak{w}_{\ast}}=(\mathcal{X}_{\ast},\mathfrak{w}_{\ast})$,
see Section 2.2 for further details. The _Manhattan curve_ for the pair
$(\mathcal{X}^{\mathfrak{w}},\mathcal{X}^{\mathfrak{w}_{\ast}}_{\ast})$ is the
boundary of the convex set

$\mathcal{C}_{\mathcal{X}^{\mathfrak{w}_{\ast}}_{\ast}/\mathcal{X}^{\mathfrak{w}}}:=\left\\{(a,b)\in{\mathbb{R}}^{2}:\sum_{[g]\in{\bf
conj}(\Gamma)}e^{-a\ell^{\mathfrak{w}}_{\mathcal{X}}[g]-b\ell^{\mathfrak{w}_{\ast}}_{\mathcal{X}_{\ast}}[g]}<\infty\right\\},$

where $\ell_{\mathcal{X}}^{\mathfrak{w}}$ and
$\ell^{\mathfrak{w}_{\ast}}_{\mathcal{X}_{\ast}}$ are the respective
translation length functions of the actions of $\Gamma$ on the 1-skeleta of
$\mathcal{X}^{\mathfrak{w}}$ and $\mathcal{X}_{\ast}^{\mathfrak{w}_{\ast}}$.
We can parameterize this curve as
$s\mapsto\theta_{\mathcal{X}^{\mathfrak{w}_{\ast}}_{\ast}/{\mathcal{X}^{\mathfrak{w}}}}(s)$,
where for $s\in{\mathbb{R}}$,
$\theta_{\mathcal{X}^{\mathfrak{w}_{\ast}}_{\ast}/{\mathcal{X}^{\mathfrak{w}}}}(s)$
is the abscissa of convergence of the series

$t\mapsto\sum_{[g]\in{\bf
conj}(\Gamma)}e^{-t\ell^{\mathfrak{w}}_{\mathcal{X}}[g]-s\ell^{\mathfrak{w}_{\ast}}_{\mathcal{X}_{\ast}}[g]}.$

By abuse of notation, we also call the parametrization
$\theta_{\mathcal{X}^{\mathfrak{w}_{\ast}}_{\ast}/\mathcal{X}^{\mathfrak{w}}}$
the Manhattan curve of
$(\mathcal{X}^{\mathfrak{w}},\mathcal{X}^{\mathfrak{w}_{\ast}}_{\ast})$.

Manhattan curves are useful tools for studying pairs of actions and are
related to rigidity results, as well as recovering asymptotic invariants. They
were introduced by Burger [10] for pairs of convex-cocompact representations
of a group on rank 1 symmetric spaces, and later Sharp [66] proved that they
are analytic for pairs of cocompact Fuchsian representations. Sharp also
extended these results for pairs of points in the outer space of a free group
[64, 65]. Recently, Manhattan curves have been studied for pairs of cusped
Fuchsian representations [44, 45], pairs of cusped quasi-Fuchsian
representations [5], comparing quasi-Fuchsian representations with negatively
curved metrics on surfaces [43], pairs of cusped Hitchin representations [6],
and pairs of geometric actions on hyperbolic groups [15, 16].

Our first main theorem fits into the aforementioned results, and to the
authors’ knowledge, is the first to address the analyticity of Manhattan
curves outside the scope of relatively hyperbolic groups or representation
theory.

######  Theorem 1.2.

Let $\Gamma$ be a group in the class $\mathfrak{G}$ and let it act properly
and cocompactly on the cuboid complexes
$\mathcal{X}^{\mathfrak{w}}=(\mathcal{X},\mathfrak{w})$ and
$\mathcal{X}_{\ast}^{\mathfrak{w}_{\ast}}=(\mathcal{X}_{\ast},\mathfrak{w}_{\ast})$.
Then the Manhattan curve
$\theta_{\mathcal{X}^{\mathfrak{w}_{\ast}}_{\ast}/\mathcal{X}^{\mathfrak{w}}}:{\mathbb{R}}\rightarrow{\mathbb{R}}$
is convex, decreasing, and analytic. In addition, the following limit exists
and equals
$-\theta^{\prime}_{\mathcal{X}^{\mathfrak{w}_{\ast}}_{\ast}/\mathcal{X}^{\mathfrak{w}}}(0)$:

$\tau(\mathcal{X}^{\mathfrak{w}_{\ast}}_{\ast}/\mathcal{X}^{\mathfrak{w}}):=\lim_{T\to\infty}\frac{1}{\\#\\{[g]\in{\bf
conj}\colon\ell^{\mathfrak{w}}_{\mathcal{X}}[g]<T\\}}\sum_{\ell^{\mathfrak{w}}_{\mathcal{X}}[g]<T}\frac{\ell^{\mathfrak{w}_{\ast}}_{\mathcal{X}_{\ast}}[g]}{T}.$

Moreover, we always have

$\tau(\mathcal{X}^{\mathfrak{w}_{\ast}}_{\ast}/\mathcal{X}^{\mathfrak{w}})\geq
v_{\mathcal{X}^{\mathfrak{w}}}/v_{\mathcal{X}^{\mathfrak{w}_{\ast}}_{\ast}},$

for
$v_{\mathcal{X}^{\mathfrak{w}}},v_{\mathcal{X}^{\mathfrak{w}_{\ast}}_{\ast}}$
the corresponding exponential growth rates, and the following are equivalent:

  1. (1)

$\theta_{\mathcal{X}^{\mathfrak{w}_{\ast}}_{\ast}/\mathcal{X}^{\mathfrak{w}}}$
is a straight line;

  2. (2)

there exists $\Lambda>0$ such that
$\ell^{\mathfrak{w}}_{\mathcal{X}}[g]=\Lambda\ell^{\mathfrak{w}_{\ast}}_{\mathcal{X}_{\ast}}[g]$
for all $[g]\in{\bf conj}(\Gamma)$; and,

  3. (3)

$\tau(\mathcal{X}^{\mathfrak{w}_{\ast}}_{\ast}/\mathcal{X}^{\mathfrak{w}})=v_{\mathcal{X}^{\mathfrak{w}}}/v_{\mathcal{X}^{\mathfrak{w}_{\ast}}_{\ast}}$.

######  Remark 1.3.

In the result above, the group $\Gamma$ does not have to belong to
$\mathfrak{G}$ as long as the triple $(\Gamma,\mathcal{X},\mathcal{X}_{\ast})$
belongs to the class $\mathfrak{X}$ in Definition 5.1. In particular, the
action on $\mathcal{X}_{\ast}$ does not have to be proper. See Theorem 6.1 for
the more general statement.

The main tool in the proof of Theorems 1.2 and 6.1 is the construction of a
finite-state automaton that simultaneously encodes translation lengths for the
actions on both $\mathcal{X}$ and $\mathcal{X}_{\ast}$. This is done in
Proposition 5.9, where for a convenient finite index subgroup
$\overline{\Gamma}<\Gamma$ such that the quotient
$\overline{\mathcal{X}}=\overline{\Gamma}\backslash\mathcal{X}$ is a special
cube complex, we construct a finite state automaton
$\mathcal{A}_{\mathcal{X}}$ with corresponding directed graph
$\mathcal{G}_{\mathcal{X}}$ satisfying the following:

  * •

The labeling map assigns to any edge of $\mathcal{G}_{\mathcal{X}}$ an
oriented hyperplane of $\overline{\mathcal{X}}$.

  * •

There is a base vertex $o\in\mathcal{X}$ such that each admissible path in
$\mathcal{G}_{\mathcal{X}}$ corresponds to a geodesic path in $\mathcal{X}$
starting at $o$. The hyperplanes dual to the edges of this geodesic project in
$\overline{\mathcal{X}}$ to the labels of the corresponding path in
$\mathcal{G}_{\mathcal{X}}$.

  * •

The assignment from the set of admissible paths in $\mathcal{G}_{\mathcal{X}}$
into $\mathcal{X}^{0}$ that sends each path to the endpoint of its geodesic
constructed as above is surjective and uniformly finite-to-one.

  * •

Loops in $\mathcal{G}_{\mathcal{X}}$ correspond to geodesics in $\mathcal{X}$
with endpoints related by an element of $\overline{\Gamma}$, so they induce
conjugacy classes in $\overline{\Gamma}$. The length of any such geodesic is
the $\ell_{\mathcal{X}}$-translation length of the conjugacy class.

  * •

There exist functionals $r_{\mathcal{X}}^{\mathfrak{w}}$ and
$\psi^{\mathfrak{w}_{\ast}}_{\mathcal{X}_{\ast}}$ on the edges of
$\mathcal{G}_{\mathcal{X}}$ such that their sums along the edges of a loop in
$\mathcal{G}_{\mathcal{X}}$ equal the
$\ell^{\mathfrak{w}}_{\mathcal{X}}$-translation length and
$\ell^{\mathfrak{w}_{\ast}}_{\mathcal{X}_{\ast}}$-translation length of the
induced conjugacy class, respectively.

We use the automaton $\mathcal{A}_{\mathcal{X}}$ and the functional
$r_{\mathcal{X}}^{\mathfrak{w}}$ to define a suspension flow over a subshift
of finite type, whose periodic orbits induce conjugacy classes in ${\bf
conj}(\overline{\Gamma})$ with periods corresponding to
$\ell^{\mathfrak{w}}_{\mathcal{X}}$-translation lengths. The functional
$\psi^{\mathfrak{w}_{\ast}}_{\mathcal{X}_{\ast}}$ induces a potential $\Phi$
on this suspension, whose Birkhoff sums correspond to
$\ell^{\mathfrak{w}_{\ast}}_{\mathcal{X}_{\ast}}$-translation lengths. The
existence of a contracting element allows us to describe the Manhattan curve
$\theta_{\mathcal{X}^{\mathfrak{w}_{\ast}}_{\ast}/\mathcal{X}^{\mathfrak{w}}}$
in terms of pressure functions associated to $\Phi$ (see Proposition 6.8), and
the theorems then follow by standard results in thermodynamic formalism.

###  1.2. Large deviations

For a pair $\mathcal{X},\mathcal{X}_{\ast}$ of cubulations of a group
$\Gamma\in\mathfrak{G}$, we also study large deviations for their translation
lengths. That is, we estimate the number of conjugacy classes $[g]$ for which

$\left|\frac{\ell_{\mathcal{X}_{\ast}}[g]}{\ell_{\mathcal{X}}[g]}-\eta\right|<\epsilon\
\text{ for some $\eta\in{\mathbb{R}}$ and a small $\epsilon>0$}.$ (1.1)

A more difficult question is to study the set of conjugacy classes $[g]$ such
that

$|\ell_{\mathcal{X}_{\ast}}[g]-\eta\ell_{\mathcal{X}}[g]|<\epsilon\ \text{ for
some $\eta\in{\mathbb{R}}$ and a small $\epsilon>0$}.$ (1.2)

Indeed, this is more delicate than the corresponding quotient question above
as (when $\ell_{\mathcal{X}}[g]$ is bounded away from $0$) (1.2) implies (1.1)
but not vice versa.

Despite this latter question being significantly harder, there are previous
works that tackle this problem in other settings. For example, let $\Sigma$ be
a closed surface with negative Euler characteristic and fundamental group
$\Gamma$, and suppose that $\mathfrak{g}$ and $\mathfrak{g}_{\ast}$ are two
hyperbolic metrics on $\Sigma$. These metrics induce isometric actions of
$\Gamma$ on $\widetilde{\Sigma}$ with translation length functions
$\ell_{\mathfrak{g}}$ and $\ell_{\mathfrak{g}_{\ast}}$. A result of Schwartz
and Sharp [63] states that there is an interval
$(\alpha,\beta)\subset{\mathbb{R}}$ and constants $C,\lambda>0$ such that any
$\eta\in(\alpha,\beta)$ satisfies

$\\#\left\\{[g]\in{\bf
conj}(\Gamma):\ell_{\mathfrak{g}}[g]<T:|\ell_{\mathfrak{g}_{\ast}}[g]-\eta\ell_{\mathfrak{g}}[g]|<\epsilon\right\\}\sim\frac{Ce^{\lambda
T}}{T^{3/2}}$

as $T\to\infty$ for any fixed $\epsilon>0$ (here ‘$\sim$’ represents that the
quotients of the two quantities converge to $1$ as $T\to\infty$). Similar
results are known to hold for surfaces of variable negative curvature by
Dal’bo [24], for Hitchin representations by Dai and Martone [23], for Green
metrics by Cantrell [13] and for some pairs of points in outer space by Sharp
[64]. These asymptotics are often referred to as correlation results and to
prove them thermodynamic formalism is usually employed. To apply thermodynamic
formalism one needs to know that the length spectra of the two considered
metrics are not _rationally related_. That is, if $\ell_{1}$, $\ell_{2}$ are
the length spectra that we want to compare then we would need to know that
there do not exist non-zero $a,b\in{\mathbb{R}}$ with
$a\ell_{1}[g]+b\ell_{2}[g]\in{\mathbb{Z}}$ for all $[g]\in{\bf conj}(\Gamma).$
This property is vital as it implies bounds on the operator norm of families
of transfer operators which are then used in the proof of the correlation
asymptotic.

On the other hand, the length spectra of a pair of cubical actions on ${\rm
CAT}(0)$ cube complexes are always rationally related. Indeed, after possibly
performing one cubical barycentric subdivision, every cubical isometry of a
${\rm CAT}(0)$ cube complex either fixes a vertex or preserves a bi-infinite
geodesic on which the isometry acts by non-trivial translations [38]. In
particular, the translation length function associated to any of these actions
has image belonging to $\frac{1}{2}{\mathbb{Z}}$.

However, by means of the automaton $\mathcal{A}_{\mathcal{X}}$, we are still
able to estimate the number of conjugacy classes satisfying (1.2). As a
consequence of Theorem 3.1 in the setting of subshifts of finite type, we can
prove the following theorem.

######  Theorem 1.4.

Let $\Gamma$ be a group in the class $\mathfrak{G}$ and let it act properly
and cocompactly on the ${\rm CAT}(0)$ cube complexes $\mathcal{X}$ and
$\mathcal{X}_{\ast}$. Let ${\bf conj}^{\prime}\subset{\bf conj}$ be the set of
non-torsion conjugacy classes and consider the dilations

${\rm Dil}(\mathcal{X}_{\ast},\mathcal{X})=\sup_{[g]\in{\bf
conj}^{\prime}}\frac{\ell_{\mathcal{X}_{\ast}}[g]}{\ell_{\mathcal{X}}[g]}\
\text{ and }\ {\rm Dil}(\mathcal{X},\mathcal{X}_{\ast})^{-1}=\inf_{[g]\in{\bf
conj}^{\prime}}\frac{\ell_{\mathcal{X}_{\ast}}[g]}{\ell_{\mathcal{X}}[g].}$

Then there exists an analytic function

$\mathcal{I}:[{\rm Dil}(\mathcal{X},\mathcal{X}_{\ast})^{-1},{\rm
Dil}(\mathcal{X}_{\ast},\mathcal{X})]\rightarrow{\mathbb{R}}$

and $C>0$ such that for any $\eta\in({\rm
Dil}(\mathcal{X},\mathcal{X}_{\ast})^{-1},{\rm
Dil}(\mathcal{X}_{\ast},\mathcal{X}))$ we have

$0<\limsup_{T\to\infty}\frac{1}{T}\log\left(\\#\left\\{[g]\in{\bf
conj}:\ell_{\mathcal{X}}[g]<T,|\ell_{\mathcal{X}_{\ast}}[g]-\eta\ell_{\mathcal{X}}[g]|<\frac{C}{T}\right\\}\right)=\mathcal{I}(\eta)\leq
v_{\mathcal{X}}.$ (1.3)

Furthermore, we have equality in the above inequality if and only if
$\eta=\tau(\mathcal{X}_{\ast}/\mathcal{X})$.

######  Remark 1.5.

As in Theorem 1.2, the conclusion above still holds for triples
$(\Gamma,\mathcal{X},\mathcal{X}_{\ast})$ in the class $\mathfrak{X}$, see
Theorem 6.2. However, for our arguments (particularly Theorem 3.1) it is
crucial that the translation length functions belong to a lattice in
${\mathbb{R}}$. We still expect Theorem 6.2 to hold for arbitrary cuboid
complexes $\mathcal{X}^{\mathfrak{w}}$ and
$\mathcal{X}^{\mathfrak{w}_{\ast}}_{\ast}$, but we will not pursue this in
this work.

As an application of Theorem 1.4 we deduce large deviations with shrinking for
the intersection of curves on hyperbolic surfaces. Let $\Sigma$ be a closed
orientable surface of negative Euler characteristic and fundamental group
$\Gamma$. If $\alpha,\beta$ are immersed closed oriented curves in $\Sigma$,
then the _(geometric) intersection number_ is the minimal number
$i_{\Sigma}(\alpha,\beta)$ of intersections of closed curves in the free
homotopy classes of $\alpha$ and $\beta$. The function $i_{\Sigma}$ can be
extended by bilinearity to _weighted multicurves_ , which are finite sums of
the form $\sum_{j}{\lambda_{j}\alpha_{j}}$ with $\alpha_{j}$ immersed oriented
closed curves in $\Sigma$ and a set $(\lambda_{j}\geq 0)_{i}$ of _weights_.
Any non-trivial element in ${\bf conj}(\Gamma)$ is represented by a unique
free homotopy class of immersed oriented closed curves, so we can talk of the
intersection number between a weighted multicurve in $\Sigma$ and a conjugacy
class in ${\bf conj}(\Gamma)$. For more details about the intersection number,
see [28].

A generating set $S$ for $\Gamma$ is _simple_ if there exists a point
$p\in\Sigma$ such that elements of $S\subset\Gamma=\pi_{1}(\Sigma,p)$ can be
represented by simple loops that are pairwise non-homotopic and disjoint
except at the base point $p$. For example, the generating set for the standard
presentation

$\Gamma=\left<a_{1},b_{1},\dots,a_{g},b_{g}\colon[a_{1},b_{1}]\cdots[a_{g},b_{g}]\right>$

is simple. In [27, Thm. 1.2], Erlandsson proved that the translation length
function $\ell_{S}$ of the word metric of a simple generating set $S$ can be
recovered by pairing in the intersection number against a carefully chosen
weighted multicurve $\alpha_{S}$ with weights in $\frac{1}{2}\mathbb{Z}$. Up
to scaling, this translation length function can also be recovered by looking
at the ${\rm CAT}(0)$ cube complex dual to the multicurve $\alpha_{S}$.
Therefore, Theorem 6.2 applies and we obtain the following.

######  Corollary 1.6.

Let $\Gamma$ be the fundamental group of the closed orientable hyperbolic
surface $\Sigma$ and consider a simple generating set $S$ of exponential
growth rate $v_{S}$. Let $\alpha$ be a non-trivial weighted multicurve on
$\Sigma$ with integer weights, and define

$a_{\inf}:=\inf_{[g]\in{\bf
conj}^{\prime}}\frac{i_{\Sigma}(\alpha,[g])}{\ell_{S}[g]}\ \text{ and }\
a_{\sup}:=\sup_{[g]\in{\bf
conj}^{\prime}}\frac{i_{\Sigma}(\alpha,[g])}{\ell_{S}[g]}.$

Then there exists an analytic convex function
$\mathcal{I}:[a_{\inf},a_{\sup}]\rightarrow{\mathbb{R}}$ and $C>0$ such that
for any $\eta\in(a_{\inf},a_{\sup})$ we have

$0<\limsup_{T\to\infty}\frac{1}{T}\log\left(\\#\left\\{[g]\in{\bf
conj}:\ell_{S}[g]<T,|i_{\Sigma}(\alpha,[g])-\eta\ell_{S}[g]|<\frac{C}{T}\right\\}\right)=\mathcal{I}(\eta)\leq
v_{S}.$

###  1.3. Word metrics on hyperbolic groups

Since the proof of Theorem 1.4 relies on Theorem 3.1 (a purely dynamical
statement), the existence of the automaton $\mathcal{A}_{\mathcal{X}}$
encoding both actions on $\mathcal{X}$ and $\mathcal{X}_{\ast}$, and the
arithmeticity of the translation length functions, we can deduce large
deviation with shrinking for any pair of group actions fulfilling similar
conditions. That is the case of word metrics on hyperbolic groups, and in
fact, this was the author’s main motivation at the beginning of this project.

Let $\Gamma$ be a non-elementary hyperbolic group and let
$S,S_{\ast}\subset\Gamma$ be finite generating sets with corresponding word
metrics $d_{S},d_{S_{\ast}}$. By Cannon’s theorem [12], for a total order on
$S$, the language of lexicographically first geodesics in $\Gamma$ is regular,
so it is parametrized by a finite-state automaton. As a consequence of [11,
Lem. 3.8], Calegari and Fujiwara are able to modify this automaton (without
modifying the parameterized language), and find an integer functional on the
edges of the graph of the automaton so that its sum over paths recovers the
$S_{\ast}$-word length for the corresponding element in $\Gamma$ (this was our
main motivation to construct the automaton $\mathcal{A}_{\mathcal{X}}$ in
Proposition 5.9).

By studying the subshift of finite type associated to this automaton, Cantrell
and Tanaka [16, 15] deduced analyticity of the Manhattan curve for
$S,S_{\ast}$ as well as a large deviation principle. More precisely, let
$\ell_{S},\ell_{S_{\ast}}$ be the corresponding translation length functions
and consider the dilations

${\rm Dil}(S_{\ast},S)=\sup_{[g]\in{\bf
conj}^{\prime}}\frac{\ell_{S_{\ast}}[g]}{\ell_{S}[g]}\ \text{ and }\ {\rm
Dil}(S,S_{\ast})^{-1}=\inf_{[g]\in{\bf
conj}^{\prime}}\frac{\ell_{S_{\ast}}[g]}{\ell_{S}[g].}$

Then there exists a real analytic, concave function $\mathcal{I}:[{\rm
Dil}(S,S_{\ast})^{-1},{\rm Dil}(S_{\ast},S)]\to{\mathbb{R}}_{>0}$ such that
for $\eta\in({\rm Dil}(S,S_{\ast})^{-1},{\rm Dil}(S_{\ast},S))$ we have

$\lim_{\epsilon\to
0^{+}}\limsup_{n\to\infty}\frac{1}{T}\log\left(\\#\left\\{[g]\in{\bf
conj}(\Gamma):\ell_{S}[g]<T:\left|\frac{\ell_{S_{\ast}}[g]}{\ell_{S}[g]}-\eta\right|<\epsilon\right\\}\right)=\mathcal{I}(\eta).$

By applying Theorem 3.1 to this subshift, we can improve this result and
obtain a large deviation theorem with shrinking.

######  Theorem 1.7.

Let $\Gamma$ be a non-elementary hyperbolic group and consider two finite
generating sets $S,S_{\ast}$ for $\Gamma$ with exponential growth rates
$v_{S},v_{S_{\ast}}$. Then there exists $C>0$ such that for any $\eta\in({\rm
Dil}(S,S_{\ast})^{-1},{\rm Dil}(S_{\ast},S))$ we have

$0<\limsup_{T\to\infty}\frac{1}{T}\log\left(\\#\left\\{[g]\in{\bf
conj}:\ell_{S}[g]<T,|\ell_{S_{\ast}}[g]-\eta\ell_{S}[g]|<\frac{C}{T}\right\\}\right)=\mathcal{I}(\eta)\leq
v_{S}.$

Furthermore, we have equality in the above inequality if and only if

$\eta=\tau(S_{\ast}/S):=\lim_{T\to\infty}\frac{1}{\\#\\{[g]\in{\bf
conj}\colon\ell_{S}[g]<T\\}}\sum_{\ell_{S}[g]<T}\frac{\ell_{S_{\ast}}[g]}{T}.$

This result implies that, after scaling a pair of word metrics by their
exponential growth rates, there is always an exponentially growing set for
which their translation lengths are close, i.e. for any $\epsilon>0$

$0<\limsup_{T\to\infty}\frac{1}{T}\log\\#\left\\{[g]\in{\bf
conj}:\ell_{S}[g]<T,|v_{S}\ell_{S}[g]-v_{S_{\ast}}\ell_{S_{\ast}}[g]|<\epsilon\right\\}\leq
v_{S}.$ (1.4)

This extends the recent work [14, Thm. 4.1] where the authors proved a
correlation result for pairs of word metrics under an additional rationality
assumption on the exponential growth rates. This result also answers a
question raised by the authors in [14, Rmk. 4.3]. We deduce the following
corollary.

######  Corollary 1.8.

Let $\Gamma$ be a non-elementary hyperbolic group, and let $S$ and $S_{\ast}$
be two finite generating sets on $\Gamma$. Then there exists $C>0$ such that
for any $\eta\in[{\rm Dil}(S,S_{\ast})^{-1},{\rm Dil}(S_{\ast},S)]$ we can
find an infinite sequence $(g_{n})_{n\geq 1}\subset\Gamma$ such that

$\left|\frac{\ell_{S_{\ast}}[g_{n}]}{\ell_{S}[g_{n}]}-\eta\right|\leq\frac{C}{|g_{n}|_{S}^{2}}.$

If $\eta\in[{\rm Dil}(S,S_{\ast})^{-1},{\rm Dil}(S_{\ast},S)]$ is rational
then there exists $g\in\Gamma$ such that

$\frac{\ell_{S_{\ast}}[g]}{\ell_{S}[g]}=\eta.$

In Section 4.1 we present an example for a pair of word metrics on a free
group. In particular, we compute the limit supremum in (1.4) for this pair of
word metrics.

### Organization

The organization of the paper is as follows. In Section 2 we cover preliminary
material about Manhattan curves, ${\rm CAT}(0)$ cube complexes and cubulable
groups, symbolic dynamics and suspension flows, and finite-state automata.

In Section 3 we prove Theorem 3.1, a large deviation result with shrinking
intervals for lattice potentials on mixing subshifts of finite type that are
constant on 2 cylinders. We apply this theorem to pairs of word metrics on
hyperbolic groups in Section in Section 4 and prove Theorem 1.7.

In Section 5 we prove Proposition 5.2 that describes large classes of groups
included in $\mathfrak{G}$. There we also prove Proposition 5.9, in which we
construct a finite-state automaton for pairs of compatible actions on ${\rm
CAT}(0)$ cube complexes. We use this automaton in Section 6 to prove Theorems
6.1 and 6.2, from which we deduce Theorems 1.2 and 1.4.

Finally, in the appendix we prove a Proposition A.1, a criterion for convex-
cocompactness of subgroups of cubulable relatively hyperbolic groups, which
may be of independent interest.

### Acknowledgements

Both authors are grateful to Richard Sharp for his comments and suggestions on
a preliminary version of this paper. The second author would like to thank the
Max Planck Institut für Mathematik for its hospitality and financial support.

##  2\. Preliminaries

###  2.1. Isometric group actions

Let $\Gamma$ be a finitely generated group acting by isometries on the metric
space $(X,d_{X})$ and let $x\in X$ be an arbitrary base point. The _(stable)
translation length_ of this action is the function $\ell_{X}:{\bf
conj}\rightarrow{\mathbb{R}}$ given by

$\ell_{X}[g]=\lim_{n\to\infty}{\frac{d_{X}(g^{n}x,x)}{n}}\ \text{ for
}g\in[g]\text{ in }{\bf conj}.$

The _exponential growth rate_ of this action is the quantity

$v_{X}:=\limsup_{T\to\infty}\frac{\log\\#\\{g\in\Gamma\colon
d_{X}(gx,x)<T\\}}{T}\in[0,+\infty].$

As for the translation lengths, the exponential growth rate is independent of
the chosen base point $x$. If $X$ is geodesic (or more generally roughly
geodesic) and the action of $\Gamma$ on $X$ is proper and cocompact, then
$v_{X}$ is finite. In some cases we can recover the exponential growth rate as
the limit

$v_{X}=v_{X}(\Gamma)=\limsup_{T\to\infty}{\frac{1}{T}\log\\#\mathfrak{C}_{X}(T)},$

where each $T>0$ we denote

$\mathfrak{C}_{X}(T)=\\{[g]\in{\bf conj}\colon\ell_{X}[g]<T\\}.$

This happens for example when $\Gamma$ is hyperbolic and the action on $X$ is
proper and cocompact.

Given two isometric actions of $\Gamma$ on the metric spaces $X$ and
$X_{\ast}$, the _Manhattan curve_ for the pair $(X,X_{\ast})$ is the boundary
of the convex set

$\mathcal{C}_{X_{\ast}/X}:=\left\\{(a,b)\in{\mathbb{R}}^{2}:\sum_{[g]\in{\bf
conj}}e^{-a\ell_{X}[g]-b\ell_{X_{\ast}}[g]}<\infty\right\\},$

assuming it is non-empty. Equivalently, $\mathcal{C}_{X_{\ast}/X}$ is the set
of points $(s,\theta_{X_{\ast}/X}(s))$ where $\theta_{X_{\ast}/{X}}(s)$ is the
abscissa of convergence of the series

$t\mapsto\sum_{[g]\in{\bf conj}}e^{-t\ell_{X}[g]-s\ell_{X_{\ast}}[g]}.$

By abuse of notation, $\theta_{X_{\ast}/X}$ is also called the Manhattan curve
for $(X,X_{\ast})$.

###  2.2. ${\rm CAT}(0)$ cube complexes

For bibliography about ${\rm CAT}(0)$ cube complexes and groups acting on
them, we refer the reader to [8, 59]. A _non-positively curved (NPC) cube
complex_ is a metric polyhedral complex in which all polyhedra are unit-length
Euclidean cubes, and satisfies Gromov’s link condition: the link of each
vertex is a flag complex. If this complex is simply connected we say that it
is a _${\rm CAT}(0)$ cube complex_.

Let $\mathcal{X}$ be an NPC cube complex. Consider the minimal equivalence
relations on the set of edges (resp. oriented edges) of $\mathcal{X}$ such
that the edges $e=\\{v,w\\}$ and $e=\\{v^{\prime},w^{\prime}\\}$ (resp.
oriented edges $v\xrightarrow{e}w$ and
$v^{\prime}\xrightarrow{e^{\prime}}w^{\prime}$) are in the same equivalence
class if $v,w,v^{\prime},w^{\prime}$ span a square in $\mathcal{X}$ (resp.
$v,w,v^{\prime}w^{\prime}$ span a square in $\mathcal{X}$ with $v,v^{\prime}$
adjacent and $w,w^{\prime}$ adjacent). Equivalence classes of these
equivalence relations are called _hyperplanes_ (resp. _oriented hyperplanes_),
and we let $\mathbb{H}(\mathcal{X})$ denote the set of hyperplanes of
$\mathcal{X}$. If the equivalence class of an (oriented) edge $e$ is the
(oriented) hyperplane $\mathfrak{h}$, then we say that $e$ _dual_ to
$\mathfrak{h}$. A hyperplane is _2-sided_ if it corresponds to exactly two
oriented hyperplanes, otherwise it is _1-sided_.

Suppose now that $\mathcal{X}$ is a ${\rm CAT}(0)$ cube complex, in which case
all hyperplanes are 2-sided. A _combinatorial path_ in $\mathcal{X}$ is a
sequence $\gamma=(\gamma_{0},\dots,\gamma_{n})$ of vertices in $\mathcal{X}$
such that $\gamma_{i}$ is adjacent to $\gamma_{i+1}$ for $i=0,\dots,n-1$. In
that case, we say that $\gamma_{0}$ is the initial vertex of $\gamma_{0}$ and
$\gamma_{n}$ is its final vertex. The length of
$\gamma=(\gamma_{0},\dots,\gamma_{n})$ is defined as $n$. This path is often
seen as a continuous path by also considering the edges $e_{i+1}$ joining each
$\gamma_{i}$ with $\gamma_{i+1}$. Such a path is _geodesic_ if no two distinct
edges $e_{i}$ are dual to the same hyperplane. The combinatorial metric on
$\mathcal{X}$ is the graph metric $d_{\mathcal{X}}$ on its 1-skeleton
$\mathcal{X}^{1}$ so that each edge has length 1. It follows that a
combinatorial path is geodesic if an only if it is geodesic for the metric
$d_{\mathcal{X}}$.

A hyperplane $\mathfrak{h}$ in the ${\rm CAT}(0)$ cube complex $\mathcal{X}$
_separates_ two vertices of $\mathcal{X}$ if some (any) combinatorial path
connecting these vertices has an edge dual to $\mathfrak{h}$. It follows that
the combinatorial distance of any two vertices in $\mathcal{X}$ equals the
number of hyperplanes separating them. Also, a hyperplane $\mathfrak{h}$
determines the equivalence relation of “not being separated by $\mathfrak{h}$”
on the set of vertices of $\mathcal{X}$. This equivalence relation has exactly
2 equivalence classes $\\{\mathfrak{h}^{-},\mathfrak{h}^{+}\\}$, which are the
_halfspaces_ determined by $\mathfrak{h}$. A subcomplex of $\mathcal{X}$ is
_convex_ if its vertex set is the intersection of halfspaces. Equivalently,
$Z\subset\mathcal{X}$ is convex if any combinatorial geodesic joining points
in $Z^{0}$ is contained in $Z^{0}$.

An _orthotope structure_ on the ${\rm CAT}(0)$ cube complex $\mathcal{X}$ is a
function

$\mathfrak{w}:\mathbb{H}(\mathcal{X})\rightarrow{\mathbb{R}}_{>0},$

and the pair $\mathcal{X}^{\mathfrak{w}}=(\mathcal{X},\mathfrak{w})$ is called
a _cuboid complex_. An orthotope structure induces a metric
$d_{\mathcal{X}}^{\mathfrak{w}}$ on $\mathcal{X}^{1}$ by declaring each edge
$e$ to have length $\mathfrak{w}(\mathfrak{h})$ for $\mathfrak{h}$ the
hyperplane dual to $e$. In this way, for any two vertices
$x,y\in\mathcal{X}^{0}$ we have

$d_{\mathcal{X}}^{\mathfrak{w}}(x,y)=\sum_{\mathfrak{h}\in\mathbb{H}(x|y)}{\mathfrak{w}(\mathfrak{h})},$

where $\mathbb{H}(x|y)\subset\mathbb{H}(\mathcal{X})$ is the collection of
hyperplanes separating $x$ and $y$. Note that if $\mathfrak{w}$ is the
constant function equal to 1, then $d_{\mathcal{X}}^{\mathfrak{w}}$ is just
the standard combinatorial metric $d_{\mathcal{X}}$.

######  Remark 2.1.

It is clear that a geodesic in $\mathcal{X}$ with respect to $d_{\mathcal{X}}$
is also geodesic with respect to $d_{\mathcal{X}}^{\mathfrak{w}}$ for any
orthotope structure $\mathfrak{w}$.

Now let $\Gamma$ be a group acting on the ${\rm CAT}(0)$ cube complex
$\mathcal{X}$. We always assume that the action is cubical, and hence by
isometries on $\mathcal{X}^{1}$ with the combinatorial metric
$d_{\mathcal{X}}$. Similarly, $\ell_{\mathcal{X}}$ always denotes the stable
translation length of $\Gamma$ with respect to the action on
$(\mathcal{X}^{1},d_{\mathcal{X}})$. If the action of $\Gamma$ is proper and
cocompact, we say that $\mathcal{X}$ is a _cubulation_ of $\Gamma$.

The action of $\Gamma$ on $\mathcal{X}$ induces a natural action on
$\mathbb{H}(\mathcal{X})$. If $\mathfrak{w}$ is a $\Gamma$-invariant orthotope
structure on $\mathcal{X}$ in the sense that
$\mathfrak{w}(\mathfrak{h})=\mathfrak{w}(g\mathfrak{h})$ for all $g\in\Gamma$
and $\mathfrak{h}\in\mathbb{H}(\mathcal{X})$, then we say that $\Gamma$ _acts_
on the cuboid complex $(\mathcal{X},\mathfrak{w})$. In that case the action of
$\Gamma$ on $(\mathcal{X}^{1},d_{\mathcal{X}}^{\mathfrak{w}})$ is also by
isometries. We let $\ell_{\mathcal{X}}^{\mathfrak{w}}$ denote the stable
translation length of $\Gamma$ for its action on
$(\mathcal{X}^{1},d_{\mathcal{X}}^{\mathfrak{w}})$.

By a _hyperplane stabilizer_ we mean a subgroup of $\Gamma$ group elements $g$
such that $g\mathfrak{h}=\mathfrak{h}$ for some fixed hyperplane
$\mathfrak{h}\in\mathbb{H}(\mathcal{X})$. A hyperplane $\mathfrak{h}$ is
_essential_ for the action of $\Gamma$ if for any vertex $x$ of $\mathcal{X}$,
the halfspaces $\mathfrak{h}^{\pm}$ contain elements in the $\Gamma$-orbit of
$x$ arbitrarily far from $\mathfrak{h}^{\mp}$. The action of $\Gamma$ on
$\mathcal{X}$ is _essential_ if every hyperplane is essential.

If $\mathcal{X}$ is a cubulation of $\Gamma$, a subgroup $H<\Gamma$ is called
_convex-cocompact_ with respect to $\mathcal{X}$ if there exists a convex
subcomplex $Z\subset\mathcal{X}$ that is $H$-invariant and so that the action
of $H$ on $Z$ is cocompact. Such a subcomplex $Z$ is called a _convex core_
for $H$. Note that the hyperplane stabilizer of any hyperplane $\mathfrak{h}$
is convex-cocompact since it acts cocompactly on the (convex subcomplex
spanned by the) set of vertices in edges dual to $\mathfrak{h}$ [39, Lem.
13.4].

If $\mathcal{X}$ is a ${\rm CAT}(0)$ cube complex and
$\mathbb{W}\subset\mathbb{H}(\mathcal{X})$ is any collection of hyperplanes,
in [17, Sec. 2.3] Caprace and Sageev introduced the _restriction quotient_ ,
which is a ${\rm CAT}(0)$ cube complex $\mathcal{X}(\mathbb{W})$ equipped with
a surjective cellular map $\phi:\mathcal{X}\rightarrow\mathcal{X}(\mathbb{W})$
satisfying the following: an edge in $\mathcal{X}$ is collapsed to a single
vertex under $\phi$ if and only if it is dual to a hyperplane not in
$\mathbb{W}$. The projection $\phi$ induces a natural bijection between
$\mathbb{W}$ and $\mathbb{H}(\mathcal{X}(\mathbb{W}))$, and hence any
orthotope structure $\mathfrak{w}$ on $\mathcal{X}$ induces an orthotope
structure $\phi_{\ast}(\mathfrak{w})$ on $\mathcal{X}(\mathbb{W})$.

######  Remark 2.2.

Note that (pre)images of convex subcomplexes under restriction quotients
remain convex. In particular, images of geodesic paths remain geodesic,
although some subpaths are allowed to collapse to points. Also note that if
$\Gamma$ acts on $\mathcal{X}$ and $\mathbb{W}$ is $\Gamma$-invariant, then
there is a natural action of $\Gamma$ on $\mathcal{X}(\mathbb{W})$.

A cubulation $\mathcal{X}$ of $\Gamma$ is _co-special_ if the quotient
$\overline{\mathcal{X}}=\Gamma\backslash\mathcal{X}$ is a _special cube
complex_ in the sense of Haglund-Wise [39]. Equivalently, $\mathcal{X}$ is co-
special if $\Gamma$ injects into a right-angled Artin group $A_{G}$ inducing a
$\Gamma$-equivariant isometric embedding of $\mathcal{X}$ into $R_{G}$ as a
convex subcomplex, where $R_{G}$ is the universal cover of the _Salvetti
complex_ $\overline{R}_{G}$ associated to the graph $G$. Among other
properties of special cube complexes, hyperplanes are 2-sided and embedded,
and they do not self-osculate [39, Def. 3.2]. In particular, different
oriented edges with the same initial vertex are dual to different oriented
hyperplanes. The cubulation $\mathcal{X}$ of $\Gamma$ is _virtually co-
special_ if there exists a finite-index subgroup $\overline{\Gamma}<\Gamma$
such that the action of $\overline{\Gamma}$ on $\mathcal{X}$ is co-special.

###  2.3. Symbolic dynamics

In this section we introduce the preliminary material we need from symbolic
dynamics. See [54] for more details. Let $A$ be a $k\times k$ matrix with
entries $0$ or $1$. This matrix is said to be _aperiodic_ if there exists
$N\geq 1$ such that all of the entries of $A^{N}$ are strictly positive. We
say that $A$ is _irreducible_ if for any $i,j\in\\{1,\ldots,k\\}$ there exists
$n\geq 1$ such that $A_{i,j}^{n}$ is strictly positive.

The (one-sided) _subshift of finite type_ $\Sigma_{A}$ associated to $A$ is
the set of infinite sequences

$\Sigma_{A}=\left\\{(x_{n})_{n=0}^{\infty}:x_{j}\in\\{1,\ldots,k\\}\text{ and
}A_{x_{j},x_{j+1}}=1\text{ for all }j\geq 0\right\\}.$

These infinite sequences can be seen as infinite paths in a directed graph
$\mathcal{G}_{A}$ with vertices labelled $1,\ldots,k$ and a directed edge from
vertex $i$ to $j$ if and only if $A_{i,j}=1$. We will therefore refer to the
numbers $1,\ldots,k$ as the _states_ of $\Sigma_{A}$. We equip $\Sigma_{A}$
with the _shift map_ $\sigma:\Sigma_{A}\to\Sigma_{A}$ defined by

$\sigma((x_{n})_{n=0}^{\infty})=(x_{n+1})_{n=0}^{\infty}$

to obtain a dynamical system $(\Sigma_{A},\sigma)$.

Consider a finite ordered string $x_{0},\ldots,x_{m-1}\in\\{1,\ldots,k\\}$
where $A_{x_{j},x_{j+1}}=1$ for each $j=0,\ldots,m-2$. The _cylinder set_
associated to this string is the subset of $\Sigma_{A}$ given by

$[x_{0},\ldots,x_{m-1}]:=\left\\{(y_{n})_{n=0}^{\infty}\in\Sigma_{A}:y_{j}=x_{j}\text{
for }j=0,\ldots,m-1\right\\}.$

We endow $\Sigma_{A}$ with a topology by declaring the set of all cylinder
sets to be an open basis.

The system $(\Sigma_{A},\sigma)$ is said to be _mixing_ if for any two open
sets $U,V\subset\Sigma_{A}$ there is $N\geq 1$ such that $\sigma^{n}(U)\cap
V\neq\emptyset$ for all $n\geq N$. We say that $(\Sigma_{A},\sigma)$ is
_transitive_ if for any two open sets $U,V\subset\Sigma_{A}$ there exists
$n\geq 1$ such that $\sigma^{n}(U)\cap V\neq\emptyset.$ We have that
$(\Sigma_{A},\sigma)$ is mixing if and only if $A$ aperiodic and
$(\Sigma_{A},\sigma)$ is transitive if and only if $A$ is irreducible. We will
often suppress the dependence of $A$ in the notation for a subshift and will
write $(\Sigma,\sigma)$.

Throughout the rest of the section $(\Sigma,\sigma)$ will be a mixing subshift
of finite type, and consider a function $\psi:\Sigma\to{\mathbb{R}}$. We say
that $\psi$ is _constant on $2$ cylinders_ if $\psi$ is constant on each set
of the form $[x_{0},x_{1}]$ where $x_{0},x_{1}\in\\{1,\ldots,k\\}$ and
$A_{x_{0},x_{1}}=1$. For each $n\geq 1$ the $n$th _Birkhoff sum_ of $\psi$ is
the function

$\psi^{n}:\Sigma\to{\mathbb{R}}\ \text{ such that }\
\psi^{n}(x):=\psi(x)+\psi(\sigma(x))+\cdots+\psi(\sigma^{n-1}(x)).$

A point $x\in\Sigma$ is said to be _periodic_ if $\sigma^{n}(x)=x$ for some
$n\geq 1$. Such an $n$ is called a _period_ of $x$ and it is often denoted by
$|x|$. Note that a periodic point has infinitely many periods, and in general
we are not writing $|x|$ for the least period of $x$.

Two functions $\psi,\varphi:\Sigma\to{\mathbb{R}}$, which we are assuming to
be constant on $2$ cylinders, are said to be _cohomologous_ if there exists a
continuous function $u:\Sigma\to{\mathbb{R}}$ such that
$\psi(x)=\varphi(x)+u(\sigma(x))-u(x)$ for all $x\in\Sigma$. By Livsic’s
Theorem [54], $\psi$ and $\varphi$ are cohomologous if and only if
$\psi^{n}(x)=\varphi^{n}(x)$ whenever $\sigma^{n}(x)=x.$

The variational principle states that there is a unique $\sigma$-invariant
Borel probability measure on $(\Sigma,\sigma)$ that achieves the supremum

$\text{P}(\psi):=\sup_{\mu\in\mathcal{M}_{\sigma}}\left\\{h_{\mu}(\sigma)+\int\psi\
d\mu\right\\},$

where $\mathcal{M}_{\sigma}$ is the collection of all $\sigma$-invariant Borel
probability measures on $\Sigma$ and $h_{\mu}(\sigma)$ denotes the _(metric)
entropy_ of $\sigma$ with respect to the measure $\mu$. The quantity
$\text{P}(\psi)$ is referred to as the pressure of $\psi$ and the measure
attaining the supremum is called the equilibrium state of $\psi$. When $\psi$
is a constant function, the measure achieving the supremum for the pressure of
$\psi$ is the _measure of maximal entropy_. Furthermore the _topological
entropy_ $h=h(\sigma)$ of $(\Sigma,\sigma)$ is given by $h=\text{P}(0)$.

Consider the quantities

$\alpha_{\min}:=\inf_{\mu\in\mathcal{M}_{\sigma}}\int_{\Sigma}\psi\ d\mu\ \
\text{ and }\ \
\alpha_{\max}:=\sup_{\mu\in\mathcal{M}_{\sigma}}\int_{\Sigma}\psi\ d\mu.$

The large deviation principle implies that there exists a real analytic,
concave function
$\mathcal{L}(\psi,\cdot):{\mathbb{R}}\to{\mathbb{R}}_{>0}\cup\\{\infty\\}$
such that, for any non-empty sets $U\subset V\subset{\mathbb{R}}$ with $U$
open and $V$ closed we have

$\displaystyle-\inf_{s\in U}\mathcal{L}(\psi,s)$
$\displaystyle\leq\liminf_{n\to\infty}\frac{1}{n}\log\mu\left(x\in\Sigma:\left|\frac{\psi^{n}(x)}{n}-\eta\right|<\epsilon\right)$
$\displaystyle\leq\limsup_{n\to\infty}\frac{1}{n}\log\mu\left(x\in\Sigma:\left|\frac{\psi^{n}(x)}{n}-\eta\right|<\epsilon\right)\leq-\inf_{s\in
V}\mathcal{L}(\psi,s).$

The function $\mathcal{L}(\psi,\cdot)$ is the Legendre transform of
$t\mapsto\text{P}(t\psi)-h$. That is,

$-\mathcal{L}(\psi,s)=\inf_{t\in{\mathbb{R}}}(\text{P}(t\psi)-h-ts).$

Furthermore, $\mathcal{L}(\psi,\cdot)$ is finite on
$[\alpha_{\min},\alpha_{\max}]$ and is infinite otherwise. An alternative
characterisation for $\mathcal{L}$ is the following:

$-\mathcal{L}(\psi,\eta)=\sup\left\\{h_{\mu}(\sigma):\mu\in\mathcal{M}_{\sigma}\text{
and}\int\psi\ d\mu=\eta\right\\}-h.$

A function $\psi:\Sigma\rightarrow{\mathbb{R}}$ is _lattice_ if there are
$a,b\in{\mathbb{R}}$ satisfying

$\left\\{\psi^{n}(x)+an:x\in\Sigma\text{ and }\sigma^{n}(x)=x\text{ for some
}n\geq 1\right\\}\subseteq b{\mathbb{Z}}.$

If this is not the case then we say that $\psi$ is _non-lattice_.

######  Remark 2.3.

Suppose that $\psi$ is lattice. Then $\psi$ is cohomologous to a function of
the form $a+b\varphi$ where $a,b\in{\mathbb{R}}$ and
$\varphi:\Sigma\to{\mathbb{Z}}$ [54]. When this is the case, the large
deviation behaviour of $\psi$ and $\varphi$ over periodic orbits is the same,
since $\psi^{n}(x)=an+b\varphi^{n}(x)$ when $\sigma^{n}(x)=x$.

###  2.4. Suspension flows

In this section we define suspension flows of subshifts of finite type. See
[54] for more details on the results stated in this section. Let $\Sigma_{A}$
be a transitive subshift of finite type and $r:\Sigma_{A}\to{\mathbb{R}}_{>0}$
a function that is constant on $2$ cylinders. We note that in [54] suspension
flows are considered over mixing subshifts however the same proofs (with some
minor modifications) work when the subshift is transitive. We define the
_suspension flow_ of $\Sigma_{A}^{r}$ to be the space

$\Sigma_{A}^{r}=\\{(x,t)\in\Sigma_{A}\times{\mathbb{R}}_{\geq 0}:0\leq t\leq
r(x)\\}/\sim$

where $(x,t)\sim(r(x),0)$ equipped with the flow
$\sigma^{r}=(\sigma^{r}_{t})_{t>0}$ so that $\sigma_{t}^{r}$ send $(x,s)$ to
$(x,s+t)$ for $s\in{\mathbb{R}}$. There is a natural metric on
$\Sigma_{A}^{r}$ which can be constructed as in [54]. We will not present the
construction of this metric here as it is a little technical.

For a Hölder continuous function $\Phi:\Sigma_{A}^{r}\to{\mathbb{R}}$ we can
define its pressure as

$\text{P}_{\sigma^{r}}(\Phi)=\sup_{m\in\mathcal{M}_{\sigma^{r}}}\left\\{h_{m}(\sigma^{r})+\int_{\Sigma_{A}^{r}}\Phi\
dm\right\\},$

where $\mathcal{M}_{\sigma^{r}}$ is the space of $\sigma^{r}_{t}$\- invariant
Borel probability measures on $\Sigma_{A}^{r}$ and $h_{m}(\sigma^{r})$ is the
entropy of the time-one map $\sigma^{r}_{1}$ for the measure $m$. The map
$s\mapsto\text{P}_{\sigma^{r}}(s\Phi)$ is real analytic. Let $\delta_{r}>0$ be
the unique number such that $\text{P}(-\delta_{r}r)=0$ and write
$\mu_{-\delta_{r}r}$ for the equilibrium state of $-\delta_{r}r$ on
$\Sigma_{A}$. The measure of maximal entropy for $\Sigma_{A}^{r}$ is (locally)
given by

$\frac{\mu_{-\delta_{r}r}\times\text{Leb}}{\int r\ d\mu_{-\delta_{r}r}},$

i.e. up to normalisation it is the measure that acts as Lebesgue along the
fibers of the suspension and as $\mu_{-\delta_{r}r}$ on the base. If we write
$m$ for the measure of maximal entropy then we have that

$\left.\frac{d}{ds}\right|_{s=0}\text{P}_{\sigma^{r}}(s\Phi)=\int\Phi\ dm.$

For $T>0$ we will write $P(\Sigma_{A}^{r},T)$ for the collection of periodic
orbits of $\sigma^{r}$ of length less than $T$. Given $R>0$ we will write
$P(\Sigma_{A}^{r},R,T)$ for the collection of periodic orbits of length
between $T-R$ and $T+R$.

Given a Hölder continuous function $\Phi:\Sigma_{A}^{r}\to{\mathbb{R}}$ it is
a standard result that for any $R>0$ sufficiently large

$\lim_{T\to\infty}\frac{1}{T}\log\left(\sum_{\tau\in
P(\Sigma_{A}^{r},R,T)}e^{-s\int_{\tau}\Phi}\right)=\text{P}_{\sigma^{r}}(-s\Phi)$

for any $s\in{\mathbb{R}}$.

Lastly we recall that two functions $\Phi,\Psi:\Sigma_{A}^{r}\to{\mathbb{R}}$
are _cohomologous_ if $\Phi-\Psi=u^{\prime}$ where
$u:\Sigma_{A}^{r}\to{\mathbb{R}}$ is continuously differentiable (along flow
lines) and

$u^{\prime}(x)=\lim_{t\to 0}\frac{u(\sigma^{r}_{t}(x))-u(x)}{t}.$

Further the function $s\mapsto P_{\sigma^{r}}(s\Phi)$ is a straight line if
and only if $\Phi$ is cohomologous to a constant function.

###  2.5. Finite-state automata

Let $S$ be a finite set and let $S^{\ast}$ denote the set of finite words over
the alphabet $S$. If $w=h_{1}\cdots h_{n}$ and
$w^{\prime}=h^{\prime}_{1}\cdots h_{m}^{\prime}$ are words in $S^{\ast}$, then
its _concatenation_ is the word $ww^{\prime}:=h_{1}\cdots
h_{n}h^{\prime}_{1}\cdots h_{m}^{\prime}$. The _length_ of a word is the
number of letters in $S$ composing it. We let the empty set correspond to the
unique word of length 0 in $S^{\ast}$. A _language_ over $S$ is any subset of
words in $S^{\ast}$.

An _automaton_ over $S$ is a tuple

$\mathcal{A}=(\mathcal{G},\pi,I,F),$

where $\mathcal{G}=(V,E)$ is a finite directed graph, $\pi:E\rightarrow S$ is
a _labeling function_ and $I,F\subset V$ are non-empty sets of _initial_ and
_final_ states.

######  Remark 2.4.

This convention differs from the standard definition of automaton, where it is
required for $I$ to consist of a single vertex.

By a _path_ in $\mathcal{G}$ we mean a sequence $\omega$ of (always directed)
edges $e_{1},\dots,e_{n}$ in $E$ such that the final vertex $v_{i}$ of $e_{i}$
is the initial vertex of $e_{i+1}$ for $i=1,\dots,n-1$. If $v_{0}$ is the
initial vertex of $e_{1}$, we denote this path $\omega$ either by
$\omega=(\xrightarrow{e_{1}}\cdots\xrightarrow{e_{n}})$ or
$\omega=(v_{0}\xrightarrow{e_{1}}\cdots\xrightarrow{e_{n}}v_{n})$ depending on
the emphasis we want to give to the vertices. If there is no ambiguity on the
edges, we can also denote this path by $(v_{0}\rightarrow\cdots\rightarrow
v_{n})$. The _length_ of a path is the number of edges that determine it. Note
that paths of length 1 correspond to the edges in $E$. We also allow the
degenerate case of paths of length 0, which are the vertices in $V$.

If $\omega,\omega^{\prime}$ are paths in $\mathcal{G}$ such that the final
vertex of $\omega$ is the initial vertex of $\omega^{\prime}$, then the
concatenation $\omega\omega^{\prime}$ is the path in $\mathcal{G}$ defined in
the expected way. Similarly we define the concatenation of any finite number
of paths.

A word $w$ in $S^{\ast}$ is _represented_ by the path
$\omega=(v_{0}\xrightarrow{e_{1}}v_{1}\cdots\xrightarrow{e_{n}}v_{n})$ in
$\mathcal{G}$ if $w=\pi(e_{1})\cdots\pi(e_{n})$. If in addition $v_{0}\in I$
and $v_{n}\in F$, we say that $w$ _accepted_ by $\mathcal{A}$. It is clear
that the word represented by a concatenation $\omega\omega^{\prime}$ is the
concatenation of the words represented by $\omega$ and $\omega^{\prime}$. Let
$L=L_{\mathcal{A}}$ be the language consisting of the words accepted by
$\mathcal{A}$. In this case we say that $L$ is _parametrized_ by
$\mathcal{A}$.

The automaton $\mathcal{A}$ is _deterministic_ if any two edges in
$\mathcal{G}$ with the same initial vertex have different labels. In that
case, for any $w\in L_{\mathcal{A}}$ and any initial state $v\in I$ there
exists at most one path in $\mathcal{G}$ representing $w$ and starting at $v$.
The automaton is _pruned_ if any vertex in $\mathcal{G}$ is the final vertex
of a path starting at an initial state.

##  3\. Large deviations

In this section we discuss large deviations with shrinking for potentials on
mixing subshifts of finite type. The main result of the section is Theorem
3.1, and it will be used in the proof of Theorems 1.7 and 6.2 in subsequent
sections.

Suppose that $(\Sigma,\sigma)$ is a mixing subshift of finite type with
$k\times k$ transition matrix $A$, and let $\mu$ denote its measure of maximal
entropy. Also, let $M$ be the least number such that $A^{M}$ has strictly
positive entries. The large deviation principle from Section 2.3 implies that
there is a real analytic, concave function
$\mathcal{L}(\psi,\cdot):[\alpha_{\min},\alpha_{\max}]\to{\mathbb{R}}_{>0}$
such that the following holds: for any $\eta\in(\alpha_{\min},\alpha_{\max})$

$\lim_{\epsilon\to
0^{-}}\limsup_{n\to\infty}\frac{1}{n}\log\mu\left(x\in\Sigma:\left|\frac{\psi^{n}(x)}{n}-\eta\right|<\epsilon\right)=-\mathcal{L}(\psi,\eta).$

Instead of taking two limits as above, first with respect to $n$ and then with
respect to $\epsilon$, it is natural to ask the following. How quickly can a
sequence $\delta_{n}$ decay to $0$ as $n\to\infty$ so that we have

$\lim_{n\to\infty}\frac{1}{n}\log\mu\left(x\in\Sigma:\left|\frac{\psi^{n}(x)}{n}-\eta\right|<\delta_{n}\right)=-\mathcal{L}(\psi,\eta)$
(3.1)

for each $\eta\in(\alpha_{\min},\alpha_{\max})$? We refer to this problem as
large deviations with shrinking intervals. We can ask the same question when
the limit in (3.1) is replaced with the limit supremum.

Large deviations with shrinking intervals are best understood for potentials
$\psi$ that are non-lattice. For example, when $\psi$ is non-lattice the local
central limit theorem [34] implies that (3.1) holds when
$\delta_{n}^{-1}=O(n)$. In [55] Pollicott and Sharp improved this result under
an additional assumption. They showed that if $\psi$ satisfies a non-
Diophantine condition then there exist $\kappa>0$ such that $\eqref{eq.ldpsi}$
holds when $\delta_{n}^{-1}=O(n^{1+\kappa})$.

When $\psi$ is lattice, large deviations with shrinking intervals are not as
well understood. The aim of this section is to study (3.1) for functions
$\psi$ that are constant on $2$ cylinders and are lattice.

We now state our large deviation theorem with shrinking intervals. Write
$\mathcal{L}(\psi,\cdot):[\alpha_{\min},\alpha_{\max}]\to{\mathbb{R}}_{>0}$ be
the function introduced above.

######  Theorem 3.1.

Suppose that $(\Sigma,\sigma)$ is a mixing subshift of finite type and that
$\psi:\Sigma\to{\mathbb{R}}$ is a function that is constant on $2$ cylinders.
Then the following holds. There exists $C>0$ such that for any
$\eta\in(\alpha_{\min},\alpha_{\max})$

$\limsup_{n\to\infty}\frac{1}{n}\log\left(\\#\left\\{x\in\Sigma:\sigma^{n}(x)=x\text{
and
}\left|\frac{\psi^{n}(x)}{n}-\eta\right|<\frac{C}{n^{2}}\right\\}\right)=h-\mathcal{L}(\psi,\eta)$

where $h$ is the topological entropy of $(\Sigma,\sigma)$. Furthermore we can
take

$C=\frac{4M^{2}(1+k^{2})^{2}(\alpha_{\max}-\alpha_{\min})}{\sqrt{5}}.$

In the case that $\psi$ takes values in ${\mathbb{Z}}$ then there exists
$\eta\in(\alpha_{\min},\alpha_{\max})$ and $\epsilon>0$ such that

$\limsup_{n\to\infty}\frac{1}{n}\log\left(\\#\left\\{x\in\Sigma:\sigma^{n}(x)=x\text{
and
}\left|\frac{\psi^{n}(x)}{n}-\eta\right|<\frac{\epsilon}{n^{2}}\right\\}\right)=0.$

######  Remark 3.2.

i) This theorem also holds if we only assume that $(\Sigma,\sigma)$ is
transitive (opposed to mixing). Indeed, if $(\Sigma,\sigma)$ is transitive we
can find an integer $p\geq 1$ such that $(\Sigma,\sigma^{p})$ decomposes as a
disjoint union of $p$, $\sigma^{p}$-invariant sets. These
$\sigma^{p}$-invariant sets are mixing subshifts of finite type when equipped
with $\sigma^{p}$. We can then apply the mixing version of our theorem above
to these subshifts to deduce the transitive version.
ii) Our result significantly improves the decay rate implied by the local
limit theorem under the non-lattice assumption. Furthermore, the case that
$\psi$ takes values in a lattice shows that the decay rates obtained in the
first part of Theorem 3.1 are optimal.

For the rest of the section we note the correspondence between periodic orbits
of $(\Sigma,\sigma)$ and cycles (i.e. closed paths) in the adjacency graph
$\mathcal{G}_{A}$. We say that a cycle is _simple_ if it does not visit any
state more than once.

To prove the above result we start with the following observation.

######  Lemma 3.3.

Suppose that $(\Sigma,\sigma)$ is a mixing subshift of finite type and that
$\psi:\Sigma\to{\mathbb{R}}$ is a function that is constant on $2$ cylinders.
Then

$\alpha_{\min}=\inf_{\sigma^{n}(x)=x}\frac{\psi^{n}(x)}{n}\ \text{ and }\
\alpha_{\max}=\sup_{\sigma^{n}(x)=x}\frac{\psi^{n}(x)}{n},$

and furthermore there exist periodic orbits $\overline{x},\overline{y}$ that
achieve these values, i.e.
$\psi^{|\overline{x}|}(\overline{x})=|\overline{x}|\alpha_{\min},\psi^{|\overline{y}|}(\overline{y})=|\overline{y}|\alpha_{\max}.$
Here the infimum and supremum are over all the periodic orbits.

###### Proof.

The first statement follows from a result of Sigmund [67] which states that
the set of probability measures supported on periodic orbits is dense in
$\mathcal{M}_{\sigma}$ (equipped with the weak-$\ast$ topology). For the
furthermore statement note that each periodic orbit can be written as a
disjoint union of simple cycles. It follows easily that the above infimum and
supremum are attained by simple cycles (and powers of them). ∎

We also need a more technical version of this lemma that applies on
subsequences. We begin with the following observation.

######  Lemma 3.4.

Take an interval $(s,t)\subset{\mathbb{R}}$ and a number $\eta\in(s,t)$. Then
there are infinitely many $n\geq 1$ for which there exist integers $0\leq
a,b\leq n$ with $a+b=n$ and such that

$\left|\frac{as+bt}{n}-\eta\right|\leq\frac{t-s}{\sqrt{5}\,n^{2}}.$

###### Proof.

Note that it suffices to prove this result when $s=0$, $t=1$. The general
result then follows by shifting and rescaling the interval $(0,1)$ into
$(s,t)$. When $s=0$, $t=1$ the result follows from the well-known Hurwitz’s
Theorem [41] from Diophantine approximation. ∎

We also need the following lemma. Suppose that the simple periodic orbit
$\overline{x}$ realising $\alpha_{\max}$ has initial state $i$ and that the
initial state for $\overline{y}$ realising $\alpha_{\min}$ is $j$ (from Lemma
3.3). Further assume that we repeat $\overline{x}$ and $\overline{y}$ by each
other’s periods so that they both have period $l$ satisfying $1<l\leq k^{2}$.

######  Lemma 3.5.

Suppose that $(\Sigma,\sigma)$ is a mixing subshift of finite type and that
$\psi:\Sigma\to{\mathbb{R}}$ is a function that is constant on $2$ cylinders
such that $\alpha_{\min}<\alpha_{\max}$. Then we can find periodic orbits
$x,y$ both with period at most $2M(1+k^{2})$ such that the initial state for
$x$ is $i$, the initial state for $y$ is $j$ and we have that

$\alpha_{\min}<\frac{\psi^{|x|}(x)}{|x|}<\frac{\psi^{|y|}(y)}{|y|}<\alpha_{\max}.$

###### Proof.

Consider the start state $i$ and find a path $p$ from $i$ to $j$ of length $M$
and a path $q$ from $j$ to $i$ of length $M$. By composing the path $p$ with
$r$ (to be chosen later) repeats of a single cycle of $\overline{y}$ and $q$
we obtain a periodic orbit $y$ of length $2M+lr$. Further we have that

$\frac{\psi^{|y|}(y)}{|y|}\leq\frac{2M\alpha_{\max}+lr\alpha_{\min}}{2M+lr}$

and $y$ starts at $i$. Similarly we find $x$ starting at $j$ with $|x|=2M+lr$
and

$\frac{\psi^{|x|}(x)}{|x|}\geq\frac{2M\alpha_{\min}+lr\alpha_{\max}}{2M+lr}.$

Now, as long as $r$ is chosen so that

$2M\alpha_{\min}+lr\alpha_{\max}>2M\alpha_{\max}+lr\alpha_{\min}$

$x,y$ will satisfy the final inequality in the lemma. Note that this
inequality is satisfied for $r=2M$ in which case $x$ and $y$ have periods
$2M+2Ml\leq 2M(1+k^{2})$ as required. ∎

We also require the following.

######  Lemma 3.6.

Suppose that $(\Sigma,\sigma)$ is a mixing subshift of finite type and that
$\psi:\Sigma\to{\mathbb{R}}$ is a function that is constant on $2$ cylinders.
Suppose that there exist periodic orbits $x,y$ both with period $l$ and same
initial state such that $lA=\psi^{l}(x)<\psi^{l}(y)=lB$. Then there exists
$\overline{C}>0$ such that for any $\eta\in(A,B)$ we can find an infinite
sequence of periodic orbits $x_{n}\in\Sigma$ such that

$\left|\frac{\psi^{|x_{n}|}(x_{n})}{|x_{n}|}-\eta\right|\leq\frac{\overline{C}}{|x_{n}|^{2}}.$

Furthermore we can take

$\overline{C}=\frac{(\alpha_{\max}-\alpha_{\min})l^{2}}{\sqrt{5}}.$

###### Proof.

By Lemma 3.4 there exist infinitely many $n\geq 1$ such that the following
holds. There are integers $n_{1},n_{2}\geq 0$ with $n_{1}+n_{2}=n$ and such
that

$\left|\frac{n_{1}A+n_{2}B}{n_{1}+n_{2}}-\eta\right|\leq\frac{B-A}{\sqrt{5}n^{2}}\leq\frac{(\alpha_{\max}-\alpha_{\min})l^{2}}{\sqrt{5}(ln)^{2}}.$

Since $x$ and $y$ have the same initial vertex, we can form a new periodic
orbit by composing $n_{1}$ copies of $x$ followed by $n_{2}$ copies of $y$.
This creates a periodic orbit $z$ of orbit length $nl$ with the property that

$\frac{\psi^{nl}(z)}{nl}=\frac{n_{1}A+n_{2}B}{n_{1}+n_{2}}\ \text{ and so }\
\left|\frac{\psi^{nl}(z)}{nl}-\eta\right|\leq\frac{(\alpha_{\max}-\alpha_{\min})l^{2}}{\sqrt{5}|z|^{2}}.$

Since we can run this construction for infinitely many $n$, the result
follows. ∎

To obtain uniformity over $\eta$, that is, to show the existence of $C$ in
Theorem 3.1, we need to upgrade Lemma 3.6 using Lemma 3.5.

######  Proposition 3.7.

Suppose that $(\Sigma,\sigma)$ is a mixing subshift of finite type and that
$\psi:\Sigma\to{\mathbb{R}}$ is a function that is constant on $2$ cylinders.
Then there exists $C>0$ such that for any
$\eta\in(\alpha_{\min},\alpha_{\max})$ there exists an infinite sequence of
periodic orbits $x_{n}\in\Sigma$ such that

$\left|\frac{\psi^{|x_{n}|}(x_{n})}{|x_{n}|}-\eta\right|\leq\frac{C}{|x_{n}|^{2}}.$

Furthermore we can take

$C=\frac{4M^{2}(1+k^{2})^{2}(\alpha_{\max}-\alpha_{\min})}{\sqrt{5}}.$

###### Proof.

We can assume that $\psi$ is not cohomologous to a constant function
(otherwise the conclusion is clear), so that $\alpha_{\min}<\alpha_{\max}$.

We split the interval $(\alpha_{\min},\alpha_{\max})=I_{1}\cup I_{2}$ into the
two (non-disjoint) intervals

$I_{1}=\left(\alpha_{\min},\frac{\psi^{|y|}(y)}{|y|}\right)\ \text{ and }\
I_{2}=\left(\frac{\psi^{|x|}(x)}{|x|},\alpha_{\max}\right)$

where $x,y$ are the orbits constructed in Lemma 3.5. In particular, both $|x|$
and $|y|$ are bounded above by $2M(1+k^{2})$. We can now apply Lemma 3.6 to
both of the intervals $I_{1}$ and $I_{2}$ to deduce the result. ∎

######  Definition 3.8.

Let $\psi,\Sigma$ be as above. Suppose $w\in(\alpha_{\min},\alpha_{\max})$ is
chosen so that there exists $x$ with $\sigma^{n}(x)=x$ and $\psi^{n}(x)=nw$.
We define $d(\psi,w)$ to be the greatest common divisor of all numbers $n\geq
1$ such that

$\\#\left\\{x\in\Sigma_{\mathcal{C}}:\sigma^{n}(x)=x,\psi^{n}(x)=wn\right\\}>0.$

If
$\\#\left\\{x\in\Sigma_{\mathcal{C}}:\sigma^{n}(x)=x,\psi^{n}(x)=wn\right\\}=0$
for all $n$ then we set $d(\psi,w)=0$.

Note that $d(\psi,w)=0$ for all but countably many values of $w.$ This is
because the values for which $d(\psi,w)>0$ are contained in the rational span
of the values that the averaged Birkhoff sum of $\psi$ attains on simple
cycles. By a result of Marcus and Tuncel [48, Thm. 14] for any $\xi>0$ and any
closed subset $W\subset(\alpha_{\min},\alpha_{\max})$ there exist
$r,N\in{\mathbb{Z}}_{\geq 0}$ and $\delta>0$ such that, for any $n\geq N$ with
$d(\psi,w)|n$,

$\\#\left\\{x\in\Sigma:\sigma^{n}(x)=x,\psi^{n}(x)=wn\right\\}\geq\delta
n^{-r}e^{n(h-(\mathcal{L}(\psi,w))-\xi)}$ (3.2)

for each $w\in W$ satisfying $d(\psi,w)>0$. To make use of this result we need
to control the values of $d(\psi,w)$ as $w$ takes values in a shrinking
interval.

######  Lemma 3.9.

There exists $C>0$ such that for any $\eta\in(\alpha_{\min},\alpha_{\max})$ we
can find a sequence $w_{n}\in(\alpha_{\min},\alpha_{\max})$ and a sequence
$x_{n}\in\Sigma$ of periodic orbits such that

$w_{n}\in\left[\eta-\frac{C}{|x_{n}|^{2}},\eta+\frac{C}{|x_{n}|^{2}}\right]\
\text{ with }\ \frac{\psi^{|x_{n}|}(x_{n})}{|x_{n}|}=w_{n}$

and $d(\psi,w_{n})||x_{n}|$.

###### Proof.

By Lemma 3.7 there exist $C>0,N\geq 1$ depending only on $\psi,\Sigma$ such
that for any $\eta\in(\alpha_{\min},\alpha_{\max})$ and $n\geq N$ there is a
sequence of periodic orbits $x_{n}\in\Sigma$ with periods $|x_{n}|$ (i.e.
$\sigma^{|x_{n}|}(x_{n})=x_{n}$) such that

$\left|\frac{\psi^{|x_{n}|}(x_{n})}{|x_{n}|}-\eta\right|\leq\frac{C}{|x_{n}|^{2}}.$

We define $w_{n}=\frac{\psi^{n}(x_{n})}{n}$ and note that
$d(\psi,w_{n})||x_{n}|$ if and only if

$\\#\left\\{x\in\Sigma:\sigma^{|x_{n}|}(x)=x,\frac{\psi^{|x_{n}|}(x_{n})}{|x_{n}|}=w_{n}\right\\}>0.$

Hence we are done. ∎

For a sequence $(\delta_{n})_{n\geq 1}$ of positive numbers and $n\geq 1$ we
define

$F_{n}(\eta,\delta_{n})=\left\\{x\in\Sigma:\sigma^{n}(x)=x,\left|\frac{\psi^{n}(x)}{n}-\eta\right|<\delta_{n}\right\\}$

for $\epsilon>0,n\geq 1$ and $\eta\in(\alpha_{\min},\alpha_{\max})$.

######  Proposition 3.10.

Suppose that $(\Sigma,\sigma)$ is a mixing subshift of finite type and that
$\psi:\Sigma\to{\mathbb{R}}$ is a function that is constant on $2$ cylinders.
Then there exists $C>0$ such that for any
$\eta\in(\alpha_{\min},\alpha_{\max})$ and $\xi>0$ there exist
$\delta,r,M,\epsilon>0$ and a sequence of integers $n_{l}$ with
$n_{l}\to\infty$ as $l\to\infty$ such that

$\\#F_{n_{l}}(\eta,Cn_{l}^{-2})\geq\delta
n_{l}^{-r}e^{n_{l}((h-\mathcal{L}(\psi,\eta))-\xi)}$

for all $l\geq 1.$

######  Remark 3.11.

For $\eta$ with $d(\psi,\eta)>0$ this result follows immediately from
estimates due to Marcus and Tuncel [48]. The main strength of the above
estimates are that they hold for all values of
$\eta\in(\alpha_{\min},\alpha_{\max})$.

###### Proof of Proposition 3.10.

We use Lemma 3.7 to find a sequence of periodic orbits $(x_{n})_{n}$ such that

$|w_{n}-\eta|\leq\frac{C}{|x_{n}|^{2}}\ \text{ where }\
w_{n}=\frac{\psi^{|x_{n}|}(x_{n})}{|x_{n}|}$

for each $n\geq 1$. By (3.2), for any $\xi>0$ and for all $n$ sufficiently
large we have that

$\\#\left\\{x\in\Sigma:\sigma^{|x_{n}|}(x)=x\text{ and
}\left|\frac{\psi^{|x_{n}|}(x_{n})}{|x_{n}|}-\eta\right|<\frac{C}{|x_{n}|^{2}}\right\\}\geq\delta|x_{n}|^{-r}e^{|x_{n}|((h-\mathcal{L}(\psi,w_{n}))-\xi)}$

for some $\delta,r>0$. By analyticity of $\mathcal{L}$ there is
$\widetilde{C}>0$ such that

$|\mathcal{L}(\psi,\eta)-\mathcal{L}(\psi,w_{n})|\leq\widetilde{C}|\eta-
w_{n}|=O(|x_{n}|^{-1})$

(where the implied error constant is independent of $n$) and this implies our
estimate. This concludes the proof. ∎

###### Proof of Theorem 3.1.

Note that the Large Deviation Principle implies that

$\limsup_{n\to\infty}\frac{1}{n}\log\left(\\#\left\\{x\in\Sigma_{\mathcal{C}}:\sigma^{n}(x)=x,\left|\frac{\psi^{n}(x)}{n}-\eta\right|<\frac{C^{\prime}}{n^{2}}\right\\}\right)\leq
h-\mathcal{L}(\psi,\eta)$

for any $C^{\prime}>0$ and $\eta\in(\alpha_{\min},\alpha_{\max})$. Proposition
3.10 also implies that for $C>0$ (as in the proposition)

$\limsup_{n\to\infty}\frac{1}{n}\log\left(\\#\left\\{x\in\Sigma_{\mathcal{C}}:\sigma^{n}(x)=x,\left|\frac{\psi^{n}(x)}{n}-\eta\right|<\frac{C}{n^{2}}\right\\}\right)\geq
h-\mathcal{L}(\psi,\eta).$ (3.3)

This proves part of the theorem. The other part follows similarly, and the
estimate for $C$ follows from Proposition 3.7.

We now finish by proving the final statements. Without loss of generality we
can, by Remark 2.3, assume that $\psi$ takes values in the integers. When this
is the case, the set $\left\\{\frac{\psi^{n}(x)}{n}:\sigma^{n}(x)=x\right\\}$
contains rational numbers all with denominator at most $n$. By [41] there is
$\eta\in(\alpha_{\min},\alpha_{\max})$ such that if $\epsilon>0$ is
sufficiently small then for all but finitely many values of $n$,

$\left|\frac{\psi^{n}(x)}{n}-\eta\right|>\frac{\epsilon}{n^{2}}\ \text{ for
all $x\in\Sigma$ with $\sigma^{n}(x)=x$.}$

Hence $F_{n}(\eta,\epsilon n^{-2})$ is empty for all $n$ sufficiently large. ∎

##  4\. Large deviation for pairs of word metrics

In this section we prove Theorem 1.7. The proof uses the Cannon automatic
structure for hyperbolic groups. To avoid having to define all of these
objects here, we refer the reader to [13]. Throughout the proof, we will
follow same terminology and notation as that used in [13].

###### Proof of Theorem 1.7.

Without loss of generality assume that $d_{S},d_{S_{\ast}}$ are not roughly
similar (i.e. there does not exist $\tau,C>0$ such that $|d_{S}(g,h)-\tau
d_{S_{\ast}}(g,h)|<C$ for all $g,h\in\Gamma$). By Lemma 3.8 and Example 3.9 in
[11] we can find a Cannon coding for $(\Gamma,S)$ with corresponding shift
space $(\Sigma,\sigma)$ and a Hölder continuous function
$\psi:\Sigma\to{\mathbb{R}}$ satisfying the following: if
$z=(z_{0},z_{1},\ldots,z_{n-1},z_{1},\ldots)\in\Sigma$ is a periodic orbit of
period $n$, then the $n$th Birkhoff sum of $\psi$ on $z$ outputs the value
$\ell_{S_{\ast}}[g]$, where $g\in\Gamma$ is the group element obtained by
multiplying the labelings in the finite path $z_{0},z_{1},\ldots,z_{n-1}$. By
construction, $\psi$ is constant on $2$ cylinders and takes values in
${\mathbb{Z}}$.

Fix a maximal component $\Sigma_{\mathcal{C}}$ in $\Sigma$. We know that the
function $-\psi$ satisfies a large deviation principle over the periodic
orbits on $\Sigma_{\mathcal{C}}$. Furthermore, the rate function $\mathcal{I}$
is the Legendre transform of the Manhattan curve for $d_{S},d_{S_{\ast}}$ by
[13, Lem. 3.3]. In particular,

$\alpha_{\min}=\inf_{\sigma^{n}(x)=x}\frac{\psi^{n}(x)}{n}={\rm
Dil}(S,S_{\ast})^{-1}\ \text{ and }\
\alpha_{\max}=\sup_{\sigma^{n}(x)=x}\frac{\psi^{n}(x)}{n}={\rm
Dil}(S_{\ast},S)$

where the infimum/supremum is taken over all periodic orbits in
$\Sigma_{\mathcal{C}}$. Now, by Theorem 3.1 we obtain the same limits with
shrinking intervals, i.e. $\eta\in(\alpha_{\min},\alpha_{\max})$

$\limsup_{n\to\infty}\frac{1}{n}\log\left(\\#\left\\{x\in\Sigma:\sigma^{n}(x)=x\text{
and
}\left|\frac{\psi^{n}(x)}{n}-\eta\right|\leq\frac{C}{n}\right\\}\right)=\mathcal{I}(\eta)$

for some $C$ independent of $\eta$. It is possible that the system
$(\Sigma_{\mathcal{C}},\sigma)$ is not mixing but is instead transitive. This
is no issue as explained in Remark 3.2. We know that each periodic orbit has a
corresponding conjugacy class, and [14, Lem. 4.2] says that the periodic
orbits overcount the number of conjugacy classes by at most a linear factor in
$|x|_{S}$. Hence we must have

$\limsup_{n\to\infty}\frac{1}{n}\log\\#\left\\{[g]\in{\bf
conj}:\ell_{S}[g]=n,|\ell_{S_{\ast}}[g]-\eta\ell_{S}[g]|<\epsilon\right\\}=\mathcal{I}(\eta)\leq
v_{S}$

for any $\epsilon>0$ and $\eta\in(\alpha_{\min},\alpha_{\max})$. By [16, Thm.
1.1] we have that $\mathcal{I}$ is maximised (and equals $v_{S}$) when

$\eta=\lim_{T\to\infty}\frac{1}{\\#\\{[g]\in{\bf
conj}\colon\ell_{S}[g]<T\\}}\sum_{\ell_{S}[g]<T}\frac{\ell_{S_{\ast}}[g]}{T}.$

This concludes the proof. ∎

As a corollary we deduce Corollary 1.8.

###### Proof of Corollary 1.8.

The first part of the theorem, when $\eta$ is irrational, follows as a direct
corollary of Theorem 1.7. To deduce the final statement when $\eta$ is
rational it suffices to show that, when $(\Sigma,\sigma)$ is a mixing subshift
of finite type and $\psi:\Sigma\to{\mathbb{Z}}$ is a function that is constant
of $2$ cylinders, then the following holds: if
$p/q\in(\alpha_{\min},\alpha_{\max})\cap{\mathbb{Q}}$ then there exists a
periodic orbit $x\in\Sigma$ such that $\psi^{|x|}(x)=|x|p/q.$ It is an easy
exercise to verify this and so we leave it to the reader. ∎

######  Example 4.1.

Let $F_{2}=\langle a,b\rangle$ be the free group on two generators and
consider the generating sets

$S=\\{a,b,a^{-1},b^{-1}\\}\ \text{ and }\
S_{\ast}=\\{a,b,ab,a^{-1},b^{-1},(ab)^{-1}\\}.$

The corresponding word metrics have exponential growth rates
$v_{S_{\ast}}=\log(4)$ and $v_{S}=\log(3)$. The Manhattan curve
$\theta_{S/S_{\ast}}$ was computed in [16] and is given by

$\theta_{S/S_{\ast}}(t)=\log\left(\frac{1}{2}e^{-t}\left(e^{-t}+\sqrt{e^{-t}(e^{-t}+8)}+4\right)\right).$

From the definition we see that
$\mathcal{I}(v_{S_{\ast}}/v_{S})=\log(4)-\Lambda/\log(3)$ where $\Lambda$ is
the constant

$\Lambda=\sup_{t\in{\mathbb{R}}}\left\\{\log(4)-\frac{\log(4)}{\log(3)}t-\theta_{S/S_{\ast}}(t)\right\\}.$

This can be computed (using, say Wolfram Alpha) to be

$\log(16)\log\left(\log\left(\frac{4}{3}\right)\right)+\log(9)\log\left(\frac{\log\left(\frac{3}{2}\right)}{\log(\frac{4}{3})}\right)+\log(4)\left(\log(2)-\log\left(\log\left(\frac{3}{2}\right)\log(2)\right)\right).$

Theorem 1.7 then implies that there is $C>0$ such that

$\displaystyle\limsup_{T\to\infty}\frac{1}{T}\log\left(\\#\left\\{[g]\in{\bf
conj}:\ell_{S_{\ast}}[g]<T,|v_{S}\ell_{S}[g]-v_{S_{\ast}}\ell_{S_{\ast}}[g]|\leq\frac{C}{T}\right\\}\right)$
$\displaystyle=\log(4)-\frac{\Lambda}{\log(3)}$ $\displaystyle\approx
1.3679878759$

and similarly we also have

$\displaystyle\limsup_{T\to\infty}\frac{1}{T}\log\left(\\#\left\\{[g]\in{\bf
conj}:\ell_{S}[g]<T,|v_{S}\ell_{S}[g]-v_{S_{\ast}}\ell_{S_{\ast}}[g]|\leq\frac{C}{T}\right\\}\right)$
$\displaystyle=\log(3)-\frac{\Lambda}{\log(4)}$ $\displaystyle\approx
1.0841047424.$

In this case we can set $k=6,M=2,\alpha_{\max}=2,\alpha_{\min}=1$ by [16].
Also, it was computed in [16] that $-\theta^{\prime}_{S/S_{\ast}}(0)=4/3$. We
therefore have that

$\frac{4M^{2}(1+k^{2})^{2}(\alpha_{\max}-\alpha_{\min})}{\sqrt{5}}=\frac{4(2^{2})(1+6^{2})(2-1)}{\sqrt{5}}=\frac{592}{\sqrt{5}}\approx
264.7\leq 300$

and

$\limsup_{T\to\infty}\frac{1}{T}\log\left(\\#\left\\{[g]\in{\bf
conj}:\ell_{S_{\ast}}[g]<T,|3\ell_{S}[g]-4\ell_{S_{\ast}}[g]|\leq\frac{300}{T}\right\\}\right)=v_{S_{\ast}}.$

Therefore the length spectra of $3d_{S}$ and $4d_{S_{\ast}}$ are within
distance $300$ on a set of full exponential growth rate for $d_{S_{\ast}}$. In
particular, for any $\eta\in(1,2)$ we can find an infinite sequence of
conjugacy classes $[g_{n}]\in{\bf conj}(\Gamma)$ such that

$\left|\frac{\ell_{S}[g_{n}]}{\ell_{S_{\ast}}[g_{n}]}-\eta\right|\leq\frac{300}{|g_{n}|_{S_{\ast}}^{2}}.$

##  5\. Encoding cubulations via finite-state automata

In this section we study further the class $\mathfrak{G}$ defined in the
introduction. We prove Proposition 5.2, which provides plenty of examples of
groups in this class. Then we construct a finite-state automaton that encodes
a pair of cubulations of a group in $\mathfrak{G}$, our main result being
Proposition 5.9. This will be done in the greater generality of the class
$\mathfrak{X}$ of pairs of compatible cubulations. Proposition 5.9 is key to
prove our main results in Section 6.

###  5.1. The classes $\mathfrak{G}$ and $\mathfrak{X}$

Throughout this and the next section we will work with the following notion of
compatibility of pairs of group actions on ${\rm CAT}(0)$ cube complexes.

######  Definition 5.1.

Let $\mathfrak{X}$ be the class of triples
$(\Gamma,\mathcal{X},\mathcal{X}_{\ast})$, where $\Gamma$ is a non-virtually
cyclic group acting cocompactly on the ${\rm CAT}(0)$ cube complexes
$\mathcal{X},\mathcal{X}_{\ast}$ and satisfying:

  1. (1)

the action on $\mathcal{X}$ is proper and virtually co-special;

  2. (2)

every hyperplane stabilizer for the action on $\mathcal{X}_{\ast}$ is convex-
cocompact for the action on $\mathcal{X}$; and,

  3. (3)

the action of $\Gamma$ on $\mathcal{X}$ has a contracting element.

Note that in the definition above we do not require the action on
$\mathcal{X}_{\ast}$ to be proper.

Since hyperplane stabilizers are always convex-cocompact and being a
contracting element does not depend on the cubulation [31, Lem. 4.6], it
follows that $(\Gamma,\mathcal{X},\mathcal{X}_{\ast})\in\mathfrak{X}$ whenever
$\Gamma\in\mathfrak{G}$ and $\mathcal{X},\mathcal{X}_{\ast}$ are cubulations
of $\Gamma$.

The main result of this section is the following proposition, which tells us
that the class $\mathfrak{G}$ is much bigger than the class of cubulable
hyperbolic groups.

######  Proposition 5.2.

The following classes of groups are contained in $\mathfrak{G}$.

  * i)

Hyperbolic cubulable groups that are non-elementary.

  * ii)

Right-angled Artin groups of the form $\Gamma=A_{G}$, where $G$ is a finite
graph with more than one vertex, that is not a join and such that
$\operatorname{st}(v)$ is not contained in $\operatorname{st}(w)$ for every
pair of distinct vertices $v,w$ of $G$.

  * iii)

Right-angled Coxeter groups that are not virtually cyclic or direct products
and are of the form $\Gamma=W_{G}$, where $G$ is finite and does not have any
_loose squares_.

Moreover, if $\Gamma$ is cubulable and hyperbolic relative to groups belonging
to $\mathfrak{G}$, then $\Gamma$ belongs to $\mathfrak{G}$.

For $\Gamma=W_{G}$ a right-angled Coxeter group, a _loose square_ is a full
subgraph $\Delta\subset G$ that is a square, and such that for every maximal
subgraph $\Lambda\subset G$ with $W_{\Lambda}$ virtually abelian, either
$\Delta\subset\Lambda$ or $\Delta\cap\Lambda$ generates a finite subgroup of
$\Gamma$.

Many non-relatively hyperbolic right-angled Artin and Coxeter groups satisfy
assumptions i) and ii) of Proposition 5.2. Indeed, a RAAG is non-trivially
relatively hyperbolic if and only if it is a non-trivial free product, and
hence RAAGs with underlying graphs $n$-agons for $n\geq 5$ are not relatively
hyperbolic and belong to $\mathfrak{G}$.

For the proof of Proposition 5.2 we require two results, the first one being
an observation about virtual specialness.

######  Lemma 5.3.

Let $\mathcal{X},\mathcal{X}_{\ast}$ be cubulations of the group $\Gamma$ and
assume that the action on $\mathcal{X}$ is virtually co-special. If every
hyperplane stabilizer for the action on $\mathcal{X}_{\ast}$ is convex-
cocompact with respect to $\mathcal{X}$, then the action of $\Gamma$ on
$\mathcal{X}_{\ast}$ is virtually co-special.

###### Proof.

If $\mathcal{X}$ and $\mathcal{X}_{\ast}$ satisfy the assumptions of the
lemma, then all the double cosets of the hyperplane stabilizers for the action
of $\Gamma$ on $\mathcal{X}_{\ast}$ are separable by [58, Thm. A.1]. Then the
action of on $\mathcal{X}_{\ast}$ is virtually co-special by the double-cosets
criterion [39, Thm. 9.19]. ∎

The second result we need is a criterion of convex-cocompactness for subgroups
of cubulable relatively hyperbolic groups, which may be of independent
interest and whose proof is postponed to the appendix.

######  Proposition 5.4.

Let $\Gamma$ be a relatively hyperbolic group acting properly and cocompactly
on the ${\rm CAT}(0)$ cube complex $\mathcal{X}$. Then the following are
equivalent for a subgroup $H<\Gamma$.

  1. (1)

$H$ is convex-cocompact for the action of $\Gamma$ on $\mathcal{X}$.

  2. (2)

$H$ is relatively quasiconvex and $H\cap P$ is convex-cocompact for the action
of $\Gamma$ on $\mathcal{X}$ for any maximal parabolic subgroup $P<\Gamma$.

###### Proof of Proposition 5.2.

By Agol’s Theorem [1, Thm. 1.1] every cubulation of a hyperbolic group is
virtually co-special. Moreover, the class of convex-cocompact subgroups for
any such cubulation coincides with the class of quasiconvex subgroups [39,
Prop. 7.2]. Since any loxodromic element in a hyperbolic group is contracting,
this solves the proposition for groups in class i).

Now, let $\Gamma$ be a group belonging to the class ii) (respectively iii)).
In [30, Thm. A] (resp. [30, Cor. C]) it was proven that $\Gamma$ has a unique
_cubical coarse median structure_. By [30, Thm. 2.15] this uniqueness result
is equivalent to the class of convex-cocompact subgroups being independent of
the cubulation. Since finitely generated right-angled Artin (resp. Coxeter)
groups are virtually special, $\Gamma$ satisfies Items (1) and (2) of
Definition 1.1. The existence of a contracting element for $\Gamma$ for a
geometric group action on a ${\rm CAT}(0)$ cube complex follows from [73, Sec.
5.2] and the references therein.

To prove the moreover statement, let $\Gamma$ be a group that is hyperbolic
relative to groups belonging to $\mathfrak{G}$ and let
$\mathcal{X},\mathcal{X}_{\ast}$ be two cubulations of $\Gamma$. If $P<\Gamma$
is a maximal parabolic subgroup, then by [61, Thm. 1.1] it has convex cores
$Z_{P}\subset\mathcal{X}$ and $(Z_{P})_{\ast}\subset\mathcal{X}_{\ast}$. Also,
since $P$ belongs to $\mathfrak{G}$, by Lemma 5.3 the action of $P$ on $Z_{P}$
is virtually co-special. As this holds for every maximal parabolic subgroup,
the action of $\Gamma$ on $\mathcal{X}$ is virtually co-special either by [33,
Thm. A] or [58, Thm. 1.2].

Consider a group $H<\Gamma$ that is convex-cocompact for the action of
$\Gamma$ on $\mathcal{X}$. By Proposition 5.4 $H$ is relatively quasiconvex
and $H\cap P$ is a convex-cocompact subgroup for any maximal parabolic
subgroup $P<\Gamma$. This implies that $H\cap P<P$ is convex-cocompact for the
action of $P$ on $Z_{P}$, see. e.g. Lemmas 2.14 and 2.15 in [58]. But each
such $P$ belongs to $\mathfrak{G}$, so $H\cap P$ is also convex-cocompact for
the action of $P$ on $(Z_{P})_{\ast}$, implying that $H\cap P$ is convex-
cocompact for the action of $\Gamma$ on $\mathcal{X}_{\ast}$. By Proposition
5.4 we deduce that $H$ is convex-cocompact for the action of $\Gamma$ on
$\mathcal{X}_{\ast}$, so that the actions on $\mathcal{X}$ and
$\mathcal{X}_{\ast}$ have the same sets of convex-cocompact subgroups. Since
any contracting element in a maximal parabolic subgroup is contracting for
$\Gamma$, we have proven that $\Gamma$ belongs to $\mathfrak{G}$. ∎

######  Example 5.5.

Let $M$ be a cusped hyperbolic 3-manifold with cusps $V_{1},\dots,V_{r}\subset
M$. We affirm that $\Gamma=\pi_{1}(M)$ does not belong to $\mathfrak{G}$. For
each $i=1,\dots,r$ choose distinct slopes $\alpha_{i},\beta_{i}$ for the cusp
$V_{i}$. Equivalently, each pair $\alpha_{i},\beta_{i}$ represents a pair of
cyclic subgroups (up to commensurability) such that their union generates a
finite-index subgroup of $\pi_{1}(V_{i})$. By [20, Cor. 1.3], there exists a
cubulation $\mathcal{X}$ of $\Gamma$ such that each $\alpha_{i}$ and
$\beta_{i}$ represents a convex subgroup. Since any cubulation of
${\mathbb{Z}}^{2}$ has a subgroup that is not convex-cocompact (this follows
for instance from [72, Thm. 3.6]), for $\Gamma$ as above we can produce two
cubulations $\mathcal{X},\mathcal{X}_{\ast}$ not satisfying (2) in Definition
1.1.

However, the data of the slopes that are convex-cocompact in cubulations of
$\Gamma$ are the only obstruction for them determining triplets in
$\mathfrak{X}$. That is, if $\mathcal{X},\mathcal{X}_{\ast}$ are two
cubulations of $\Gamma$, then
$(\Gamma,\mathcal{X},\mathcal{X}_{\ast})\in\mathfrak{X}$ if and only if they
have the same pairs of convex-cocompact slopes for each cusp subgroup. The
proof of this follows the same lines as the proof of Proposition 5.2.

######  Example 5.6.

There exist groups $\Gamma$ not necessarily belonging to $\mathfrak{G}$ for
which we still can find essentially distinct cubulations
$\mathcal{X},\mathcal{X}_{\ast}$ such that
$(\Gamma,\mathcal{X},\mathcal{X}_{\ast})\in\mathfrak{X}$.

As an example, let $\Gamma$ be a finite graph product of finite groups and let
$\mathcal{X}$ be the graph-product complex with the standard action by
$\Gamma$. If $\phi\in\textnormal{Aut}(\Gamma)$ is any automorphism, then we
let $\mathcal{X}_{\ast}$ be the cubulation obtained by precomposing by $\phi$
the action of $\Gamma$ on $\mathcal{X}$. Then, as long as $\Gamma$ has a
contracting element, $(\Gamma,\mathcal{X},\mathcal{X}_{\ast})\in\mathfrak{X}$
by combining Theorem D (1) and Theorem 2.15 in [30]. We note that there are
many right-angled Coxeter groups with _large_ outer automorphism groups [62].

If instead we apply [30, Thm. D (2)], the same conclusion holds for $\Gamma$
any Coxeter group with a contracting element, with $\mathcal{X}$ being its
Niblo-Reeves cubulation, and $\mathcal{X}_{\ast}$ obtained from $\mathcal{X}$
after twisting by an automorphism of $\Gamma$.

###  5.2. Constructing the appropriate automaton

In this section we construct a finite-state automaton for a triple
$(\Gamma,\mathcal{X},\mathcal{X}_{\ast})$ in $\mathfrak{X}$, our main result
being Proposition 5.9. Given such a triple, our first step is the construction
of a cubulation for $\Gamma$ that simultaneously encodes the actions on
$\mathcal{X}$ and $\mathcal{X}_{\ast}$. This is the content of the next lemma.

######  Lemma 5.7.

Given $(\Gamma,\mathcal{X},\mathcal{X}_{\ast})\in\mathfrak{X}$ there exists a
proper, cocompact, and essential action of $\Gamma$ on a ${\rm CAT}(0)$ cube
complex $\mathcal{Z}$, $\Gamma$-invariant subsets
$\mathbb{W},\mathbb{W}_{\ast}\subset\mathbb{H}(\mathcal{Z})$, and a finite
index subgroup $\overline{\Gamma}<\Gamma$ satisfying the following.

  * •

Let $\hat{\mathcal{X}}=\mathcal{Z}(\mathbb{W})$ and
$\hat{\mathcal{X}}_{\ast}=\mathcal{Z}(\mathbb{W}_{\ast})$. Then
$\hat{\mathcal{X}}$ and $\hat{\mathcal{X}}_{\ast}$ embed
$\Gamma$-equivariantly as convex subcomplexes of $\mathcal{X}$ and
$\mathcal{X}_{\ast}$ respectively. In particular, the triple
$(\Gamma,\hat{\mathcal{X}},\hat{\mathcal{X}}_{\ast})$ belongs to
$\mathfrak{X}$ and we have the equalities
$\ell_{\mathcal{X}}=\ell_{\hat{\mathcal{X}}}$ and
$\ell_{\mathcal{X}_{\ast}}=\ell_{\hat{\mathcal{X}}_{\ast}}$.

  * •

The action of $\overline{\Gamma}$ on both $\mathcal{Z}$ and
$\hat{\mathcal{X}}$ is co-special.

###### Proof.

By [17, Prop. 3.5] let $\hat{\mathcal{X}}$ and $\hat{\mathcal{X}}_{\ast}$ be
the $\Gamma$-essential cores of $\mathcal{X}$ and $\mathcal{X}_{\ast}$
respectively, which $\Gamma$-equivariantly embed in $\mathcal{X}$ and
$\mathcal{X}_{\ast}$ as convex subcomplexes.

We claim that there exists a cubulation $\mathcal{Z}^{\prime}$ of $\Gamma$ and
$\Gamma$-invariant subsets
$\mathbb{W},\mathbb{W}_{\ast}\subset\mathbb{H}(\mathcal{Z}^{\prime})$ so that
$\hat{\mathcal{X}}$ and $\hat{\mathcal{X}}_{\ast}$ are $\Gamma$-equivariantly
isometric to $\mathcal{Z}^{\prime}(\mathbb{W})$ and
$\mathcal{Z}^{\prime}(\mathbb{W}_{\ast})$. Under the additional assumption
that the action on $\mathcal{X}_{\ast}$ is proper, this is the content of the
implication $(3)\Rightarrow(4)$ in [30, Thm. 2.15], so we just sketch how to
adapt the proof of this implication to the general case.

The way $\mathcal{Z}^{\prime}$ is constructed in [30, Thm. 2.15] is by finding
a $\Gamma$-invariant and co-finite _median subalgebra_
$M\subset\hat{\mathcal{X}}^{0}\times\hat{\mathcal{X}}_{\ast}^{0}$ containing
the product $K\times K_{\ast}$ for $K,K_{\ast}$ finite sets such that $\Gamma
K=\hat{\mathcal{X}}^{0}$ and $\Gamma K_{\ast}=\hat{\mathcal{X}}_{\ast}^{0}$.
In the case the action on $\hat{\mathcal{X}}_{\ast}$ is proper, this follows
from local finiteness of $\hat{\mathcal{X}}\times\hat{\mathcal{X}}_{\ast}$ and
the existence of some $\Gamma$-invariant and cofinite median subalgebra
$N\subset\hat{\mathcal{X}}^{0}\times\hat{\mathcal{X}}_{\ast}^{0}$. On the
other hand, the existence of such an algebra $N$ follows from the implication
$(3)\Rightarrow(1)$ in [29, Prop. 7.9]. For this proposition, the assumption
is that the action of $\Gamma$ on $\hat{\mathcal{X}}_{\ast}$ is essential and
has only finitely many orbits of hyperplanes, and in that case $N$ is median
algebra generated by the $\Gamma$-orbit of any vertex in
$\hat{\mathcal{X}}^{0}\times\hat{\mathcal{X}}_{\ast}^{0}$. However, the same
argument in the proof of [29, Prop. 7.9] implies that the median algebra
generated by the $\Gamma$-translates of _any_ finite subset $\hat{K}$ of
$\hat{\mathcal{X}}^{0}\times\hat{\mathcal{X}}_{\ast}^{0}$ is cofinite (this
can be done by proving the appropriate generalization of [29, Lem. 7.11] so
that the Claim in the proof of [29, Prop. 7.9] still holds). In particular, if
the action of $\Gamma$ on $\hat{\mathcal{X}}_{\ast}$ is cocompact, we can
choose $\hat{K}=K\times K_{\ast}$ as above, and then $\mathcal{Z}^{\prime}$
can be constructed from $N$ as in the rest of the proof of [30, Thm. 2.15].

To finish the proof of the first assertion, note that the action of $\Gamma$
on $\mathcal{Z}^{\prime}$ may not be essential, so instead we consider the
projection quotient
$\mathcal{Z}=\mathcal{Z}^{\prime}(\mathbb{W}\cup\mathbb{W}_{\ast})$, which is
essential and cocompact since the action of $\Gamma$ on both
$\hat{\mathcal{X}}$ and $\hat{\mathcal{X}}_{\ast}$ is essential and the action
on $\mathcal{Z}^{\prime}$ is cocompact. The complex $\mathcal{Z}$ still
$\Gamma$-equivariantly projects onto $\hat{\mathcal{X}}$ and
$\hat{\mathcal{X}}_{\ast}$, so the action of $\Gamma$ on $\mathcal{Z}$ is
proper because the action of $\Gamma$ on $\hat{\mathcal{X}}$ is proper.

To prove the second assertion, note that by [30, Thm. 2.15] the actions of
$\Gamma$ on $\hat{\mathcal{X}}$ and $\mathcal{Z}$ have the same sets of
convex-cocompact subgroups, so any hyperplane stabilizer for the action of
$\Gamma$ on $\mathcal{Z}$ will be convex-cocompact with respect to
$\hat{\mathcal{X}}$. But the action of $\Gamma$ on $\hat{\mathcal{X}}$ is
virtually co-special (it is a convex core for $\Gamma$ acting on
$\mathcal{X}$), so $\mathcal{Z}$ is virtually co-special by Lemma 5.3.
Finally, co-specialness is preserved under taking finite-index subgroups, so
we can choose $\overline{\Gamma}$ so that both quotients
$\overline{\Gamma}\backslash\mathcal{Z}$ and
$\overline{\Gamma}\backslash\hat{\mathcal{X}}$ are special. ∎

In virtue of the lemma above, throughout the rest of the section we will work
under the following convention.

######  Convention 5.8.

$\Gamma$ is a non-virtually cyclic group acting properly, cocompactly and
essentially on the ${\rm CAT}(0)$ cube complex $\mathcal{Z}$, and
$\mathbb{W}\subset\mathbb{H}(\mathcal{Z})$ is a $\Gamma$-invariant subset such
that the action of $\Gamma$ on $\mathcal{X}=\mathcal{Z}(\mathbb{W})$ is
proper, cocompact and essential. Let $\phi:\mathcal{Z}\rightarrow\mathcal{X}$
be the restriction quotient.

Also, let $\overline{\Gamma}<\Gamma$ be a finite index subgroup such that the
quotients $\overline{\mathcal{Z}}=\overline{\Gamma}\backslash\mathcal{Z}$ and
$\overline{\mathcal{X}}=\overline{\Gamma}\backslash\mathcal{X}$ are special
cube complexes. We fix a base vertex $\widetilde{o}\in\mathcal{Z}$ and set
$o=\phi(\widetilde{o})\in\mathcal{X}$.

Let $S_{\mathcal{Z}}$ and $S_{\mathcal{X}}$ be the set of oriented hyperplanes
in $\overline{\mathcal{Z}}$ and $\overline{\mathcal{X}}$ respectively. By
specialness all the hyperplanes in $\overline{\mathcal{Z}}$ and
$\overline{\mathcal{X}}$ are 2-sided, so there exist two orientations for each
hyperplane. Since each hyperplane in $S_{\mathcal{X}}$ corresponds to a
$\overline{\Gamma}$-orbit of oriented walls in
$\mathbb{W}\subset\mathbb{H}(\mathcal{Z})$, there is a natural injection of
$S_{\mathcal{X}}$ into $S_{\mathcal{Z}}$, so often we will consider
$S_{\mathcal{X}}$ as a subset of $S_{\mathcal{Z}}$. The _label_ of an oriented
hyperplane in $\mathcal{Z}$ (resp. $\mathcal{X}$) is its projection in
$\overline{\mathcal{Z}}$ (resp. $\overline{\mathcal{X}}$).

We say that a word $w=\mathfrak{h}_{1}\cdots\mathfrak{h}_{n}$ in
$(S_{\mathcal{Z}})^{\ast}$ is _represented_ by a (combinatorial) path
$\gamma=(\gamma_{0},\dots,\gamma_{n})$ in $\mathcal{Z}$ if for each $i$ the
oriented hyperplane $\mathfrak{h}_{i}$ is the image in
$\overline{\mathcal{Z}}$ of the oriented hyperplane dual to the edge from
$\gamma_{i-1}$ to $\gamma_{i}$. Similarly, we define when a word in
$(S_{\mathcal{X}})^{\ast}$ is represented by a path in $\mathcal{X}$. A
consequence of specialness is that if a word is represented by two paths with
the same initial vertex, then the paths must coincide.

The next proposition gives us a finite-state automaton over $S_{\mathcal{X}}$
that keeps track of the action of $\overline{\Gamma}$ on both $\mathcal{X}$
and $\mathcal{Z}$.

######  Proposition 5.9.

There exists a language $L_{\mathcal{X}}\subset(S_{\mathcal{X}})^{\ast}$
parametrized by the pruned finite-state automaton

$\mathcal{A}_{\mathcal{X}}=(\mathcal{G}_{\mathcal{X}}=(V_{\mathcal{X}},E_{\mathcal{X}}),\pi_{\mathcal{X}},I_{\mathcal{X}},V_{\mathcal{X}})$

satisfying the following.

  1. (1)

There exists $C\geq 1$ such that any $w\in L_{\mathcal{X}}$ is represented by
at most $C$ paths in $\mathcal{G}_{\mathcal{X}}$ starting at an initial state.

  2. (2)

Every $w\in L_{\mathcal{X}}$ is represented by a unique combinatorial geodesic
$\gamma_{w}\subset\mathcal{X}$ starting at the vertex $o$. We let
$\tau_{\mathcal{X}}(w)$ denote the final vertex of $\gamma_{w}$.

  3. (3)

The map $\tau_{\mathcal{X}}:L_{\mathcal{X}}\rightarrow\mathcal{X}^{0}$ is a
bijection.

Moreover, there exist maps
$\Psi:V_{\mathcal{X}}\rightarrow(S_{\mathcal{Z}}\backslash
S_{\mathcal{X}})^{\ast}$ and
$\Xi:V_{\mathcal{X}}\rightarrow\overline{\mathcal{X}}^{0}$ satisfying the
following.

  1. (4)

If $w\in L_{\mathcal{X}}$ is represented by the path
$\omega=(v_{0}\xrightarrow{e_{1}}v_{1}\cdots\xrightarrow{e_{n}}v_{n})$ in
$\mathcal{G}_{\mathcal{X}}$ starting at an initial state, then the
concatenation

$\alpha(\omega):=\Psi(v_{0})\pi_{\mathcal{X}}(e_{1})\Psi(v_{1})\cdots\pi_{\mathcal{X}}(e_{n})\in(S_{\mathcal{Z}})^{*}$
(5.1)

can be represented by a unique geodesic path
$\widetilde{\gamma}_{\alpha(\omega)}$ in $\mathcal{Z}$ with initial vertex
$\widetilde{o}$ and final vertex $\tau_{\mathcal{Z}}(\alpha(\omega))$, so that
$\phi(\tau_{\mathcal{Z}}(\alpha(\omega)))=\tau_{\mathcal{X}}(w)$.

  2. (5)

If $w\in L_{\mathcal{X}}$ is represented by the path $\omega=(v_{0}\rightarrow
v_{1}\cdots\rightarrow v_{n})$ in $\mathcal{G}_{\mathcal{X}}$ starting at an
initial state, then the path $\gamma_{w}=(\gamma_{0},\dots,\gamma_{n})$ in
$\mathcal{X}$ projects to $(\Xi(v_{0}),\dots,\Xi(v_{n}))$ in
$\overline{\mathcal{X}}$.

We start the construction of $\mathcal{A}_{\mathcal{X}}$ by considering a
regular language $L_{\mathcal{Z}}\subset(S_{\mathcal{Z}})^{\ast}$
parametrizing geodesics in $\mathcal{Z}$. For that we follow Sections 5.2 and
5.3 in [47]. More precisely, there exists a deterministic pruned finite-state
automaton

$\mathcal{A}_{\mathcal{Z}}=(\mathcal{G}_{\mathcal{Z}}=(V_{\mathcal{Z}},E_{\mathcal{Z}}),\pi_{\mathcal{Z}},\\{\ast_{\mathcal{Z}}\\},V_{\mathcal{Z}})$

over $S_{\mathcal{Z}}$ parametrizing the language $L_{\mathcal{Z}}$ and
satisfying:

  * •

every $\widetilde{w}\in L_{\mathcal{Z}}$ is represented by a unique geodesic
path $\widetilde{\gamma}_{\widetilde{w}}$ in $\mathcal{Z}$ starting at
$\widetilde{o}$ and ending at the vertex $\tau_{\mathcal{Z}}(\widetilde{w})$;
and,

  * •

the map $\tau_{\mathcal{Z}}:L_{\mathcal{Z}}\rightarrow\mathcal{Z}^{0}$ is a
bijection.

######  Remark 5.10.

The language constructed in [47] actually depends on an injection of
$\overline{\Gamma}$ into a right-angled Artin group $A_{G}$ inducing a
$\overline{\Gamma}$-equivariant isometric embedding of $\mathcal{Z}$ into
$R_{G}$ as a convex subcomplex, where $R_{G}$ is the universal cover of the
Salvetti complex $\overline{R}_{G}$ associated to $G$. In that case, the
language obtained is over the alphabet of oriented hyperplanes of
$\overline{R}_{G}$. The language $L_{\mathcal{Z}}$ described above is a
particular case of this construction, when we consider the local isometric
immersion
$\overline{\mathcal{Z}}\rightarrow\overline{R}_{G_{\overline{\mathcal{Z}}}}$
for $G_{\overline{\mathcal{Z}}}$ being the _crossing graph_ of
$\overline{\mathcal{Z}}$. For this immersion there is a natural bijection
between $S_{\mathcal{Z}}$ and the set of oriented hyperplanes in
$\overline{R}_{G_{\overline{\mathcal{Z}}}}$, see for instance [39, Lem. 4.1].

We use the automaton $\mathcal{A}_{\mathcal{Z}}$ to produce a language
$L_{\mathcal{X}}$ over the alphabet $S_{\mathcal{X}}$. We do this by first
constructing an automaton

$\hat{\mathcal{A}}_{\mathcal{X}}=(\hat{\mathcal{G}}_{\mathcal{X}}=(\hat{V}_{\mathcal{X}},\hat{E}_{\mathcal{X}}),\hat{\pi}_{\mathcal{X}},\hat{I}_{\mathcal{X}},\hat{V}_{\mathcal{X}})$

as follows.

######  Definition 5.11.

Let $\hat{V}_{\mathcal{X}}$ be the set of finite directed paths (possibly of
length 0) in $\mathcal{G}_{\mathcal{Z}}$ of the form
$\omega=(v_{0}\xrightarrow{e_{1}}\cdots\xrightarrow{e_{n}}v_{n})$ and
satisfying:

  * •

$\pi_{\mathcal{Z}}(e_{i})\in S_{\mathcal{Z}}\backslash S_{\mathcal{X}}$ for
every $1\leq i\leq n$;

  * •

either $v_{0}=\ast_{\mathcal{Z}}$ or there exists an edge in $E_{\mathcal{Z}}$
with label in $S_{\mathcal{X}}$ and final vertex $v_{0}$; and,

  * •

either there exists an edge in $E_{\mathcal{Z}}$ with label in
$S_{\mathcal{X}}$ and initial vertex $v_{n}$ or there are no edges in
$E_{\mathcal{Z}}$ with initial vertex $v_{n}$.

We consider an edge $\hat{e}$ from the vertex $\omega$ to the vertex
$\omega^{\prime}$ in $\hat{V}_{\mathcal{X}}$ if there exists an edge $e\in
E_{\mathcal{Z}}$ with $\pi_{\mathcal{Z}}(e)\in S_{\mathcal{X}}$ and such that
the concatenation $\omega e\omega^{\prime}$ is a path in
$\mathcal{G}_{\mathcal{Z}}$. We define
$\hat{\pi}_{\mathcal{X}}(\hat{e}):=\pi_{\mathcal{Z}}(e)$ and let
$\hat{E}_{\mathcal{X}}$ be the set of all of the edges defined in this way.
Finally, a vertex of $\hat{V}_{\mathcal{X}}$ is an initial state if its
initial vertex (as a path in $\mathcal{G}_{\mathcal{Z}}$) is
$\ast_{\mathcal{Z}}$. We let $\hat{I}_{\mathcal{X}}$ be the set of all the
initial states.

######  Lemma 5.12.

The set $\hat{V}_{\mathcal{X}}$ is finite and non-empty. Therefore,
$\hat{\mathcal{A}}_{\mathcal{X}}$ defines a pruned finite-state automaton over
$S_{\mathcal{X}}$.

###### Proof.

The set $S_{\mathcal{X}}$ is non-empty because $\Gamma$ is non-elementary and
$\mathcal{X}$ is essential, and since $\mathcal{A}_{\mathcal{Z}}$ is pruned we
can find a vertex in $\hat{I}_{\mathcal{X}}$, so that $\hat{V}_{\mathcal{X}}$
is non-empty.

To show finiteness, let $M$ be the maximum cardinality of a preimage
$\phi^{-1}(x)\cap\mathcal{Z}^{0}$ among $x\in\mathcal{X}^{0}$, which is finite
since $\phi$ is $\Gamma$-invariant and the action of $\Gamma$ on $\mathcal{Z}$
is cocompact. If
$\omega=(v_{0}\xrightarrow{e_{1}}\cdots\xrightarrow{e_{n}}v_{n})$ is a vertex
in $\hat{V}_{\mathcal{X}}$, the fact that $\mathcal{A}_{\mathcal{Z}}$ is
pruned implies the existence of a geodesic path $\widetilde{\gamma}$ in
$\mathcal{Z}$ representing the word
$\pi_{\mathcal{Z}}(e_{1})\cdots\pi_{\mathcal{Z}}(e_{1})\in(S_{\mathcal{Z}}\backslash
S_{\mathcal{X}})^{\ast}\subset(S_{\mathcal{X}})^{\ast}$. Since $\phi$
collapses the hyperplanes not belonging to $\mathbb{W}$, the image
$\phi(\widetilde{\gamma})$ consists of a single point, implying that $n+1\leq
M$. We conclude that every vertex in $\hat{V}_{\mathcal{X}}$ has uniformly
bounded length as a path in $\mathcal{G}_{\mathcal{Z}}$, so
$\hat{V}_{\mathcal{X}}$ is finite because $\mathcal{G}_{\mathcal{Z}}$ is.

Finally, $\mathcal{A}_{\mathcal{Z}}$ being pruned implies that
$\hat{\mathcal{A}}_{\mathcal{X}}$ is pruned, and by construction this
automaton is over the alphabet $S_{\mathcal{X}}$. ∎

######  Definition 5.13.

We let $L_{\mathcal{X}}\subset(S_{\mathcal{X}})^{*}$ be the language
parametrized by $\hat{\mathcal{A}}_{\mathcal{X}}$.

If
$\hat{\omega}=(\omega_{0}\xrightarrow{\hat{e}_{1}}\cdots\xrightarrow{\hat{e}_{n}}\omega_{n})$
is a path in $\hat{\mathcal{G}}_{\mathcal{X}}$, then the concatenation

$c(\hat{\omega}):=\omega_{0}e_{1}\cdots\omega_{n-1}e_{n}$ (5.2)

is a path in $\mathcal{G}_{\mathcal{Z}}$. Let
$\hat{\alpha}(\hat{\omega})\in(S_{\mathcal{Z}})^{\ast}$ be the word
represented by $c(\hat{\omega})$.

######  Lemma 5.14.

  1. (1)

If $\hat{\omega},\hat{\omega}^{\prime}$ are paths in
$\hat{\mathcal{G}}_{\mathcal{X}}$ starting at an initial state and
representing the same word $w\in L_{\mathcal{X}}$, then
$\phi(\tau_{\mathcal{Z}}(\hat{\alpha}(\hat{\omega})))=\phi(\tau_{\mathcal{Z}}(\hat{\alpha}(\hat{\omega}^{\prime})))\in\mathcal{X}^{0}$.
We denote this vertex by $\tau_{\mathcal{X}}(w)$.

  2. (2)

Any $w$ in $L_{\mathcal{X}}$ is represented by a unique geodesic path
$\gamma_{w}$ in $\mathcal{X}$ starting at $o$ and ending at
$\tau_{\mathcal{X}}(w)$.

  3. (3)

The map $\tau_{\mathcal{X}}:L_{\mathcal{X}}\rightarrow\mathcal{X}^{0}$ is a
bijection.

###### Proof.

By induction on the length of $w$ we will prove simultaneously assertion (1)
and that $d_{\mathcal{X}}(o,\tau_{\mathcal{X}}(w))$ equals the length of $w$.
Suppose that $w$ has length $n$ and is represented by the paths

$\hat{\omega}=(\omega_{0}\xrightarrow{\hat{e}_{1}}\cdots\xrightarrow{\hat{e}_{n}}\omega_{n})\text{
and
}\hat{\omega}^{\prime}=(\omega_{0}^{\prime}\xrightarrow{\hat{e}_{1}^{\prime}}\cdots\xrightarrow{\hat{e}_{n}^{\prime}}\omega_{n}^{\prime})$

in $\hat{\mathcal{G}}_{\mathcal{X}}$. If $n=0$ then
$\hat{\alpha}(\hat{\omega})=\omega_{0}$ has no letters in $S_{\mathcal{X}}$,
and hence the projection of $\widetilde{\gamma}_{\hat{\alpha}(\hat{\omega})}$
under $\phi$ consists of a single vertex, which must be $o$. As the same
happens for $\omega^{\prime}$, this solves the base case.

If $n\geq 1$ we consider
$\hat{\xi}=(\omega_{0}\xrightarrow{\hat{e}_{1}}\cdots\xrightarrow{\hat{e}_{n-1}}\omega_{n-1})$
and
$\hat{\xi}^{\prime}=(\omega_{0}^{\prime}\xrightarrow{\hat{e}_{1}^{\prime}}\cdots\xrightarrow{\hat{e}_{n-1}^{\prime}}\omega_{n-1}^{\prime})$.
Our inductive assumption implies that
$\phi(\tau_{\mathcal{Z}}(\hat{\alpha}(\hat{\xi})))=\phi(\tau_{\mathcal{Z}}(\hat{\alpha}(\hat{\xi}^{\prime})))=:x$,
so that no hyperplane with label in $S_{\mathcal{X}}$ separates
$\tau_{\mathcal{Z}}(\hat{\alpha}(\hat{\xi}))$ and
$\tau_{\mathcal{Z}}(\hat{\alpha}(\hat{\xi}^{\prime}))$. Since
$\overline{\mathcal{X}}$ is special there exists at most one edge in
$\mathcal{X}$ with initial vertex $x$ and dual to a hyperplane with label
$\mathfrak{h}=\hat{\pi}_{\mathcal{X}}(\hat{e}_{n})=\hat{\pi}_{\mathcal{X}}(\hat{e}_{n}^{\prime})\in
S_{\mathcal{X}}$. But $\phi$ is injective on $\mathbb{W}$, so that the
hyperplane labeled $\mathfrak{h}$ that separates
$\tau_{\mathcal{Z}}(\hat{\alpha}(\hat{\xi}))$ and
$\tau_{\mathcal{Z}}(\hat{\alpha}(\hat{\omega}))$ in $\mathcal{Z}$ is the same
as the hyperplane labeled $\mathfrak{h}$ that separates
$\tau_{\mathcal{Z}}(\hat{\alpha}(\hat{\xi}^{\prime}))$ and
$\tau_{\mathcal{Z}}(\hat{\alpha}(\hat{\omega}^{\prime}))$. Since this is the
only hyperplane with a label in $S_{\mathcal{X}}$ that separates these pairs,
we conclude that every hyperplane separating
$\tau_{\mathcal{Z}}(\hat{\alpha}(\hat{\omega}))$ and
$\tau_{\mathcal{Z}}(\hat{\alpha}(\hat{\omega}^{\prime}))$ has a label in
$S_{\mathcal{Z}}\backslash S_{\mathcal{X}}$, which gives us
$\phi(\tau_{\mathcal{Z}}(\hat{\alpha}(\hat{\omega})))=\phi(\tau_{\mathcal{Z}}(\hat{\alpha}(\hat{\omega}^{\prime})))$.
Moreover, if $w^{\prime}\in L_{\mathcal{X}}$ is the word represented by
$\hat{\xi}$, then by induction we have
$d_{\mathcal{X}}(o,\tau_{\mathcal{X}}(w^{\prime}))=n-1$ and
$d_{\mathcal{X}}(\tau_{\mathcal{X}}(w^{\prime}),\tau_{\mathcal{X}}(\xi))=1$.
But all these points belong to the projection under $\phi$ of the geodesic
$\widetilde{\gamma}_{\hat{\alpha}(\hat{\omega})}$, so Remark 2.2 implies that
$d_{\mathcal{X}}(o,\tau_{\mathcal{X}}(w))=n$ and concludes the proof by
induction, proving (1).

It is not hard to see that if $w=\mathfrak{h}_{1}\cdots\mathfrak{h}_{n}\in
L_{\mathcal{X}}$ then

$\gamma_{w}:=(o,\tau_{\mathcal{X}}(\mathfrak{h}_{1}),\tau_{\mathcal{X}}(\mathfrak{h}_{1}\mathfrak{h}_{2}),\dots,\tau_{\mathcal{X}}(\mathfrak{h}_{1}\cdots\mathfrak{h}_{n}))$

is the unique geodesic representing $w$ in $\mathcal{X}$ and starting at $o$,
which settles (2).

To prove (3), injectivity can be deduced by induction on the length of words
in $L_{\mathcal{X}}$ combined with the fact that no two distinct edges with
the same initial vertex in $\mathcal{X}$ are dual to hyperplanes with the same
label in $S_{\mathcal{X}}$. This last statement is true by specialness of
$\overline{\mathcal{X}}$.

To prove surjectivity, let $x\in\mathcal{X}^{0}$ and consider
$\widetilde{w}\in L_{\mathcal{Z}}$ such that
$\phi(\tau_{\mathcal{Z}}(\widetilde{w}))=x$. Such an $\widetilde{w}$ exists
because both $\tau_{\mathcal{Z}}$ and $\phi$ are surjective. We write
$\widetilde{w}=w_{0}e_{1}\cdots e_{n}w_{n},$ where each $e_{i}$ is a letter in
$S_{\mathcal{X}}$ and each $w_{i}$ is a (possibly empty) word in
$(S_{\mathcal{Z}}\backslash S_{\mathcal{X}})^{\ast}$. Then
$\widetilde{w}^{\prime}:=w_{0}e_{1}\cdots w_{n-1}e_{n}$ equals
$\hat{\alpha}(\hat{\omega})$ for some path $\hat{\omega}$ in
$\hat{\mathcal{G}}_{\mathcal{X}}$ representing the word $w\in
L_{\mathcal{X}}$, for which
$\tau_{\mathcal{X}}(w)=\phi(\tau_{\mathcal{Z}}(\widetilde{w}^{\prime}))=\phi(\tau_{\mathcal{Z}}(\widetilde{w}))=x$.
∎

######  Lemma 5.15.

There exists $C\geq 1$ such that every $w\in L_{\mathcal{X}}$ is represented
by at most $C$ paths in $\hat{\mathcal{G}}_{\mathcal{X}}$ starting at an
initial vertex.

###### Proof.

Since $\tau_{\mathcal{Z}}$ is injective and $\phi$ is uniformly finite-to-one
when restricted to vertices, it is enough to prove that the assignment
$\hat{\omega}\mapsto\hat{\alpha}(\hat{\omega})$ from the paths in
$\hat{\mathcal{G}}_{\mathcal{X}}$ starting at an initial vertex into
$L_{\mathcal{Z}}$ is uniformly finite-to one. To show this, note that such
$\hat{\omega}$ is completely determined by its concatenation $c(\hat{\omega})$
in $\mathcal{G}_{\mathcal{Z}}$ (defined in (5.2)) and its final vertex in
$\hat{V}_{\mathcal{X}}$, and that $c(\hat{\omega})$ is completely determined
by $\hat{\alpha}(\hat{\omega})$ since $\mathcal{A}_{\mathcal{Z}}$ is
deterministic. The lemma then follows from Lemma 5.12. ∎

###### Proof of Proposition 5.9.

First we note that $\overline{\mathcal{X}}^{1}$ can be seen as the finite-
state automaton

$\overline{\mathcal{X}}^{1}=((\overline{\mathcal{X}}^{0},S_{\mathcal{X}}),\textnormal{Id}_{S_{\mathcal{X}}},\\{\overline{o}\\},\overline{\mathcal{X}}^{0})$

over $S_{\mathcal{X}}$, where $\overline{o}$ is the image of $o$ under the
quotient $\mathcal{X}\rightarrow\overline{\mathcal{X}}$. This automaton is
deterministic since $\overline{\mathcal{X}}$ is special.

Let
$\mathcal{A}_{\mathcal{X}}=(\mathcal{G}_{\mathcal{X}}=(V_{\mathcal{X}},E_{\mathcal{X}}),\pi_{\mathcal{X}},I_{\mathcal{X}},V_{\mathcal{X}})$
be the fiber product of $\hat{\mathcal{A}}_{\mathcal{X}}$ and
$\overline{\mathcal{X}}^{1}$. That is, in
$\hat{V}_{\mathcal{X}}\times\overline{\mathcal{X}}^{0}$ consider a directed
edge from $(\hat{\omega},\overline{x})$ to
$(\hat{\omega}^{\prime},\overline{x}^{\prime})$ if there exists an edge
$\hat{e}$ from $\omega$ to $\omega^{\prime}$ such that
$\hat{\mathcal{G}}_{\mathcal{X}}$ and $\hat{\pi}_{\mathcal{X}}(\hat{e})$ is
the directed hyperplane dual to an edge from $\overline{x}$ to
$\overline{x}^{\prime}$ in $\overline{\mathcal{X}}$ (so that
$\overline{x},\overline{x}^{\prime}$ must be adjacent). By abuse of notation
we will call this edge $e$ and define
$\pi_{\mathcal{X}}(e):=\hat{\pi}_{\mathcal{X}}(\hat{e})$. Let
$I_{\mathcal{X}}=\hat{I}_{\mathcal{X}}\times\\{\overline{o}\\}$ be the set of
initial states of $\mathcal{G}_{\mathcal{X}}$ and let
$V_{\mathcal{X}}\subset\hat{V}_{\mathcal{X}}\times\overline{\mathcal{X}}^{0}$
be the set of all the vertices in some directed path in
$\hat{V}_{\mathcal{X}}\times\overline{\mathcal{X}}^{0}$ starting at an initial
state. Let $E_{\mathcal{X}}$ be the set of all the directed edges between
vertices in $V_{\mathcal{X}}$ as defined above. Clearly
$\mathcal{A}_{\mathcal{X}}$ is pruned and finite.

There exists a label-preserving map $\mathfrak{p}$ from the set of paths in
$\mathcal{G}_{\mathcal{X}}$ starting at an initial state into the set of paths
in $\hat{\mathcal{G}}_{\mathcal{X}}$ starting at an initial state, which sends
the path
$((\omega_{0},\overline{x}_{0})\xrightarrow{e_{1}}\cdots\xrightarrow{e_{n}}(\omega_{n},\overline{x}_{n}))$
to the path
$\hat{\omega}=(\omega_{0}\xrightarrow{\hat{e}_{1}}\cdots\xrightarrow{\hat{e}_{n}}\omega_{n})$.
The map $\mathfrak{p}$ is a bijection since the sequence
$\overline{x}_{0},\dots,\overline{x}_{n}$ is the image of $\gamma_{w}$ under
$\mathcal{X}\rightarrow\overline{\mathcal{X}}$, where $w$ is the word
represented by $\hat{\omega}$. In particular, the language parametrized by
$\mathcal{A}_{\mathcal{X}}$ is precisely $L_{\mathcal{X}}$, so Lemma 5.15
implies Item (1). Also, Items (2) and (3) follow from Lemma 5.14.

For Item (4) we consider the map
$\Psi:V_{\mathcal{X}}\rightarrow(S_{\mathcal{Z}}\backslash
S_{\mathcal{X}})^{\ast}$ that sends the vertex $(\omega,\overline{x})$ to the
word represented by $\omega$, seen as a path in $\mathcal{G}_{\mathcal{Z}}$.
From the definition of $\hat{\mathcal{G}}_{\mathcal{X}}$ it is clear that for
the path $\omega=(v_{0}\xrightarrow{e_{1}}\cdots\xrightarrow{e_{n}}v_{n})$ in
$\mathcal{G}_{\mathcal{X}}$ starting at an initial state, the concatenation

$\alpha(\omega):=\hat{\alpha}(\mathfrak{p}(\omega))=\Psi(v_{0})\pi_{\mathcal{X}}(e_{1})\Psi(v_{1})\cdots\pi_{\mathcal{X}}(e_{n})$

belongs to $L_{\mathcal{Z}}$, so it is represented by the geodesic path
$\widetilde{\gamma}_{\alpha(\omega)}$ in $\mathcal{Z}$ starting at
$\widetilde{o}$. The word $w$ represented by $\omega$ is also represented by
$\mathfrak{p}(\omega)$, so Lemma 5.14 implies that
$\tau_{\mathcal{X}}(w)=\phi(\tau_{\mathcal{Z}}(\alpha(\omega)))$.
$\mathcal{A}_{\mathcal{Z}}$ being deterministic implies that
$\widetilde{\gamma}_{\alpha(\omega)}$ is the unique geodesic in $\mathcal{Z}$
starting at $\widetilde{o}$ and representing $w$.

Finally, we define $\Xi:V_{\mathcal{X}}\rightarrow\overline{\mathcal{X}}^{0}$
as the coordinate projection $\Xi(\omega,\overline{x})=\overline{x}$, and the
same argument for the proof that $\mathfrak{p}$ is a bijection implies Item
(5). ∎

##  6\. Proof of the main theorems

In this section we prove our main results about pairs of actions on ${\rm
CAT}(0)$ cube complexes from the introduction. They are consequences of more
general statements, given by Theorems 6.1 and 6.2. The strategy is to use the
automaton from Proposition 5.9 to define an appropriate suspension flow, and
then use Proposition 6.8 to relate the Manhattan curves with pressure
functions for potentials on this suspension. This relation will allow us to
use the tools from symbolic dynamics and thermodynamic formalism discussed in
Section 3 to deduce our main results.

The following are the main theorems of the section, and they are proven in
Section 6.2. For their statements, we interpret the quantities ${\rm
Dil}(\mathcal{X},\mathcal{X}_{\ast})^{-1}$ and
$v_{\mathcal{X}^{\mathfrak{w}}}/v_{\mathcal{X}^{\mathfrak{w}_{\ast}}_{\ast}}$
as zero if the action of $\Gamma$ on $\mathcal{X}_{\ast}$ is not proper.

######  Theorem 6.1.

Let $(\Gamma,\mathcal{X},\mathcal{X}_{\ast})\in\mathfrak{X}$ and let
$\mathfrak{w},\mathfrak{w}_{\ast}$ be $\Gamma$-invariant orthotope structures
on $\mathcal{X}$ and $\mathcal{X}_{\ast}$ respectively. Then the Manhattan
curve
$\theta_{\mathcal{X}^{\mathfrak{w}_{\ast}}_{\ast}/\mathcal{X}^{\mathfrak{w}}}:{\mathbb{R}}\rightarrow{\mathbb{R}}$
is convex, decreasing, and analytic. In addition, the following limit exists
and equals
$-\theta^{\prime}_{\mathcal{X}^{\mathfrak{w}_{\ast}}_{\ast}/\mathcal{X}^{\mathfrak{w}}}(0)$:

$\tau(\mathcal{X}^{\mathfrak{w}_{\ast}}_{\ast}/\mathcal{X}^{\mathfrak{w}}):=\lim_{T\to\infty}\frac{1}{\\#\mathfrak{C}_{\mathcal{X}^{\mathfrak{w}}}(T)}\sum_{[g]\in\mathfrak{C}_{\mathcal{X}^{\mathfrak{w}}}(T)}\frac{\ell^{\mathfrak{w}_{\ast}}_{\mathcal{X}_{\ast}}[g]}{\ell^{\mathfrak{w}}_{\mathcal{X}}[g]}.$

Moreover, we always have

$\tau(\mathcal{X}^{\mathfrak{w}_{\ast}}_{\ast}/\mathcal{X}^{\mathfrak{w}})\geq
v_{\mathcal{X}^{\mathfrak{w}}}/v_{\mathcal{X}^{\mathfrak{w}_{\ast}}_{\ast}}.$

If the action of $\Gamma$ on $\mathcal{X}_{\ast}$ is proper then the following
are equivalent:

  1. (1)

$\theta_{\mathcal{X}^{\mathfrak{w}_{\ast}}_{\ast}/\mathcal{X}^{\mathfrak{w}}}$
is a straight line;

  2. (2)

there exists $\Lambda>0$ such that
$\ell^{\mathfrak{w}}_{\mathcal{X}}[g]=\Lambda\ell^{\mathfrak{w}_{\ast}}_{\mathcal{X}_{\ast}}[g]$
for all $[g]\in{\bf conj}(\Gamma)$; and,

  3. (3)

$\tau(\mathcal{X}^{\mathfrak{w}_{\ast}}_{\ast}/\mathcal{X}^{\mathfrak{w}})=v_{\mathcal{X}^{\mathfrak{w}}}/v_{\mathcal{X}^{\mathfrak{w}_{\ast}}_{\ast}}$.

######  Theorem 6.2.

Let $(\Gamma,\mathcal{X},\mathcal{X}_{\ast})\in\mathfrak{X}$. Then there
exists an analytic function

$\mathcal{I}:[{\rm Dil}(\mathcal{X},\mathcal{X}_{\ast})^{-1},{\rm
Dil}(\mathcal{X}_{\ast},\mathcal{X})]\rightarrow{\mathbb{R}}$

and $C>0$ such that for any $\eta\in({\rm
Dil}(\mathcal{X},\mathcal{X}_{\ast})^{-1},{\rm
Dil}(\mathcal{X}_{\ast},\mathcal{X}))$ we have

$0<\limsup_{T\to\infty}\frac{1}{T}\log\left(\\#\left\\{[g]\in\mathfrak{C}_{\mathcal{X}}(T):|\ell_{\mathcal{X}_{\ast}}[g]-\eta\ell_{\mathcal{X}}[g]|<\frac{C}{T}\right\\}\right)=\mathcal{I}(\eta)\leq
v_{\mathcal{X}}.$ (6.1)

Furthermore, we have equality in the above inequality if and only if
$\eta=\tau(\mathcal{X}_{*}/\mathcal{X})$.

As we noted in the previous section,
$(\Gamma,\mathcal{X},\mathcal{X}_{\ast})\in\mathfrak{X}$ whenever
$\Gamma\in\mathfrak{G}$ and $\mathcal{X},\mathcal{X}_{\ast}$ are cubulations
of $\Gamma$. From this we see that Theorems 6.1 and 6.2 imply Theorems 1.2 and
1.4 from the introduction.

###  6.1. Manhattan curves for pairs of cubulations

In this section we use the finite-state automaton given by Proposition 5.9 to
describe the Manhattan geodesics for a pair of cubulations in terms of
pressure functions. This will allow us to use thermodynamic formalism to prove
our main results in the next section. For this section we keep the notation
from the previous section and assume the following.

######  Convention 6.3.

Let $(\Gamma,\mathcal{X},\mathcal{Z})$ be a triple satisfying Convention 5.8.
Consider a non-empty $\Gamma$-invariant subset
$\mathbb{W}_{\ast}\subset\mathbb{H}(\mathcal{Z})$ and set
$\mathcal{X}_{\ast}=\mathcal{Z}(\mathbb{W}_{\ast})$. Then the action of
$\Gamma$ on $\mathcal{X}_{\ast}$ is cocompact and essential, but not
necessarily proper. Let $\mathfrak{w}$ and $\mathfrak{w}_{\ast}$ be
$\Gamma$-invariant orthotope structures on $\mathcal{X}$ and
$\mathcal{X}_{\ast}$ respectively. We also require the action of $\Gamma$ on
$\mathcal{X}$ to have a contracting element.

Let $S_{\mathcal{X}_{\ast}}\subset S_{\mathcal{Z}}$ be the set of all the
directed hyperplanes in $\overline{\mathcal{Z}}$ whose lifts to $\mathcal{Z}$
correspond to hyperplanes in $\mathbb{W}_{\ast}$, and let
$\phi_{\ast}:\mathcal{Z}\rightarrow\mathcal{X}_{\ast}$ be the projection
quotient with $o_{\ast}=\phi_{\ast}(\widetilde{o})$.

Since the structures $\mathfrak{w},\mathfrak{w}_{\ast}$ are
$\Gamma$-invariant, there exist natural weighting maps
$\overline{\mathfrak{w}},\overline{\mathfrak{w}}_{\ast}:S_{\mathcal{Z}}\rightarrow{\mathbb{R}}$
defined as follows. If $\mathfrak{h}\in S_{\mathcal{X}}\subset
S_{\mathcal{Z}}$ then
$\overline{\mathfrak{w}}(\mathfrak{h})=\mathfrak{w}(\widetilde{\mathfrak{h}})$
for any lift of $\widetilde{\mathfrak{h}}$ in $\mathcal{X}$, and
$\overline{\mathfrak{w}}(\mathfrak{h})=0$ if $\mathfrak{h}\in
S_{\mathcal{Z}}\backslash S_{\mathcal{X}}$. Analogously, if $\mathfrak{h}\in
S_{\mathcal{X}\ast}\subset S_{\mathcal{Z}}$ then
$\overline{\mathfrak{w}}_{\ast}(\mathfrak{h})=\mathfrak{w}_{\ast}(\widetilde{\mathfrak{h}})$
for any lift of $\widetilde{\mathfrak{h}}$ in $\mathcal{X}_{\ast}$, and
$\overline{\mathfrak{w}}_{\ast}(\mathfrak{h})=0$ if $\mathfrak{h}\in
S_{\mathcal{Z}}\backslash S_{\mathcal{X}_{\ast}}$. By abuse of notation we
extend these weightings to
$\overline{\mathfrak{w}},\overline{\mathfrak{w}}_{\ast}:(S_{\mathcal{Z}})^{\ast}\rightarrow{\mathbb{R}}$
by declaring the empty word to have weights 0 and assigning

$\overline{\mathfrak{w}}(\mathfrak{h}_{1}\cdots\mathfrak{h}_{n})=\overline{\mathfrak{w}}(\mathfrak{h}_{1})+\cdots+\overline{\mathfrak{w}}(\mathfrak{h}_{n})\
\text{ and }\
\overline{\mathfrak{w}}_{\ast}(\mathfrak{h}_{1}\cdots\mathfrak{h}_{n})=\overline{\mathfrak{w}}_{\ast}(\mathfrak{h}_{1})+\cdots+\overline{\mathfrak{w}}_{\ast}(\mathfrak{h}_{n})$

for a word $\mathfrak{h}_{1}\cdots\mathfrak{h}_{n}\in(S_{\mathcal{Z}})^{\ast}$
of positive length.

Let $\Sigma^{\ast}$ be the set of all the finite directed paths in
$\mathcal{G}_{\mathcal{X}}$. We can see $\Sigma^{\ast}$ as a set of finite
sequences of edges in $E_{\mathcal{X}}$. Similarly, let
$\Sigma\subset(E_{\mathcal{X}})^{{\mathbb{N}}}$ be the set of all the semi-
infinite directed paths $(e_{i})_{i\geq 1}$ in $\mathcal{G}_{\mathcal{X}}$. We
also let $\sigma:\Sigma\rightarrow\Sigma$ denote the shift map
$\sigma((e_{i})_{i\geq 1})=(e_{i+1})_{i\geq 1}$. For each $n$ we let
$P_{n}(\Sigma^{\ast})\subset\Sigma^{\ast}$ be the subset of all the closed
paths of length $n$, and set $P_{\leq n}(\Sigma^{\ast})=\bigcup_{j\leq
n}{P_{j}(\Sigma^{\ast})}$ and
$P(\Sigma^{\ast})=\bigcup_{j}{P_{j}(\Sigma^{\ast})}$. We will often identify
the set $\operatorname{Fix}_{n}(\Sigma)$ of sequences $\omega\in\Sigma$
satisfying $\sigma^{n}(\omega)=\omega$ with $P_{n}(\Sigma^{\ast})$ via the
truncation $\omega=(e_{1},\dots,e_{n},e_{1},\dots)\mapsto
t_{n}(\omega):=(e_{1},\dots,e_{n})$.

The next definition will be useful for the rest of the section.

######  Definition 6.4.

A combinatorial path $\gamma$ in $\mathcal{X}$ is a _good representative_ of
$\omega\in\Sigma^{\ast}$ if there exists a path $\omega_{0}\in\Sigma^{\ast}$
starting at an initial state and ending at the initial vertex of $\omega$ and
satisfying the following. If $w_{0},w_{0}w\in L_{\mathcal{X}}$ are the words
corresponding to $\omega_{0}$ and $\omega_{0}\omega$ respectively, then
$\gamma$ is the portion of the path $\gamma_{w_{0}w}$ representing $w_{0}w$
from $\gamma^{-}=\tau_{\mathcal{X}}(w_{0})$ to
$\gamma^{+}=\tau_{\mathcal{X}}(w_{0}w)$.

Note that good representatives are geodesic. Also, by Proposition 5.9 (5) any
two good representatives of the same path in $\Sigma^{\ast}$ differ by a
translation by an element in $\overline{\Gamma}$. In consequence, if
$\omega\in P(\Sigma^{\ast})$ then there exists a well-defined conjugacy class
$\beta(\omega)\in{\bf conj}(\overline{\Gamma})$ represented by any
$g\in\overline{\Gamma}$ such that $\gamma^{+}=g\gamma^{-}$ for $\gamma$ a good
representative of $\omega$. Clearly $\omega\in P_{n}(\Sigma^{\ast})$ implies
$\ell_{\mathcal{X}}[\beta(\omega)]=n$.

We can consider lifts of paths in $\Sigma^{\ast}$ to $\mathcal{Z}$. First, we
extend the equation (5.1) to define a map
$\alpha:\Sigma^{\ast}\rightarrow(S_{\mathcal{Z}})^{\ast}$. If $\gamma$ is a
good representative of $\omega\in\Sigma^{\ast}$ defined using the path
$\omega_{0}$ as above, then $\widetilde{\gamma}$ is the portion of
$\widetilde{\gamma}_{\alpha(\omega_{0}\omega)}$ starting at
$\widetilde{\gamma}_{\alpha(\omega_{0})}^{+}$ and ending at
$\widetilde{\gamma}_{\alpha(\omega_{0}\omega)}^{+}$, where
$\widetilde{\gamma}_{\alpha(\omega_{0})}$ and
$\widetilde{\gamma}_{\alpha(\omega_{0}\omega)}$ are given by Proposition 5.9
(4). In this way the path $\widetilde{\gamma}$ represents the word
$\alpha(\omega)$. Different choices of $\omega_{0},\omega_{0}^{\prime}$ may
give different lifts $\widetilde{\gamma},\widetilde{\gamma}^{\prime}$ even if
$\tau_{\mathcal{X}}(w_{0})=\tau_{\mathcal{X}}(w_{0}^{\prime})$, but under this
assumption we have
$\phi(\widetilde{\gamma})=\phi(\widetilde{\gamma}^{\prime})=\gamma$.

A key feature of the automaton $\mathcal{A}_{\mathcal{X}}$ is that it keeps
track of translation lengths for the actions of $\Gamma$ on the cuboid
complexes $\mathcal{X}^{\mathfrak{w}}$ and
$\mathcal{X}_{\ast}^{\mathfrak{w}_{\ast}}$, via the potential on
$(\Sigma,\sigma)$ defined below.

######  Definition 6.5.

Let
$r=r^{\mathfrak{w}}_{\mathcal{X}},\psi=\psi^{\mathfrak{w}_{\ast}}_{\mathcal{X}_{\ast}}:E_{\mathcal{X}}\rightarrow{\mathbb{R}}$
be the functions such that

$r(e)=\overline{\mathfrak{w}}(\pi_{\mathcal{X}}(e))\ \text{ and }\
\psi(e)=\psi(v_{0}\xrightarrow{e}v_{1})=\overline{\mathfrak{w}}_{\ast}(\Psi(v_{0}))+\overline{\mathfrak{w}}_{\ast}(\pi_{\mathcal{X}}(e)),$
(6.2)

where $\Psi$ is the function from Proposition 5.9 (4). By abuse of notation we
extend these functions to potentials $r,\psi:\Sigma\rightarrow{\mathbb{R}}$
via

$r(e_{1},e_{2},\dots)=r(e_{1})\ \text{ and }\
\psi(e_{1},e_{2},\dots)=\psi(e_{1}).$

Clearly $r$ and $\psi$ are constant on 2 cylinders, and $r$ is positive. The
next lemma can be seen as a weak analog of [11, Lem. 3.8] for pairs of word
metrics on hyperbolic groups.

######  Lemma 6.6.

Let $r,\psi:\Sigma\rightarrow{\mathbb{R}}$ be the potentials defined above. If
$n\geq 1$ and $\omega\in\operatorname{Fix}_{n}(\Sigma)$ has truncation
$t_{n}(\omega)\in P_{n}(\Sigma^{\ast})$, then
$\ell_{\mathcal{X}}[\beta(t_{n}(\omega))]=n$ and the $n$th Birkhoff sums at
$\omega$ satisfy

$r^{n}(\omega)=r(\omega)+r(\sigma(\omega))+\cdots+r(\sigma^{n-1}(\omega))=\ell^{\mathfrak{w}}_{\mathcal{X}}[\beta(t_{n}(\omega))]$
(6.3)

and

$\psi^{n}(\omega)=\psi(\omega)+\psi(\sigma(\omega))+\cdots+\psi(\sigma^{n-1}(\omega))=\ell^{\mathfrak{w}_{\ast}}_{\mathcal{X}_{\ast}}[\beta(t_{n}(\omega))].$
(6.4)

We will need the next lemma, which follows immediately from Remarks 2.1 and
2.2.

######  Lemma 6.7.

Let $\gamma$ be a $g$-invariant geodesic in $\mathcal{Z}$ for some
$g\in\Gamma$. Then the image of $\gamma$ under $\phi$ (resp. $\phi_{\ast}$) in
$\mathcal{X}$ (resp. $\mathcal{X}_{\ast}$) is a (possibly non-parametrized)
geodesic. For $\mathcal{X}_{\ast}$ we allow the degenerate case that
$\phi_{\ast}(\gamma)$ is a point (which happens if and only if
$\ell_{\mathcal{X}_{\ast}}[g]=0$).

###### Proof of Lemma 6.6.

Let $\omega\in\operatorname{Fix}_{n}(\Sigma)$ be as in the statement of the
lemma and let
$\omega_{n}=t_{n}(\omega)=(v_{0}\xrightarrow{e_{1}}\cdots\xrightarrow{e_{n}}v_{n})\in
P_{n}(\Sigma^{\ast})$. As we noted previously we have
$\ell_{\mathcal{X}}[\beta(\omega_{n})]=n$, so the main content of the lemma
are the identities (6.3) and (6.4), which we now prove.

For any $k\geq 1$, let $\omega_{n}^{(k)}\in P(\Sigma^{\ast})$ be the
concatenation of $k$ copies of $\omega_{n}$ and let
$(\gamma^{(k)})_{k}=(\gamma_{({\omega_{n}}^{(k)})})_{k}\subset\mathcal{X}$ be
a sequence of good representatives of $\omega_{n}^{(k)}$ with a common
starting vertex $\gamma^{-}=(\gamma^{(k)})^{-}$. Let $q\in\Gamma$ satisfy
$(\gamma^{(1)})^{+}=q\gamma^{-}$, so that $[q]=\beta(\omega_{n})$ and
$(\gamma^{(k)})^{+}=q^{k}\gamma^{-}$ for each $k$. Also, since $\omega$ is a
closed path, by Lemma 6.7 we know that $\gamma^{(1)}$ is a fundamental domain
for a $q$-invariant geodesic in $\mathcal{X}^{\mathfrak{w}}$, and hence

$\displaystyle r^{n}(\omega)$
$\displaystyle=\overline{\mathfrak{w}}(\pi_{\mathcal{X}}(e_{1}))+\cdots+\overline{\mathfrak{w}}(\pi_{\mathcal{X}}(e_{n}))$
$\displaystyle=d_{\mathcal{X}}^{\mathfrak{w}}((\gamma^{(1)})^{-},(\gamma^{(1)})^{+})=d_{\mathcal{X}}^{\mathfrak{w}}(\gamma^{-},q\gamma^{-})=\ell_{\mathcal{X}}^{\mathfrak{w}}[q]=\ell_{\mathcal{X}}^{\mathfrak{w}}[\beta(t_{n}(\omega))].$

This proves (6.3).

To prove (6.4), let $L$ be such that
$\phi_{\ast}:\mathcal{Z}\rightarrow\mathcal{X}_{\ast}^{\mathfrak{w}_{\ast}}$
is $L$-Lipschitz and consider the lifts
$\widetilde{\gamma}^{(k)}\subset\mathcal{Z}$ of the geodesic $\gamma^{(k)}$
with a common starting vertex
$\widetilde{\gamma}^{-}=(\widetilde{\gamma}^{(k)})^{-}$. We project these
paths to $\mathcal{X}_{\ast}$ by defining
$\gamma^{-}_{\ast}:=\phi_{\ast}(\widetilde{\gamma}^{-})$ and
$(\gamma_{\ast}^{(k)})^{+}:=\phi_{\ast}((\widetilde{\gamma}^{(k)})^{+})$, and
for all $k$ we get

$|d^{\mathfrak{w}_{\ast}}_{\mathcal{X}_{\ast}}(\gamma_{\ast}^{-},(\gamma_{\ast}^{(k)})^{+})-d^{\mathfrak{w}_{\ast}}_{\mathcal{X}_{\ast}}(\gamma^{-}_{\ast},q^{k}\gamma_{\ast}^{-})|\leq
d^{\mathfrak{w}_{\ast}}_{\mathcal{X}_{\ast}}((\gamma^{(k)}_{\ast})^{+},q^{k}\gamma^{-}_{\ast})\leq
Ld_{\mathcal{Z}}((\widetilde{\gamma}^{(k)})^{+},q^{k}\widetilde{\gamma}^{-}).$
(6.5)

The last term in the inequality above is bounded by a number independent of
$k$ since
$\phi((\widetilde{\gamma}^{(k)})^{+})=\phi(q^{k}\widetilde{\gamma}^{-})=q^{k}\gamma^{-}$.
Also, we note that
$d_{\mathcal{X}_{\ast}}^{\mathfrak{w}_{\ast}}(\gamma_{\ast}^{-},(\gamma_{\ast}^{(k)})^{+})=\overline{\mathfrak{w}}_{\ast}(\alpha(\omega_{n}^{(k)}))$,
which equals $k\cdot\overline{\mathfrak{w}}_{\ast}(\alpha(\omega_{n}))$ since
$\alpha(\omega_{n}^{(k)})$ is the concatenation of $k$ copies of
$\alpha(\omega_{n})$. By Proposition 5.9 (4) it follows that

$\displaystyle
d^{\mathfrak{w}_{\ast}}_{\mathcal{X}_{\ast}}(\gamma_{\ast}^{-},(\gamma_{\ast}^{(k)})^{+})$
$\displaystyle=k\cdot\overline{\mathfrak{w}}_{\ast}(\alpha(\omega_{n}))$
$\displaystyle=k\cdot(\overline{\mathfrak{w}}_{\ast}(\Psi(v_{0})\pi_{\mathcal{X}}(e_{1}))+\overline{\mathfrak{w}}_{\ast}(\Psi(v_{1})\pi_{\mathcal{X}}(e_{2}))+\cdots+\overline{\mathfrak{w}}_{\ast}(\Psi(v_{n-1})\pi_{\mathcal{X}}(e_{n})))$
$\displaystyle=k\cdot(\psi(v_{0}\xrightarrow{e_{1}}v_{1})+\psi(v_{1}\xrightarrow{e_{2}}v_{2})+\cdots+\psi(v_{n-1}\xrightarrow{e_{n}}v_{n}))$
$\displaystyle=k\cdot(\psi(\omega)+\psi(\sigma(\omega))+\cdots+\psi(\sigma^{n-1}(\omega)))=k\psi^{n}(\omega).$

Therefore, combining this with (6.5) and after dividing by $k$ and letting $k$
tend to infinity we obtain
$\ell_{\mathcal{X}_{\ast}}^{\mathfrak{w}_{\ast}}[\beta(t_{n}(\omega))]=\ell^{\mathfrak{w}_{\ast}}_{\mathcal{X}_{\ast}}[q]=\psi^{n}(\omega)$,
as desired. ∎

To apply the results from Section 3 we require a mixing (or at least
transitive) dynamical system. To obtain such a system we consider a maximal
recurrent component $\mathcal{C}$ of the graph $\mathcal{G}_{\mathcal{X}}$. As
before we let ${\Sigma_{\mathcal{C}}}^{\ast}\subset\Sigma^{\ast}$ and
$\Sigma_{\mathcal{C}}\subset\Sigma$ be the subsets corresponding to paths in
$\mathcal{C}$, and note that $\Sigma_{\mathcal{C}}$ is $\sigma$-invariant.
Similarly we define $P(\Sigma^{\ast}_{\mathcal{C}})$,
$P_{n}(\Sigma^{\ast}_{\mathcal{C}})$ and $P_{\leq
n}(\Sigma_{\mathcal{C}}^{\ast})$, and we identify
$P_{n}(\Sigma_{\mathcal{C}}^{\ast})$ with
$\operatorname{Fix}_{n}(\Sigma_{\mathcal{C}})$.

Let $r_{\mathcal{X}}^{\mathfrak{w}}:\Sigma_{\mathcal{C}}\to{\mathbb{R}}_{>0}$
be the (constant on $2$ cylinder) restriction to $\Sigma_{\mathcal{C}}$ of the
potential introduced in Definition 6.2 and consider the suspension flow:

$\Sigma_{\mathcal{C}}^{r_{\mathcal{X}}^{\mathfrak{w}}}:=\\{(\omega,t)\in\Sigma_{\mathcal{C}}\times{\mathbb{R}}:0\leq
t\leq r_{\mathcal{X}}^{\mathfrak{w}}(\omega)\\}/\sim,$

where each $(\omega,r_{\mathcal{X}}^{\mathfrak{w}}(\omega))$ is identified
with $(\sigma(\omega),0)$ and the flow
$\sigma^{r_{\mathcal{X}}^{\mathfrak{w}}}=(\sigma^{r_{\mathcal{X}}^{\mathfrak{w}}}_{s})_{s\in{\mathbb{R}}_{>0}}$
acts as $\sigma^{r_{\mathcal{X}}^{\mathfrak{w}}}_{s}(\omega,t)=(\omega,t+s)$.

Note that any closed $\sigma^{r_{\mathcal{X}}^{\mathfrak{w}}}$-orbit $\tau$ in
$\Sigma_{\mathcal{C}}^{r_{\mathcal{X}}^{\mathfrak{w}}}$ corresponds to a
closed $\sigma$-orbit in $\Sigma_{\mathcal{C}}$. More precisely, such an orbit
$\tau$ must be of the form $\tau=\\{(\omega,t):0\leq
t\leq(r_{\mathcal{X}}^{\mathfrak{w}})^{n}(\omega)\\}$ for some
$\omega\in\Sigma_{\mathcal{C}}$ such that $\sigma^{n}(\omega)=\omega$. In this
case the period of $\tau$ equals
$l_{\tau}=(r_{\mathcal{X}}^{\mathfrak{w}})^{n}(\omega)$.

We fix a smooth function $\Delta:[0,1]\to{\mathbb{R}}_{\geq 0}$ such that
$\Delta(0)=\Delta(1)=1$ and $\int_{0}^{1}\Delta(t)\ dt=1$ and define
$\Phi:\Sigma_{\mathcal{C}}^{r_{\mathcal{X}}^{\mathfrak{w}}}\rightarrow{\mathbb{R}}_{\geq
0}$ according to

$\Phi(\omega,t)=\Delta\left(\frac{t}{r_{\mathcal{X}}^{\mathfrak{w}}(\omega)}\right)\frac{\psi_{\mathcal{X}_{\ast}}^{\mathfrak{w}_{\ast}}(\omega)}{r_{\mathcal{X}}^{\mathfrak{w}}(\omega)}\
\text{ for each
}(\omega,t)\in\Sigma_{\mathcal{C}}^{r_{\mathcal{X}}^{\mathfrak{w}}}\text{ with
}0\leq t\leq r_{\mathcal{X}}^{\mathfrak{w}}(\omega).$ (6.6)

This function has the property that, for any closed
$\sigma^{r_{\mathcal{X}}^{\mathfrak{w}}}$-orbit $\tau$ in
$\Sigma_{\mathcal{C}}^{r_{\mathcal{X}}^{\mathfrak{w}}}$ with period $l_{\tau}$