# Limits of Rauzy graphs of languages with subexponential complexity

Paul-Henry Leemann, Tatiana Nagnibeda,
Alexandra Skripchenko, Georgii Veprev

###### Abstract

To a subshift over a finite alphabet, one can naturally associate an infinite
family of finite graphs, called its Rauzy graphs. We show that for a subshift
of subexponential complexity the Rauzy graphs converge to the line
$\mathbf{Z}$ in the sense of Benjamini-Schramm convergence if and only its
complexity function $p(n)$ is unbounded and satisfies
$\lim_{n}\frac{p(n+1)}{p(n)}=1$. We then apply this criterion to many examples
of well-studied dynamical systems. If the subshift is moreover uniquely
ergodic then we show that the limit of labelled Rauzy graphs if it exists can
be identified with the unique invariant measure. In addition we consider an
example of a non uniquely ergodic system recently studied by Cassaigne and
Kaboré and identify a continuum of invariant measures with subsequential
limits of labelled Rauzy graphs.

##  1 Introduction

One of the central questions in the study of a dynamical system is that of
describing its invariant measures. Many dynamical systems admit a natural
symbolic representation as subshifts, i.e., acting as a shift on an invariant
subspace in the space of infinite words over a finite alphabet. A popular way
to study their complexity is by associating to the subshift an infinite family
of finite graphs that describe the local structure of its orbits; they were
introduced by G. Rauzy in [30] and are called the _Rauzy graphs_. The purpose
of our work is to connect the Rauzy graphs associated with a dynamical system
with its invariant measures and to provide a new, graphical realization of the
latter by considering the Benjamini-Schramm limits of the Rauzy graphs.

Given an arbitrary sequence of finite graphs of uniformly bounded degree, I.
Benjamini and O. Schramm [5] equipped it with a natural distributional limit
which has since become a central object of investigation in many different
contexts under the name of Benjamini-Schramm limit. The limiting object is not
a graph, but rather a probability measure on the space of (isomorphism classes
of) rooted graphs obtained by choosing uniformly at random a root in each of
the graphs in the sequence and by considering all possible limits in the space
of rooted graphs with local topology; see Section 2 for a precise definition.
The key fact is that it is invariant under the equivalence relation of
changing the root.

Applying this construction to a sequence of Rauzy graphs associated with a
subshift, it is natural to ask how their Benjamini-Schramm limit is related to
the original dynamical system and its invariant measures. In this paper we
provide some answers to this question in the case of subshifts of
subexponential complexity. In certain cases, the Benjamini–Schramm limits of
Rauzy graphs give us an alternative description of the invariant measures for
the original dynamical systems (see Section 4).

Let ${\mathcal{L}}$ be a language over a finite alphabet $\mathcal{A}$ and
denote by $p(n)$ its _complexity function_ ; it counts the number of words of
length $n$ that belong to ${\mathcal{L}}$. Let us recall that ${\mathcal{L}}$
is _factorial_ if it is closed under taking subwords and _prolongable_ if for
every word $w\in{\mathcal{L}}$ there exists letters $a$ and $b$ in the
alphabet $\mathcal{A}$ such that $awb$ is still in ${\mathcal{L}}$. A language
is _almost prolongable_ if the proportion of prolongable words among all words
of length $n$ tends to $1$ as $n$ tends to infinity.

For a factorial language ${\mathcal{L}}$, we denote by
${\vec{\operatorname{Rauz}}}(n)$ the $n$th _Rauzy digraph_ of ${\mathcal{L}}$.
That is the vertices of ${\vec{\operatorname{Rauz}}}(n)$ are the words of
length $n$, while the arcs are words of length $n+1$. More precisely, for $w$
of length $n-1$, the word $awb$ is the arc from $aw$ to $wb$. Given two words
$u$ and $v$ connected by an arc, the arc can be labelled by the last letter of
$v$. We can thus speak about _labelled Rauzy digraphs_ or, if we forget about
the labelling of the edges, about _unlabelled Rauzy digraphs_. It is also
possible to forget about orientation, replacing every arc by an undirected
edge, and obtain labelled and unlabelled _Rauzy graphs_
$\operatorname{Rauz}(n)$.

Our interest in the Benjamini-Schramm limits of families of Rauzy graphs
initiated in the observation in [20] that the limit of De Brujin graphs
$\\{\mathcal{B}(k,N)\\}_{N}$ (i.e., the Rauzy graphs of the full shift over
the alphabet $\\{0,...,k-1\\}$) is the (delta-measure on the) Diestel-Leader
graph $DL_{k,k}$ which is a Cayley graph of the lamplighter group
$\mathbb{Z}_{k}\wr\mathbb{Z}$. Generalizing this result, the first-named
author showed [27] that for languages coming from subshifts of finite type,
the Benjamini-Schramm limit of Rauzy graphs is a measure supported on
horocyclic products of trees that can be constructed from the subshift. On the
other hand, Drummond studied the subshifts of linear complexity [16] and
proved that the Benjamini-Schramm limit of their unlabelled Rauzy digraphs is
the (delta-measure on the) bi-infinite directed path $\vec{\mathbf{Z}}$ (see
also [18, 31, 21] for related statements about Rauzy graphs of subshifts of
linear complexity).

The main result of this paper is a characterisation of the languages whose
Rauzy (di)graphs ${\vec{\operatorname{Rauz}}}(n)$ converge to
$\vec{\mathbf{Z}}$:

######  Theorem 1.1.

Let ${\mathcal{L}}$ be a factorial and almost prolongable language with
complexity function $p(n)$. The following are equivalent:

  1. 1.

The Rauzy graphs $\operatorname{Rauz}(n)$ converge to the line $\mathbf{Z}$,

  2. 2.

The Rauzy digraphs ${\vec{\operatorname{Rauz}}}(n)$ converge to the directed
line $\vec{\mathbf{Z}}$,

  3. 3.

$p(n)$ is unbounded, grows subexponentially and the limit of the Rauzy graphs
$\operatorname{Rauz}(n)$ exists,

  4. 4.

$p(n)$ is unbounded, grows subexponentially and the limit of the Rauzy
digraphs ${\vec{\operatorname{Rauz}}}(n)$ exists,

  5. 5.

$p(n)$ is unbounded and $\lim_{n}\frac{p(n+1)}{p(n)}=1$.

Theorem 1.1 directly applies to languages coming from bi-sided subshifts, as
they are both factorial and prolongable, hence, almost prolongable. While the
language of a one-sided subshift is in general not almost prolongable, it is
the case for a broad class of subshifts. Surjective subshifts, in particular
minimal ones, have prolongable language of subwords. Moreover, if a subshift
has a dense orbit or, more generally, if it has a finite set with dense orbit
then the language is almost prolongable (see Subsection 2.3). Therefore, we
obtain the following corollary of Theorem 1.1:

######  Corollary 1.2.

Let $\Sigma$ be a bi-sided subshift or a one-sided subshift. For one-sided
subshifts, suppose moreover that $\Sigma$ has a finite subset with a dense
orbit. The following are equivalent:

  1. 1.

The Rauzy graphs $\operatorname{Rauz}(n)$ converge to the line $\mathbf{Z}$,

  2. 2.

The Rauzy digraphs ${\vec{\operatorname{Rauz}}}(n)$ converge to the directed
line $\vec{\mathbf{Z}}$,

  3. 3.

$p(n)$ is unbounded and $\lim_{n}\frac{p(n+1)}{p(n)}=1$.

Using, in particular, [11], we deduce the following sufficient condition for
the convergence of Rauzy graphs of subshifts. Here and in what follows, for
two non-negative sequences $f$ and $g$, we write $f=O(g)$ if
$\limsup_{n}f(n)/g(n)<\infty$, and $f=\Theta(g)$ if both relations $f=O(g)$
and $g=O(f)$ are satisfied. We will also write $f\sim g$ if
$\lim_{n}f(n)/g(n)=1$.

######  Corollary 1.3.

Let $\Sigma$ be a bi-sided subshift or a one-sided subshift. For one-sided
subshifts, suppose moreover that $\Sigma$ has a finite subset with dense
orbit. Suppose that $\Sigma$ has unbounded complexity and that at least one of
the following three conditions is satisfied:

  1. 1.

$p(n)=O(n^{\alpha})$ for some $\alpha<\frac{4}{3}$,

  2. 2.

$p(n)=\Theta(n^{\beta})$ for some $\beta<\frac{3}{2}$,

  3. 3.

$p(n)\sim n^{\gamma}$ for some real number $\gamma$,

Then the Rauzy digraphs of $\Sigma$ converge to $\vec{\mathbf{Z}}$ and its
Rauzy graphs converge to $\mathbf{Z}$.

In Section 4, we will see that Corollary 1.2 and Corollary 1.3 apply to many
interesting dynamical systems of different origins, including interval
exchange transformations and interval exchange transformations with flips,
interval translation maps, polygonal and polyhedral billiards, Toeplitz
subshifts, multidimensional continuous fractions and more.

Since Rauzy digraphs come with a natural labelling, we are also interested in
the convergence of the labelled Rauzy digraphs. If the limit exists then
Theorem 1.1 implies that it will be a probability measure on rooted labelled
digraphs supported on $\vec{\mathbf{Z}}$ and invariant under the change of the
root and so can be thought of as a probability measure on the set of bi-
infinite words in the alphabet $\mathcal{A}$ invariant under the shift. It is
therefore not surprising that unique ergodicity is a natural condition
sufficient for the existence of the Benjamini-Schramm limit of labelled Rauzy
digraphs.

In the context of unique ergodicity, it is natural to consider identifying the
Benjamini-Schramm limit of labelled Rauzy digraphs for topologically
transitive subshifts. Any such subshift (one-sided or two-sided) can be
represented as follows. For an infinite word $\omega$, let us denote by
$\Sigma_{\omega}$ the closure of the orbit of $\omega$ under the shift map
$S$. That is, $\Sigma_{\omega}$ is the smallest one-sided subshift (if
$\omega$ is a one-sided infinite word) or the smallest bi-sided subshift (if
$\omega$ is a bi-sided infinite word) containing $\omega$. It is known that
the subshift $(\Sigma_{\omega},S)$ is uniquely ergodic if and only if the word
$\omega$ has _uniform frequencies_ (see Section 3). The natural extension
$(\tilde{\Sigma}_{\omega},S)$ of $(\Sigma_{\omega},S)$ is a bi-sided subshift
that consists of all infinite words $\tau$ such that every finite subword of
$\tau$ is also a subword of $\omega$. If the initial subshift is already bi-
sided, then $(\tilde{\Sigma}_{\omega},S)$ and $(\Sigma_{\omega},S)$ coincide.
It is known that the uniform frequences property, hence, unique ergodicity is
preserved under passing to the natural extension. In this context we have

######  Theorem 1.4.

Let $\omega$ be an infinite word over a finite alphabet such that the subshift
$(\Sigma_{\omega},S)$ is uniquely ergodic. Assume that its complexity function
is unbounded and satisfies $\lim_{n}\frac{p(n+1)}{p(n)}=1$. Then the
Benjamini–Schramm limit of the labelled Rauzy digraphs exists and can be
identified with the unique $S$-invariant measure on
$(\tilde{\Sigma}_{\omega},S)$.

In the case of subshifts of linear complexity, this was proved in [16].

######  Remark 1.5.

The uniform frequencies property can be defined not only for transitive
subshifts but for arbitrary languages over a finite alphabet as well.
Following the same arguments, it is possible to obtain a similar result for
almost prolongable languages with uniform frequencies.

In the case of a non-uniquely ergodic subshift, one can consider subsequential
limits; we show that we can always obtain an invariant measure for a subshift
as such a limit with respect to some subsequence of labelled Rauzy digraphs
(see Proposition 3.3 in Section 3). In Section 5 we present a concrete example
of a non-uniquely ergodic system where the limit of labelled Rauzy digraphs
does not exist and where subsequential limits realize a continuum of distinct
invariant measures.

#### Plan of the article

Section 2 contains all the necessary definitions and Theorem 2.6 which
generalizes Theorem 1.1 and implies Corollary 1.2 for bi-sided subshifts. It
also contains the proof of Corollary 1.3, which is split between Corollaries
2.7 and 2.13 for bi-sided subshifts. The statements about one-sided subshifts
in Corollary 1.2 and Corollary 1.3 are proved with the help of an additional
technical result: Proposition 2.14. Section 3 deals with the limits of
labelled Rauzy graphs. Section 4 is devoted to applications of the above to
various concrete examples of dynamical systems. Finally, Section 5 contains an
example of a non-uniquely ergodic subshift where we identify subsequential
limits of labelled Rauzy graphs and show that they give us a continuum of
invariant measures.

## Acknowledgements

This work was supported by the Research Preparation Grant – Leading House
Geneva (2022). A. S. heartily thanks University of Geneva for its hospitality
and A. Frid for several interesting discussions.

##  2 Limits of Rauzy graphs of languages with subexponential complexity

In the following, $k$ will be an integer greater than $1$ and ${\mathcal{A}}$
will be a set of cardinality $k$, which we will call an _alphabet_. Elements
of ${\mathcal{A}}$ are called _letters_ , while elements of the free monoid
${\mathcal{A}}^{*}$ (where the operation is the concatenation) are called
_words_. A _language_ ${\mathcal{L}}$ is simply a subset of
${\mathcal{A}}^{*}$. We will denote by
${\mathcal{L}}_{n}={\mathcal{A}}^{n}\cap{\mathcal{L}}$ the set of words of
length $n$ in ${\mathcal{L}}$ and by $p(n)=p_{\mathcal{L}}(n)$ the
_complexity_ function of ${\mathcal{L}}$, that is, for every $n$,
$p(n)=\lvert{\mathcal{L}}_{n}\rvert$ is the number of words of ${\mathcal{L}}$
of length $n$.

A language ${\mathcal{L}}$ is _factorial_ if for any word $u$ in
${\mathcal{L}}$, any subword $v$ of $u$ is still in ${\mathcal{L}}$. A word
$v$ of ${\mathcal{L}}$ is _left-prolongable_ , respectively _right-
prolongable_ , if there exists $a\in{\mathcal{A}}$, respectively
$b\in{\mathcal{A}}$, such that $av$, respectively $vb$ is still in
${\mathcal{L}}$.

######  Definition 2.1.

A language is _prolongable_ if any word $v\in{\mathcal{L}}$ is both left-
prolongable and right-prolongable. We will say that ${\mathcal{L}}$ is _almost
prolongable_ if both the proportion of left prolongable words of length $n$
and the proportion of right prolongable words of length $n$ tend to $1$ when
$n$ goes to infinity.

######  Remark 2.2.

In the following, for a factorial language ${\mathcal{L}}$, we will always
assume that $p(1)=k$, as otherwise this implies that a letter of
${\mathcal{A}}$ is not used in ${\mathcal{L}}$ and that ${\mathcal{L}}$ is
hence a language on a smaller alphabet
${\mathcal{A}}^{\prime}\subset{\mathcal{A}}$.

As mentioned in the introduction, we denote by
${\vec{\operatorname{Rauz}}}(n)={\vec{\operatorname{Rauz}}}_{\mathcal{L}}(n)$
the $n$th _Rauzy digraph_ of ${\mathcal{L}}$. That is, the vertex set of
${\vec{\operatorname{Rauz}}}(n)$ is ${\mathcal{L}}_{n}$ the set of words of
length $n$, and there is an arc between $v$ and $w$ if there exist letters
$a,b\in{\mathcal{A}}$ and $u\in{\mathcal{L}}_{n-1}$ such that $v=au$, $w=ub$,
and $aub$ is in ${\mathcal{L}}_{n+1}$. It naturally gives rise to the _Rauzy
graph_ $\operatorname{Rauz}(n)$ where every arc $(au,ub)$ is replaced by an
edge $\\{au,ub\\}$. We will also consider the _labelled Rauzy (di)graph_
obtained by putting the label $b$ on the arc from $au$ to $ub$.

Note that the number of vertices of the (labelled) Rauzy (di)graph is exactly
$p(n)$. If ${\mathcal{L}}$ is factorial, then the arc set of the Rauzy digraph
${\vec{\operatorname{Rauz}}}_{\mathcal{L}}(n)$ can be identified with
${\mathcal{L}}(n+1)$ and, moreover,
${\vec{\operatorname{Rauz}}}_{\mathcal{L}}(n+1)$ is a spanning subgraph of the
line graph of ${\vec{\operatorname{Rauz}}}_{\mathcal{L}}(n)$.

A _rooted graph_ is a connected graph with a specified vertex, which is called
the root. Let us denote by $\mathcal{G}$ the space of rooted graphs of
uniformly bounded degree, where two rooted digraphs are close if they coincide
on a big ball around their roots. One defines similarly the spaces of rooted
digraphs, of rooted labelled graphs and of rooted labelled digraphs. We will
write $\mathcal{G}$ as a placeholder for any of the four above spaces. The
topology of $\mathcal{G}$ is induced by the metric:
$d((G_{1},v_{1}),(G_{2},v_{2}))=2^{-r}$ where $r$ is the biggest radius such
that $G_{1}$ and $G_{2}$ have isomorphic balls of radius $r$ around their
respective root. The metric is complete and separable. Moreover, the space
$\mathcal{G}$ of rooted (di)graphs (labelled or not) of uniformly bounded
degree is compact. Since here we study limits of Rauzy graphs of languages
over an alphabet with $k$ letters, all our graphs are of degree bounded by
$k$. Since $\mathcal{G}$ is separable and complete metrizable, the space
$\mathbf{P}(\mathcal{G})$ of Borel probability measures on $\mathcal{G}$ is
compact in the weak-$*$ topology. For a sequence $(G_{i})_{i}$ of finite
graphs in $\mathcal{G}$ let us choose the root in each of them uniformly at
random. This means that we define, for each $i$, the measure

$\mu_{i}\coloneqq\frac{1}{\lvert G_{i}\rvert}\sum_{v\in
G_{i}}\delta_{[(G_{i},v)]}$ (1)

in the space $\mathbf{P}(\mathcal{G})$. If the limit of the sequence $\mu_{i}$
in $\mathbf{P}(\mathcal{G})$ exists then it is called the _Benjamini-Schramm
limit of the sequence_ $(G_{i})_{i}$ (see [5]).

An important property of the Benjamini-Schramm limit is its _unimodularity_ ,
that is, invariance under the change of the root (see [1, 24] for details). A
specific case of convergence of random (di)graphs is when they converge to a
measure $\mu$ supported on one rooted (di)graph $(G,v)$ with $G$ vertex-
transitive. In that case, we say that the random (di)graphs converge to the
graph $G$.

###  2.1 Rauzy (di)graphs converging to the (directed) line

The aim of this subsection is to characterize languages for which the sequence
of Rauzy (di)graphs converges to the (directed) line. We will prove Theorem
1.1.

For a language ${\mathcal{L}}$, let the functions $e_{l}(n)$ and $e_{r}(n)$
count the number of words of length $n$ that are not left, respectively not
right, prolongable while $s_{l}(n)$ and $s_{r}(n)$ will count words that are
left, respectively right, prolongable but not in a unique way. Finally, let
$r_{l}(n)$ and $r_{r}(n)$ count the number of words that are left,
respectively right, prolongable in a unique way, while
$r(n)=\lvert\\{v\in{\mathcal{A}}^{n}\cap{\mathcal{L}}\ |\
\lvert{\mathcal{A}}v{\mathcal{A}}\cap{\mathcal{L}}\rvert=1\\}\rvert$ counts
the number of words that are both left and right-prolongable in a unique way.
With these notations, ${\mathcal{L}}$ is prolongable if and only if
$e_{r}(n)\equiv e_{l}(n)\equiv 0$ and almost prolongable if and only if
$\lim_{n}\frac{e_{l}(n)}{p(n)}=\lim_{n}\frac{e_{r}(n)}{p(n)}=0$.

First, we show an upper bound on the number of connected components of
${\vec{\operatorname{Rauz}}}(n)$ that are directed cycles.

######  Lemma 2.3.

Let ${\mathcal{L}}$ be a language on a finite alphabet of cardinality $k$.
Denote by $c_{r}(n)$ the number of (weakly) connected components of
${\vec{\operatorname{Rauz}}}(n)$ that are directed cycles of length $r$. Then
for $n\geq r$ we have

$c_{r}(n)\leq k^{r}.$

###### Proof.

Let $n$ be an integer greater than $r$ and let $C$ be a connected component of
${\vec{\operatorname{Rauz}}}(n)$ which is a directed cycle. Choose an
arbitrary vertex $v=x_{1}\cdots x_{n}$ in $C$. Then the vertex following $v$
in the cycle is of the form $x_{2}\cdots x_{n}x_{n+1}$ and when closing the
cycle we obtain $x_{1}\cdots x_{n}=x_{1+r}\cdots x_{n}x_{n+1}\cdots x_{n+r}$
since $n\geq r$. In particular, for every $1\leq i\leq n$ we have the relation
$x_{i}=x_{i+r}$ and the cycle $C$ is uniquely determined by the sequence
$x_{1}\cdots x_{r}$, which gives us the desired result. ∎

Let us recall that the function $r(n)$ counts the number of words of length
$n$ that are both left and right-prolongable in a unique way.

######  Lemma 2.4.

Let ${\mathcal{L}}$ be any language over a finite alphabet. Then the following
are equivalent:

  1. 1.

The Rauzy digraphs ${\vec{\operatorname{Rauz}}}(n)$ converge to the directed
line $\vec{\mathbf{Z}}$,

  2. 2.

The Rauzy graphs $\operatorname{Rauz}(n)$ converge to the line $\mathbf{Z}$
and ${\mathcal{L}}$ is almost prolongable,

  3. 3.

$p(n)$ is unbounded and $\lim_{n}\frac{r(n)}{p(n)}=1$.

###### Proof.

(2)$\implies$(3). Suppose that $\operatorname{Rauz}(n)$ converge to
$\mathbf{Z}$. This is equivalent to the fact that for every $r>1$ and every
$\epsilon>0$ there exists $N=N(r,\epsilon)$ such that for $n\geq N$, for at
least $1-\epsilon$ of the vertices of $\operatorname{Rauz}(n)$ the ball of
radius $r$ around $v$ is a path of length $2r$. On the one hand, for $n\geq
N(r,\frac{1}{4})$ the graph $\operatorname{Rauz}(n)$ has at least $1$ vertex
with the ball as described above, and hence at least $2r$ vertices, which
implies the first condition. On the other hand, for $n\geq N(2,\epsilon)$, we
have $\frac{t(n)}{p(n)}\geq 1-\epsilon$, where $t(n)$ is the number of
vertices of $\operatorname{Rauz}(n)$ that have degree $2$. This show that
$\lim_{n}\frac{t(n)}{p(n)}=1$. Finally, $t(n)=r(n)+q_{i}(n)+q_{o}(n)$, where
$q_{i}(n)$ counts the number of vertices of ${\vec{\operatorname{Rauz}}}(n)$
of in-degree $2$ and out-degree $0$, while $q_{o}(n)$ counts the number of
vertices of out-degree $2$ and in-degree $0$. Since ${\mathcal{L}}$ is almost
prolongable, both $\frac{q_{i}(n)}{p(n)}$ and $\frac{q_{o}(n)}{p(n)}$ go to
$0$ when $n$ goes to infinity, which finishes the proof.

(1)$\implies$(3). If the digraphs ${\vec{\operatorname{Rauz}}}(n)$ converge to
$\vec{\mathbf{Z}}$, then the same proof as above shows that $p(n)$ is
unbounded and that $\frac{r(n)}{p(n)}\geq 1-\epsilon$ for $n\geq
N(2,\epsilon)$, without supposing that ${\mathcal{L}}$ is almost prolongable.

(3)$\implies$(1). We now show that the conditions on $p(n)$ and $r(n)$ imply
the convergence of the Rauzy digraphs. Let $r$ be an integer. For $n\geq r$,
the number of non-biregular vertices of ${\vec{\operatorname{Rauz}}}(n)$ is
$p(n)-r(n)$. Since every vertex has at most $2k$-neighbours, the number of
vertices of ${\vec{\operatorname{Rauz}}}(n)$ which are at distance at most $r$
of a non-biregular vertex is bounded above by
$(2k)^{r+1}\bigl{(}p(n)-r(n)\bigr{)}$. In consequence, for at least

$1-\frac{(2k)^{r+1}\bigl{(}p(n)-r(n)\bigr{)}}{p(n)}$

of the vertices of ${\vec{\operatorname{Rauz}}}(n)$, the ball of radius $r$
around $v$ consists only of biregular vertices. The only connected rooted
digraphs of radius at most $2r$ with only biregular vertices — excepts maybe
for vertices at distance $r$ from the root which might have in or out-degree
$0$ — are the directed paths of length $2r$ and the directed cycles of length
less than $2r$. By Lemma 2.3 there are at most

$\sum_{i=1}^{2r}i\cdot k^{i}\eqqcolon M$

vertices of ${\vec{\operatorname{Rauz}}}(n)$ contained in a connected
component of ${\vec{\operatorname{Rauz}}}(n)$ isomorphic to a cycle of length
at most $2r$. Altogether, the proportion of vertices of
${\vec{\operatorname{Rauz}}}(n)$ such that the balls of radius $r$ around them
is a directed path is at least

$1-\frac{(2k)^{r+1}\bigl{(}p(n)-r(n)\bigr{)}}{p(n)}-\frac{M}{p(n)}.$

By assumptions on $p(n)$ and $r(n)$ this quantity tends to $1$ when $n$ goes
to infinity, which proves the Benjamini–Schramm convergence of the
${\vec{\operatorname{Rauz}}}(n)$ to $\vec{\mathbf{Z}}$.

(1)$\implies$(2). It is clear that the convergence of the Rauzy digraphs
implies the convergence of the Rauzy graphs. It hence remains to show that it
also implies that ${\mathcal{L}}$ is almost prolongable. It follows from the
definition that for $*\in\\{l,r\\}$ we have

$r(n)\leq r_{*}(n)=p(n)-s_{*}(n)-e_{*}(n).$ (2)

But then, using that the convergence of ${\vec{\operatorname{Rauz}}}(n)$ to
$\vec{\mathbf{Z}}$ implies $\lim_{n}\frac{r(n)}{p(n)}=1$, the above inequality
implies that $\lim_{n}\frac{s_{*}(n)}{p(n)}=\lim_{n}\frac{e_{*}(n)}{p(n)}=0$
for $*\in\\{l,r\\}$. In particular, ${\mathcal{L}}$ is almost prolongable. ∎

Note that Lemma 2.4 holds in any, not necessarily prolongable, language. The
condition on $\frac{r(n)}{p(n)}$ is however hard to check in general. For
factorial languages, the situation is better and Theorem 2.6 below gives a
criterion for convergence that depends only on the complexity. For factorial
and almost prolongable languages of unbounded subexponential complexity it
says moreover that if the graphs converge, then they converge to the line. We
first prove that under these hypotheses one can always find a subsequence of
$\operatorname{Rauz}(n)$ converging to $\mathbf{Z}$.

######  Lemma 2.5.

Let ${\mathcal{L}}$ be a factorial and almost prolongable language. Suppose
that its complexity is unbounded and grows subexponentially. Then there exists
a sequence of positive integers $n_{d}$ such that the Rauzy graphs
$\operatorname{Rauz}(n_{d})$ converge to the line $\mathbf{Z}$.

###### Proof.

Let $d$ be an arbitrary positive integer. On the one hand, we observe that for
any positive subexponential function $p(n)$, there exists infinitely many $n$
such that

$\frac{p(n+2d)}{p(n)}<1+\frac{1}{d}.$ (3)

Indeed, otherwise all $n$ big enough would satisfy
$p(n+2d)>(1+\frac{1}{d})p(n)$, implying exponential growth. On the other hand,
for all $n$ big enough we have

$\lvert\\{v\in{\mathcal{L}}_{n}\ |\ \exists
u,w\in{\mathcal{L}}_{d}:uvw\in{\mathcal{L}}_{n+2d}\\}\rvert>(1-\frac{1}{d})p(n).$
(4)

Indeed, given $d\in\mathbf{N}$ one can choose $\delta>0$ such that
$(1-\delta)^{2d}>(1-\frac{1}{d})$. Since ${\mathcal{L}}$ is almost
prolongable, for $n$ big enough at least $(1-\delta)p(n)$ of words in
${\mathcal{L}}_{n}$ are prolongable. Using that ${\mathcal{L}}$ is also
factorial, the left hand side in Equation (4) is bigger than
$(1-\delta)^{2d}p(n)>(1-\frac{1}{d})p(n)$.

Consider a map $\phi\colon{\mathcal{L}}_{n+2d}\to{\mathcal{L}}_{n}$ that maps
a word $w$ of length $n+2d$ to the middle subword $\phi(w)=w_{d+1}\dots
w_{d+n}$ of length $n$. Since the language is factorial, the map $\phi$ is
well-defined. Assume that $n$ and $d$ are such that both Equations (3) and (4)
are satisfied. Then there are at most $\frac{1}{d}p(n)$ words in
${\mathcal{L}}_{n}$ which have more than one pre-image and at most
$\frac{1}{d}p(n)$ words in ${\mathcal{L}}_{n}$ which have no pre-image. Let
${\mathcal{L}}^{\prime}_{n}$ denote the subset of words in ${\mathcal{L}}_{n}$
with a unique pre-image under $\phi$. It is then clear that
$\lvert{\mathcal{L}}^{\prime}_{n}\rvert>(1-\frac{2}{d})p(n)$. For any word in
${\mathcal{L}}^{\prime}_{n}$, its $k$-neighborhood in the Rauzy graph
$\operatorname{Rauz}(n)$ is either a segment of $\mathbf{Z}$ of length $2d$ or
a closed cycle of length no more than $2d$.

Now, let $(n_{d})_{d\in\mathbf{N}}$ be an increasing sequence of integers such
that for all $d$, the couple $(d,n_{d})$ satisfies Equations (3) and (4). We
claim that the $\operatorname{Rauz}(n_{d})$ converge to $\mathbf{Z}$. To prove
that, we take any positive integer $l$ and show that with probability tending
to $1$ the $l$-neighborhood of a uniformly random vertex in
$\operatorname{Rauz}(n_{d})$ is a segment of $\mathbf{Z}$ of length $2l$. The
number of cycles of length no more than $2l$ is finite. More precisely, it is
bounded above by some constant $c_{l}$ depending only on $l$ and on the
cardinality of the alphabet. Therefore, the number of all the vertices covered
by these cycles is $o(p(n_{d}))$ due to the unboundedness of $p(n)$. Hence,
for any $d\geq l$, with probability at least
$1-\frac{2}{d}-\frac{o(p(n_{d}))}{p(n_{d})}$ the $l$-neighborhood of a vertex
in $\operatorname{Rauz}(n_{d})$ is a segment of $\mathbf{Z}$. ∎

Now we finally prove Theorem 1.1.

######  Theorem 2.6.

Let ${\mathcal{L}}$ be a factorial language with complexity $p(n)$. Then the
following are equivalent:

  1. 1.

The Rauzy digraphs ${\vec{\operatorname{Rauz}}}(n)$ converge to the directed
line $\vec{\mathbf{Z}}$,

  2. 2.

${\mathcal{L}}$ is almost prolongable and the Rauzy graphs
$\operatorname{Rauz}(n)$ converge to the line $\mathbf{Z}$,

  3. 3.

${\mathcal{L}}$ is almost prolongable, $p(n)$ is unbounded, grows
subexponentially, the limit of the Rauzy digraphs
${\vec{\operatorname{Rauz}}}(n)$ exists,

  4. 4.

${\mathcal{L}}$ is almost prolongable, $p(n)$ is unbounded, grows
subexponentially, the limit of the Rauzy graphs $\operatorname{Rauz}(n)$
exists,

  5. 5.

${\mathcal{L}}$ is almost prolongable, $p(n)$ is unbounded and
$\lim_{n}\frac{p(n+1)}{p(n)}=1$.

###### Proof.

(3)$\implies$(4) The limit of the $\operatorname{Rauz}(n)$ is the underlying
graph of the limit of the ${\vec{\operatorname{Rauz}}}(n)$.

(4)$\implies$(2) This is Lemma 2.5.

(1)$\iff$(2)$\iff$(5) By a theorem of Ehrenfeucht and Rozenberg [17], for a
factorial language ${\mathcal{L}}$ either $p(n)$ is bounded or $p(n)\geq n+1$
for every $n$. In particular, the condition $p(n)$ is unbounded is equivalent
to $\lim_{n}p(n)=\infty$. Thus, by Lemma 2.4, it is enough to show that, for a
factorial language, we have $\lim_{n}\frac{r(n)}{p(n)}=1$ if and only if
${\mathcal{L}}$ is almost prolongable and $\lim_{n}\frac{p(n+1)}{p(n)}=1$.
Observe that the last equality is equivalent to
$\lim_{n}\frac{p(n+1)-p(n)}{p(n)}=0$.

Since ${\mathcal{L}}$ is factorial, every word of length $n+1$ can be obtained
as $av$ with $a\in{\mathcal{A}}$ and $v\in{\mathcal{L}}$ of length $n$. Hence
we obtain

$r_{l}(n)+2s_{l}(n)\leq p(n+1)\leq r_{l}(n)+ks_{l}(n).$

Using that $p(n)=r_{l}(n)+s_{l}(n)+e_{l}(n)$ we conclude that

$s_{l}(n)\leq p(n+1)-p(n)+e_{l}(n)\leq(k-1)s_{l}(n).$ (5)

Analogous inequalities hold for $s_{r}(n)$ and $e_{r}(n)$. We also have the
inequality

$p(n)-s_{l}(n)-s_{r}(n)-e_{l}(n)-e_{r}(n)\leq r(n)$ (6)

which holds for any language.

Suppose now that $\lim_{n}\frac{r(n)}{p(n)}=1$. We already know that this
implies that ${\mathcal{L}}$ is almost prolongable. Equation (2) gives us
$\lim_{n}\frac{s_{l}(n)}{p(n)}=\lim_{n}\frac{s_{r}(n)}{p(n)}=0$, while by the
right-hand side of Equation (5) we obtain that
$\lim_{n}\frac{p(n+1)-p(n)}{p(n)}=0$.

For the converse, suppose that ${\mathcal{L}}$ is almost prolongable and that
$\lim_{n}\frac{p(n+1)}{p(n)}=1$. The left-hand side of Equation (5) gives us
that $\lim_{n}\frac{s_{l}(n)}{p(n)}=0$ and similarly
$\lim_{n}\frac{s_{r}(n)}{p(n)}=0$. Using Equation (6) we conclude that
$\lim_{n}\frac{r(n)}{p(n)}=1$.

(1)$\implies$(3) We have to show that Condition (1) implies that
${\mathcal{L}}$ is almost prolongable, and $p(n)$ is unbounded and grows
subexponentially. The first part follows from (2) and the second part from
(5).

∎

Heuristically, Theorem 2.6 (namely, the equivalence between Conditions (1) and
(5)) implies that for a factorial and almost prolongable language of unbounded
complexity, the Rauzy digraphs converge to $\vec{\mathbf{Z}}$ (equivalently,
the Rauzy graphs converge to $\mathbf{Z}$) if and only if the complexity is
both subexponential and “sufficiently regular”.

As a first example of this principle, we have the following corollary of
Theorem 2.6, where two functions are _asymptotically equivalent_ , denoted
$f\sim g$, if $\lim_{x}\frac{f(x)}{g(x)}=1$.

######  Corollary 2.7.

Let ${\mathcal{L}}$ be a factorial and almost prolongable language. Suppose
that there exists a real $\alpha\geq 1$ with $p(n)\sim n^{\alpha}$. Then its
Rauzy digraphs converge to $\vec{\mathbf{Z}}$.

######  Remark 2.8.

In the above corollary, it is not enough to ask for _polynomial complexity_ in
the usual sense that $p(n)=\Theta(n^{d})$ for some integer $d$, as this only
implies that there exist constants $0<C_{1}\leq C_{2}$ with
$1\leq\lim_{n}\frac{p(n+1)}{p(n)}\leq\frac{C_{2}}{C_{1}}$. For more on the
case $p(n)=\Theta(n^{\alpha})$, see Corollary 2.13.

We conclude this section with the following simple observation.

######  Proposition 2.9.

If the complexity function $p(n)$ of a regular factorial language is
subexponential then is satisfies
$\lim_{n\to\infty}\frac{p(n+1)-p(n)}{p(n)}=0.$

###### Proof.

It is known that a regular language has either exponential or polynomial
complexity (see [33]). Moreover, in the latter case, the complexity function
is a quasi-polynomial and, hence, satisfies
$\lim_{n\to\infty}\frac{p(n+1)-p(n)}{p(n)}=0$. ∎

######  Corollary 2.10.

The Rauzy graphs of any regular factorial almost prolongable language converge
in Benjamini-Schramm sense to $\mathbf{Z}$.

###  2.2 Asymptotics of complexity function and convergence of Rauzy graphs

In this subsection we present asymptotic bounds on the complexity function
sufficient to conclude that the Rauzy graphs of a language converge to a line.

Recall that $e_{l}(n)$ and $e_{r}(n)$ denote the number of words of length $n$
that are not left, respectively not right, prolongable and $e(n)$ denotes the
number of words of length $n$ that are neither left nor right-prolongable. The
estimates that we derive in this subsection are inspired by a paper by
Cassaigne [11]. We need the following generalization of one of his results.

######  Lemma 2.11.

Let ${\mathcal{L}}$ be a factorial and almost prolongable language with
unbounded complexity and such that $e(n)=0$ for $n$ big enough. Suppose that
there exists $\alpha\in[0,\frac{1}{2}]$ and $\beta\in[1,\frac{3}{2}]$ such
that $p(n)=O(n^{\beta})$ and both $e_{l}(n)$ and $e_{r}(n)$ are
$O(n^{\alpha})$. Then $p(n+1)-p(n)=O(n^{3\cdot\max(\alpha,\beta-1)})$.

Using this Lemma, we get the following corollary of our Theorem 2.6

######  Corollary 2.12.

Let ${\mathcal{L}}$ be a factorial and almost prolongable language with
unbounded complexity and such that $e(n)=0$ for $n$ big enough. Suppose that
there exists $\alpha\in[0,\frac{1}{2})$, $\beta\in[1,\frac{3}{2})$ and
$\gamma\in(3\cdot\max(\alpha,\beta-1),\beta]$ such that both $e_{l}(n)$ and
$e_{r}(n)$ are $O(n^{\alpha})$ and there exists constants $C_{1}$ and $C_{2}$
with

$C_{1}n^{\gamma}\leq p(n)\leq C_{2}n^{\beta}$ (7)

for $n$ big enough. Then the Rauzy digraphs of ${\mathcal{L}}$ converge to
$\vec{\mathbf{Z}}$.

###### Proof.

By Lemma 2.11, the upper bound for $p(n)$ implies that $p(n+1)-p(n)\leq
Kn^{3\cdot\max(\alpha,\beta-1)}$ for some constant $K$ and for $n$ big enough.
Hence we obtain

$0\leq\lim_{n}\frac{p(n+1)-p(n)}{p(n)}\leq\lim_{n}\frac{Kn^{3\cdot\max(\alpha,\beta-1)}}{C_{1}n^{\gamma}}.$

We conclude by Theorem 2.6. ∎

Observe that while $\alpha=\frac{1}{2}$ and $\beta=\frac{3}{2}$ are allowed in
Lemma 2.11, they are excluded for Corollary 2.12 as we ask there that $\gamma$
be smaller than $\beta$ and strictly bigger than $3\cdot\max(\alpha,\beta-1)$.

As a particular case of Corollary 2.12 we also have

######  Corollary 2.13.

Let ${\mathcal{L}}$ be a factorial and almost prolongable language with
unbounded complexity and such that $e(n)=0$ for $n$ big enough. Suppose that
there exists $\alpha$ and $\beta$ such that both $e_{l}(n)$ and $e_{r}(n)$ are
$O(n^{\alpha})$ and one of the following two conditions is satisfied:

  1. 1.

$p(n)=O(n^{\beta})$, $\alpha\in[0,\frac{1}{3})$ and $\beta\in[1,\frac{4}{3})$,

  2. 2.

$p(n)=\Theta(n^{\beta})$, $\alpha\in[0,\frac{1}{2})$ and
$\beta\in[1,\frac{3}{2})$.

Then the Rauzy digraphs of ${\mathcal{L}}$ converge to $\vec{\mathbf{Z}}$.

###### Proof.

On the one hand, the second assertion is simply Corollary 2.12 with
$\gamma=\beta$. On the other hand, since $p(n)$ is unbounded, we have
$p(n)\geq n+1$ and the first assertion is Corollary 2.12 with $\gamma=1$. But
$1$ is in $(3\cdot\max(\alpha,\beta-1),\beta]$ if and only if both
$\alpha<\frac{1}{3}$ and $\beta<\frac{4}{3}$. ∎

We end this subsection with a proof of Lemma 2.11.

###### Proof.

If ${\mathcal{L}}$ is prolongable, then $\alpha=0$ and this is [11,
Proposition 2] of Cassaigne. He also treated the case $e_{l}(n)\equiv 1$ and
$e_{r}(n)\equiv 0$ by using an auxiliary language ${\mathcal{L}}^{\prime}$ on
$k+1$ letters. We will now adapt Cassaigne’s trick to the general case. Let
$z$ be a new letter not in ${\mathcal{A}}$ and let
${\mathcal{A}}^{\prime}\coloneqq{\mathcal{A}}\cup\\{z\\}$. Define a new
language ${\mathcal{L}}^{\prime}\subset{\mathcal{A}}^{\prime}$ by

$\displaystyle{\mathcal{L}}^{\prime}\coloneqq{\mathcal{L}}$
$\displaystyle\cup\\{z^{n}v\ |\ n\in\mathbf{N},v\in{\mathcal{L}}\textnormal{
not left-prolongable}\\}$ $\displaystyle\cup\\{wz^{m}\ |\
m\in\mathbf{N},w\in{\mathcal{L}}\textnormal{ not right-prolongable}\\}$
$\displaystyle\cup\\{z^{m}uz^{n}\ |\
m,n\in\mathbf{N},u\in{\mathcal{L}}\textnormal{ neither left nor right-
prolongable}\\}.$

By construction the language ${\mathcal{L}}^{\prime}$ is factorial. We claim
that it is also prolongable. Let $t$ be in ${\mathcal{L}}^{\prime}$. If $t$
already belongs to ${\mathcal{L}}$, then it is either left-prolongable in
${\mathcal{L}}$, or $zt$ is in ${\mathcal{L}}^{\prime}$. In both cases, it is
possible to prolong $t$ to the left in ${\mathcal{L}}^{\prime}$. The same
holds for right-prolongation. If $t$ is of the form $z^{m}v$, then $v$ is not
left-prolongable in ${\mathcal{L}}$ and hence $z^{m+1}v$ is in
${\mathcal{L}}^{\prime}$. On the one hand, if $v$ is right-prolongable in
${\mathcal{L}}$, there exists $a\in{\mathcal{A}}$ such that $va$ is in
${\mathcal{L}}$. Using that ${\mathcal{L}}$ is factorial, we have that $va$ is
not left-prolongable in ${\mathcal{L}}$ and hence $z^{m}va$ is in
${\mathcal{L}}^{\prime}$. On the other hand, if $v$ is not right-prolongable
in ${\mathcal{L}}$ then $z^{n}vz$ is in ${\mathcal{L}}^{\prime}$ by
construction. An analogous reasoning take care of the case $t=wz^{n}$.
Finally, words of the form $z^{m}uz^{n}$ are obviously both left and right-
prolongable.

We now need to compare the complexity functions of ${\mathcal{L}}$ and
${\mathcal{L}}^{\prime}$. Words of length $n$ in ${\mathcal{L}}$ are of the
form $t$ for $t\in{\mathcal{A}}^{n}\cap{\mathcal{L}}$, $z^{n-i}v$ for
$v\in{\mathcal{A}}^{i}\cap{\mathcal{L}}$ not left-prolongable, $wz^{n-j}$ for
$w\in{\mathcal{A}}^{j}\cap{\mathcal{L}}$ not right-prolongable or
$z^{j}uz^{n-i-j}$ for $u\in{\mathcal{A}}^{i}\cap{\mathcal{L}}$ neither left
nor right-prolongable. In particular, any
$u\in{\mathcal{A}}^{i}\cap{\mathcal{L}}$ which is neither left nor right-
prolongable will add $n-i-1$ new words of the form $z^{j}uz^{n-i-j}$ with both
$j\neq 0$ and $n-i-j\neq 0$. This gives us

$p_{{\mathcal{L}}^{\prime}}(n)=p_{\mathcal{L}}(n)+\sum_{i=1}^{n-1}(e_{{\mathcal{L}},l}(i)+e_{{\mathcal{L}},r}(i)+e_{\mathcal{L}}(i)(n-i-1))$

Using that $e_{\mathcal{L}}(n)=0$ for $n$ big enough and that
$e_{{\mathcal{L}},l}(n)$ and $e_{{\mathcal{L}},r}(n)$ are $O(\alpha)$ we
obtain (for $n$ big enough)

$p_{{\mathcal{L}}^{\prime}}(n)\leq p_{\mathcal{L}}(n)+Cn^{\alpha+1}$

where $C$ is a constant. Moreover, we have

$\displaystyle p_{{\mathcal{L}}^{\prime}}(n+1)-p_{{\mathcal{L}}^{\prime}}(n)$
$\displaystyle=p_{{\mathcal{L}}}(n+1)-p_{{\mathcal{L}}}(n)+e_{{\mathcal{L}},l}(n)+e_{{\mathcal{L}},r}(n)+\sum_{i=1}^{n}e_{\mathcal{L}}(i)$
$\displaystyle\geq p_{{\mathcal{L}}}(n+1)-p_{{\mathcal{L}}}(n).$

By hypothesis, there exists a real number $a>0$ and an integer $n_{0}$ such
that we have $p_{{\mathcal{L}}}(n)\leq an^{\beta}$ for $n\geq n_{0}$. Using
that $\beta\geq 1$, for $n\geq n_{0}$ we have

$p_{{\mathcal{L}}^{\prime}}(n)\leq
an^{\beta}+Cn^{\alpha+1}\leq(a+C)n^{\max(\alpha+1,\beta)}$

with $1\leq\max(\alpha+1,\beta)\leq\frac{3}{2}$. We can hence apply [11,
Proposition 2] to ${\mathcal{L}}^{\prime}$ to obtain

$p_{{\mathcal{L}}}(n+1)-p_{{\mathcal{L}}}(n)\leq
p_{{\mathcal{L}}^{\prime}}(n+1)-p_{{\mathcal{L}}^{\prime}}(n)\leq
Kn^{3\cdot\max(\alpha,\beta-1)}$

for some constant $K$ and for $n$ big enough. ∎

###  2.3 Languages of one-sided subshifts

In this subsection, we finish the proof of Corollaries 1.2 and 1.3. The
language of finite subwords of a one-sided subshift $\Sigma$ is always
factorial and right-prolongable, but not necessarily prolongable. Hence, the
only missing part is to prove that the conditions that we impose on a subshift
imply almost prolongability of its language.

There are several natural properties of a subshift that ensure the desired
almost prolongability. For example, minimality or, more generally, topological
transitivity is sufficient for prolongability of the language. It is known
that for subshifts over a finite alphabet, topological transitivity implies
existence of a dense orbit. Which, as we will see, guarantees almost
prolongability. Moreover, existence of a finite set with dense orbit is enough
for the same conclusion.

######  Proposition 2.14.

Let $\Sigma$ be a one-sided subshift with a finite subset with dense orbit. If
$p(n)$ is unbounded then ${\mathcal{L}}$ is almost-prolongable.

It is sufficient to show the following.

######  Lemma 2.15.

Let $\Sigma$ be a one-sided subshift with a finite set $F$ with dense orbit.
Then $e_{l}(n)$, the number of words of length $n$ that can’t be left
prolongated, is bounded above by $\lvert F\rvert$.

###### Proof.

By assumption we have $\Sigma=\overline{\bigcup_{i=1}^{d}\\{S^{m}(w_{i})\ |\
m\in\mathbf{N}\\}}$ for some $\omega_{i}$ in $\Sigma$. Let $v$ be a finite
subword of length $n$ of some $\omega$ in $\Sigma$. We claim that $v$ can be
left-prolongated, unless maybe when $v$ is the first $n$ letters of one of the
$\omega_{i}$. If $v$ is not the first $n$ letters of a sequence $\omega$ then
the claim trivially holds. It is also the case if $v$ is the first $n$ letters
of $S^{m}(\omega_{i})$ for $m\geq 1$. Finally, if $v$ is the first $n$ letters
of some limit point $\omega$, then there exists an index $i$ and infinitely
many $m$ such that $v$ is the first $n$ letters of $S^{m}(\omega_{i})$. ∎

The proof of Corollary 1.2 and Corollary 1.3 is now complete.

We conclude this subsection with a simple example of a subshift whose
complexity function $p(n)$ is unbounded and satisfies
$\lim_{n}\frac{p(n+1)}{p(n)}=1$ but its Rauzy graphs do not converge to a
line. The reason for that is the absence of almost prolongability.

######  Example 2.16.

Let ${\mathcal{L}}$ be the language of a one-sided subshift $\Sigma$ over a
finite alphabet ${\mathcal{A}}$ and $z$ be a letter not in ${\mathcal{A}}$.
Assume that $p_{\mathcal{L}}(n)$ is unbounded and
$\lim_{n}\frac{p_{\mathcal{L}}(n+1)}{p_{\mathcal{L}}(n)}=1$ (see Section 4 for
examples of such subshifts).

Let $\tilde{\Sigma}=\Sigma\cup z\Sigma$ be a new subshift with the language
$\tilde{\mathcal{L}}\coloneqq{\mathcal{L}}\cup z{\mathcal{L}}$. Clearly, the
complexity function $p_{\tilde{\mathcal{L}}}(n)$ is
$p_{\mathcal{L}}(n)+p_{\mathcal{L}}(n-1)$ and, therefore, satisfies the limit
condition. However, the language $\tilde{\mathcal{L}}$ is not almost
prolongable and, hence, the Rauzy graphs do not converge to a line.

##  3 Limit of labelled Rauzy digraphs

As we already know, if the Benjamini-Schramm limit of (unlabelled) Rauzy
digraphs for a subshift of unbounded subexponential complexity exists then it
is $\vec{\mathbf{Z}}$. Throughout this section, we will assume that such a
limit does exist. Now let us introduce labels on our Rauzy digraphs. Recall
that we label an arc connecting two words $u$ and $v$ by the last letter of
$v$. In this case, the limit of labelled Rauzy digraphs, if it exists, will be
a probability measure on rooted labelled digraphs supported on
$\vec{\mathbf{Z}}$ and invariant under the change of the root. In other words,
the limit will be a probability measure on the set of bi-infinite words
invariant under the shift. In this section, we show that if the subshift is
uniquely ergodic then the Benjamini-Schramm limit of labelled Rauzy digraphs
exists and is the unique ergodic invariant measure for the subshift. In the
case of subshifts of linear complexity, this was earlier proved in [16].

In the case of a non-uniquely ergodic subsift, one can consider subsequential
limits; we show that we can always obtain an invariant measure for a subshift
as such a limit with respect to some subsequence of labelled Rauzy digraphs.
In Section 5 we present a concrete example of a non-uniquely ergodic system
where this procedure realizes a continuum of distinct invariant measures.

In this section, we restrict our considerations to the case of topologically
transitive subshifts. That is, given an infinite word $\omega$, we define a
closed subset $\Sigma_{\omega}\subset{\mathcal{A}}^{\mathbf{N}}$ to be the
closure of the orbit of $\omega$ with respect to the shift map $S$ on
${\mathcal{A}}^{\mathbf{N}}$. We will refer to the complexity function of the
language coming from $\Sigma_{\omega}$ as the complexity of the word $\omega$.
Let us recall the definition of _words with uniform frequencies_.

######  Definition 3.1.

We denote by $\lvert\omega_{k}\cdots\omega_{k+n}\rvert_{u}$ the number of
occurrences of a finite word $u$ within a finite stretch of $\omega$:

$\lvert\omega_{k}\cdots\omega_{k+n}\rvert_{u}=\sum_{i=0}^{n-\lvert
u\rvert}I_{u}(S^{i+k}\omega),$

where $I_{u}$ is the indicator function of a cylinder set with base $u$. The
word $\omega$ has _uniform frequencies_ if for every $u$ there exists a
constant $F_{u}(\omega)$ such that

$\lim_{n}\sup_{k}|\frac{\lvert\omega_{k}\cdots\omega_{k+n}\rvert_{u}}{n+1}-F_{u}(\omega)|=0.$

######  Proposition 3.2 (Oxtoby ergodic theorem, [29]).

A word $\omega$ has uniform frequencies if and only if $(\Sigma_{\omega},S)$
is uniquely ergodic.

Let us recall that the natural extension $(\tilde{\Sigma},S)$ of a subshift
$(\Sigma,S)$ is a bi-sided subshift that consists of all bi-infinite words
$\tau\in{\mathcal{A}}^{\mathbf{Z}}$ such that any finite subword of $\tau$
belongs to the language of $\Sigma$. It can be shown that the natural
extension of a uniquely ergodic subshift is also uniquely ergodic. Now, let us
proceed with the proof of Theorem 1.4.

###### Proof of Theorem 1.4.

We follow the argument from [16] where the case of linear complexity was
treated. First, we apply Theorem 1.1 to the subshift and conclude that the
Benjamini–Schramm limit of its unlabelled Rauzy digraphs is the oriented line.

Let $u$ be a finite word of even length. The Benjamini–Schramm convergence of
the Rauzy digraphs implies that there exists an unbounded non-decreasing
sequence $\\{d_{n}\\}$ of integer numbers such that for any sufficiently large
$n$, there exists a subset $E_{n}$ of vertices of
${\vec{\operatorname{Rauz}}}(n)$ such that $|E_{n}|=o(p(n))$ and each
connected component of ${\vec{\operatorname{Rauz}}}(n)\setminus E_{n}$ is an
oriented segment of length at least $d_{n}$.

For each segment of length $k$, we assign a finite sequence of labels that can
be read following the orientation starting from the vertex with no ingoing
edges. This sequence forms a finite subword of $\omega$ of length $k\geq
d_{n}$. Due to the uniform frequencies condition, the number of occurrences of
$u$ in this word is $F_{u}(\omega)k+o(k)$. Each such occurrence represents a
vertex in ${\vec{\operatorname{Rauz}}}(n)$ whose $\frac{|u|}{2}$–neighborhood
is the oriented segment whose sequence of labels is exactly $u$. Hence, the
total number of such vertices in ${\vec{\operatorname{Rauz}}}(n)$ is
$F_{u}(\omega)p(n)+o(p(n))$. Therefore, the labelled Rauzy digraphs converge
to a measure on ${\mathcal{A}}^{\mathbf{Z}}$ such that the cylinder set with
base $u$ has measure $F_{u}(\omega)$. That is this limit coincides with the
unique invariant measure on $(\tilde{\Sigma}_{\omega},S)$.

∎

We conclude this section with the following proposition showing that even if a
subshift is not uniquely ergodic, we can represent some of its invariant
measures as the limit of labelled Rauzy digraphs. However, to do that we have
to consider only subsequential limits since the actual limit may not exist in
general (see Section 5).

######  Proposition 3.3.

Let $(\Sigma,S)$ be a subshift of unbounded subexponential complexity over a
finite alphabet that has a finite subset with dense orbit. Then there exists a
sequence $\\{n_{k}\\}$ such that the Benjamini–Schramm limit of the labelled
Rauzy digraphs ${\vec{\operatorname{Rauz}}}(n_{k})$ exists and can be
identified with an invariant probability measure on $(\tilde{\Sigma},S)$.

###### Proof.

First, we apply Lemma 2.5 to ${\mathcal{L}}_{\Sigma}$ and find a sequence
$\\{n_{k}^{\prime}\\}$ such that the underlying unlabelled Rauzy digraphs
${\vec{\operatorname{Rauz}}}(n_{k})$ converge to $\vec{\mathbf{Z}}$. Then, due
to the compactness argument, we can choose a subsequence
$\\{n_{k}\\}\subset\\{n_{k}^{\prime}\\}$ such that the Benjamini–Schramm limit
along $n_{k}$ of the labelled Rauzy digraphs exists. This limit is supported
on the set of labelings of $\vec{\mathbf{Z}}$ and is invariant under the
change of the root, hence, it is a stationary measure on
${\mathcal{A}}^{\mathbf{Z}}$. Clearly, the measure of any cylinder set with
base $u$ is positive only if $u$ belongs to the language of $(\Sigma,S)$.
Hence, the limiting measure is a shift-invariant measure supported on the
natural extension of the system. ∎

##  4 Examples and applications

In this section we explain how various dynamical systems fit in the framework
of our main results (Theorem 1.1, Corollaries 1.2 and 1.3 and Theorem 1.4).

###  4.1 Symbolic dynamical systems

Recall that a _substitution_ is a mapping from an alphabet $A$ to the set of
words $A^{*}$. It can be extended to a monoid morphism $A^{*}\to A^{*}$ and
further to a morphism $\phi:A^{\mathbb{N}}\to A^{\mathbb{N}}$. A _pure morphic
sequence_ is a fixed point of such a morphism. A natural generalization of
this notion is that of a _morphic sequence_ , that is, the image of a pure
morphic sequence under some coding (a morphism $A\rightarrow B$ between two
alphabets).

It was proved in [15] that the complexity function $p$ of a morphic sequence
is either $p(n)=\Theta(n^{1+1/k})$ for some $k\in\mathbf{N}$, or $p(n)=O(n\log
n)$. Rauzy graphs in the linear complexity case (corresponding to primitive
substitutions) were studied in the literature (see, for example, [18]). We are
now able to identify the limit of the Rauzy graphs for morphic sequences of
superlinear complexity. Indeed, one can easily check that if $k>2$, all the
conditions of Theorem 1.2 and Corollary 1.3 are satisfied. Therefore, we prove
the following

######  Corollary 4.1.

For $k>2$, the Benjamini-Schramm limit of the Rauzy graphs corresponding to a
morphic sequence is $\mathbf{Z}$.

Note, however, that there are examples (see [15]) with $k=1$, and so not all
the morphic sequences are covered by the Corollary.

The study of morphic sequences and their invariant and/or ergodic measures is
an important step in the understanding of the dynamical properties of tiling
systems and of quasi-crystals (see, for example, [6]). In certain special
cases the tiling space of a word has been shown to be homeomorphic to the
inverse limit of its Rauzy graphs ([23]); the Benjamini-Schramm limit of the
Rauzy graphs provides therefore an invariant measure on the associated tiling
space.

Next, we consider Toeplitz subshifts.

Theorem A in [26] claims that for any rational number $\frac{p}{q}$ and any
function $f(n)=o(n^{\alpha})$ such that $nf^{\prime}(n)=o(n^{\alpha})$ there
exists a Toeplitz sequence whose complexity satisfies the following condition:

$c_{1}f(n)n^{\frac{p}{q}}\leq p(n)<c_{2}f(n)n^{\frac{p}{q}}.$

So, if we takes parameters $\alpha$ and $\frac{p}{q}$ such that
$\alpha+\frac{p}{q}<\frac{4}{3}$ we can apply Corollary 1.3 and conclude that
the Benjamini-Schramm limit of the Rauzy graphs of the subshift is the line.
It also holds for the so-called simple Toeplitz subshifts considered in [31]
as they have linear complexity.

Another family of so called $(p,q)$-Toeplitz shifts is given in [13]. It is
shown that this family has polynomial complexity (see Theorem 7 in [13]) and
it follows easily from the proof of Lemma 8 in [13] that the asymptotics of
$p(n+1)-p(n)$ is given by $O(n)$. Thus, for this series of Toeplitz subshifts,
the Benjamini-Schramm limit of corresponding Rauzy graphs is also
$\mathbf{Z}$.

###  4.2 Interval Translation Mappings

Interval translation mappings (ITMs) were introduced by M. Boshernitzan and I.
Kornfeld (see [8]) as a natural generalization of one of the most famous one-
dimensional dynamical systems - interval exchange transformations (IETs). IETs
were defined in 60s in connection with the study of measured foliations on
oriented surfaces and billiards in rational polygons. Namely, IETs appear as
the first return map to the transversal for the leaves of the measured
foliation (or, equivalently, for the vertical translation flow on the
translation surface or billiard flow in a rational billiard). We refer to [14,
Chapter 5] for basics about IETs.

######  Definition 4.2.

_Interval exchange transformation_ (IET) is a bijective piecewise continuous
map from the half-interval of real axis to itself with a finite number of
discontinuity points, such that on each interval of continuity this map is a
translation.

An _interval translation map_ is a piecewise translation map $T$ defined on an
half-open interval $I\subset\mathbf{R}$ with values in $I$. We call $T$ a
$d$-interval translation map (or $d$-ITM) if $I$ has exactly $d$ maximal half-
open sub-intervals to which the restriction of the $T$ is a translation.

As follows from the definition, both IETs and ITMs are defined by a finite
number of parameters.

From the point of view of symbolic dynamics, IETs admit the following natural
description: each interval of continuity can be denote by a separate letter,
and thus any orbit is given by the (possibly, periodic) word of a finite
alphabet, and the application of the IET is given by a one-side shift on such
a word. It is easy to estimate and very often even to compute complexity of an
IETs on $d$ intervals: $p(n)\leq(d-1)n+1$ and it is a precise equality for all
generic maps (generic means that the lengths of the intervals of continuity
are rationally independent). Such IETs are known to be minimal and uniquely
ergodic. Therefore Drummond’s result [16] applies and gives us a description
of the unique invariant ergodic measure as the limit of (labelled) Rauzy
digraphs.

Boshernitzan and Kornfeld ([8]) noticed that ITMs can be divided into two
classes in the following way: looking at the sequence $\Sigma_{k}=I\cap
T(I)\cdots\cap T^{k}(I)$ we distinguish two cases. Either there exists
$m\in\mathbb{N}$ such that $\Sigma_{m}=\Sigma_{m+1}$, then we say that an ITM
$T$ is _of finite type_. Morally it means that $T$ can be reduced to an IET.
If such an $m$ does not exist and the limit of $\Sigma_{m}$ is a nowhere dense
set, we say that $T$ is _of infinite type_. A challenging question is to
understand the maps of infinite type because only these ITMs represent some
dynamics crucially different from IETs. Additional motivation to study ITMs of
infinite type comes from the geometric group theory, where a very similar
object, named _systems of isometries_ or _band complex_ , appears in
connection with actions of free groups on $\mathbb{R}$-trees (see [19] for the
definitions); ITMs of infinite type can be seen as a particular case of
systems of isometries of so called thin type.

ITMs admit symbolic description similar to IETs: encode each interval of
continuity by a letter, and hence get every orbit encoded by an infinite word
in this finite alphabet and the ITM acting by the one-sided shift.

Bruin and Troubetzkoy ([9]) studied a 2-parameter family of ITM’s of linear
complexity, where a typical map of infinite type is uniquely ergodic ([32]).
Hence Drummond’s result [16] applies and gives a description of the unique
ergodic invariant measure as the limit of the labelled Rauzy digrpahs.

In general, the complexity of an ITM is at most polynomial [8]. The next
candidate for a similar analysis is the class of the so-called ”double
rotations" since we know that typical double rotation of infinite type is
uniquely ergodic ([3]). However, no exact estimate on the complexity of double
rotations of infinite type is known.

###  4.3 Polygonal and polyhedral billiards

An important class of dynamical systems that fit in the framework of Theorem
1.2 but is not covered by Drummond’s results are billiards in rational
polygons and, more generally, polyhedra.

Given a polygon $Q$ with a finite number of sides, we can consider a billiard
ball, i.e. a point mass, that moves inside the polygon $Q$ with unit speed
along a straight line until it reaches the boundary, then instantaneously
changes direction according to the mirror law. Billiards are widely studied in
different branches of mathematics, for example, in connection with Hamiltonian
systems or geodesic flows on Riemannian manifolds (see, for example, [34]). We
call the polygon $Q$ _rational_ , if all the angles of $W$ are equal to
$\frac{p}{q}\pi$ for some natural $p$ and $q$. Billiards in rational polygons
play a particular role in Teichmüller dynamics due to their connections with
interval exchange transformations and measured foliations on surfaces.

A billiard dynamical system admits a natural coding: we label the sides of the
polygon by symbols from a finite alphabet whose cardinality is equal to the
number of sides of $Q$ and code the orbit by the sequence of sides it hits.
Application of the billiard map in a given direction defines a shift of the
word provided by the orbit. Then there are two natural ways to define a
subshift via this coding. The _general subshift_ $\Sigma^{g}$ consists of the
infinite words corresponding to all the orbits of the billiard and the
_directional subshift_ $\Sigma^{d,v}$ consists of words corresponding to all
the orbits in a given direction $v$. These subshifts give rise to two
different approaches toward the study of complexity of billiard systems. The
_general complexity_ $p_{g}(n)$ (i. e., complexity of $\Sigma^{g}$) includes
all the directions, while the _directional complexity_ $p_{d,v}(n)$ (i. e.,
complexity of $\Sigma^{d,v}$) counts only trajectories in one (typically,
irrational) direction $v$.

It is known that directional complexity for the rational polygonal billiard is
linear ([22]), and, hence, we can apply [16]. The general complexity of a
rational polygonal billiard grows polynomially. It was proved in [10] that for
any rational convex polygon, there exist positive constants $D_{1}$, $D_{2}$
such that

$D_{1}<\frac{p_{g}(n)}{n^{3}}<D_{2}.$ (8)

Moreover, for certain billiard tables such as the unit square, the isosceles
right triangle, or the equilateral triangle the limit
$\lim_{n\to\infty}\frac{p_{g}(n)}{n^{3}}$ exists (see [10]). Let us note that
there are no known examples when this limit does not exist. Using relation (8)
together with the bounds by Masur [28] we obtain that for any rational convex
polygon $Q$

$\lim_{n\to\infty}\frac{p_{g}(n+1)}{p_{g}(n)}=1.$

Since the language of $\Sigma^{g}$ is prolongable we obtain the following.

######  Corollary 4.3.

The Benjamini-Schramm limit of the Rauzy graphs, associated with the language
of all trajectories of the billiard flow in the rational polygon, is equal to
$\mathbf{Z}$.

Not much is known about the complexity of polyhedral billiards. However, we
can apply our results to directional subshifts corresponding to hypercubic
billiards. Let $Q$ be a hypercube of dimension $s+1$ and let $v$ be a totally
irrational direction (i. e., such that its components are independent over
$\mathbf{Q}$ as well as their inverses). It is known that the billiard flow in
$\mathbf{Q}$ in direction $v$ is uniquely ergodic as well as the corresponding
directional subshift (see, e. g., [2] for discussion of the three-dimensional
case). Moreover, the following explicit polynomial formula for the directional
complexity was shown in [4]

$p_{d,v}(n)=\sum_{i=0}^{inf(n,s)}\frac{n!s!}{(n-i)!i!(s-i)!}.$

Thus, $p_{d,v}(n)\sim n^{s}$ and billiard trajectories for a given irrational
direction are also covered by our main results. Applying Corollary 1.3 and
Theorem 1.4, we get the following

######  Proposition 4.4.

The Rauzy graphs of the language of hypercubic billiard trajectories in a
given totally irrational direction converge to $\mathbf{Z}$. Moreover, for
almost every such direction, the unique invariant measure for the directional
subshift can be identified with the limit of the labelled Rauzy digraphs.

##  5 A non uniquely ergodic example and subsequential limits of Rauzy
digraphs

We conclude the paper with an example of a non-uniquely ergodic system where
we identify a continuum of invariant measures with subsequential limits of
labelled Rauzy digraphs. In a recent paper [12], Cassaigne and Kaboré
constructed a uniformly recurrent infinite word $u$ with complexity bounded by
$3n+1$ that does not have uniform frequencies; see also [25] for an older
example with similar properties. The linear bound on the complexity implies
that the unlabelled Rauzy digraphs converge to $\vec{\mathbf{Z}}$ due to
Corollary 1.3. Their construction of such a word goes as follows. For certain
very fast growing sequences $(l_{i})_{i}$, $(m_{i})_{i}$ and $(n_{i})_{i}$,
consider two sequences $(u_{i})_{i}$ and $(v_{i})_{i}$ of finite binary words
defined by the rule $u_{0}=0$, $v_{0}=1$ and for any non-negative integer $i$,
$u_{i+1}=u_{i}^{m_{i}}v_{i}^{l_{i}}$ and $v_{i+1}=u_{i}^{m_{i}}v_{i}^{n_{i}}$.
The word $u$ is the limit of finite words $u_{i}$’s. The exact values of the
parameters that can be used for our purpose are given by

$l_{i}=2^{2\cdot 2^{i}+4},\quad m_{i}=2^{8\cdot
2^{i}}\quad\textnormal{and}\quad n_{i}=2^{10\cdot 2^{i}}.$

It is proved in [12] that the complexity $p(n)$ of the word $u$ is bounded
from above by $3n+1$ and, moreover, $p(n+1)-p(n)\leq 3$. At the same time,
they show that $\liminf\frac{p(n)}{n}=2$. This equality implies that the
corresponding subshift has at most $2$ invariant ergodic probability measures
[7]. It is also shown in [12] that $u$ does not have uniform frequencies and,
therefore, the corresponding subshift is not uniquely ergodic and has hence
exactly two invariant ergodic probability measures. The key observation is
that $u_{i}$’s and $v_{i}$’s have different frequencies of $0$:

$\lim\limits_{i\to\infty}\frac{\lvert u_{i}\rvert_{0}}{\lvert
u_{i}\rvert}=\alpha>\lim\limits_{i\to\infty}\frac{\lvert
v_{i}\rvert_{0}}{\lvert v_{i}\rvert}=\beta.$

One can see two ergodic invariant probability measures by considering two weak
limits:

$\mu_{\alpha}=\lim\frac{1}{\lvert u_{i}\rvert}\sum_{k=0}^{\lvert
u_{i}\rvert-1}\delta\\{S^{k}u\\}\quad\textnormal{and}\quad\mu_{\beta}=\lim\frac{1}{\lvert
v_{i}\rvert}\sum_{k=0}^{\lvert v_{i}\rvert-1}\delta\\{S^{k}(S^{m_{i+1}\lvert
u_{i}\rvert}u)\\}.$

Measures $\mu_{\alpha}$ and $\mu_{\beta}$ have different values ($\alpha$ and
$\beta$ respectively) on the cylinder set
$\\{0\\}\times\\{0,1\\}^{\mathbf{N}}$. Hence every invariant measure is
determined by its value on this cylinder set.

Let ${\mathcal{L}}_{n}^{0}$ be the set of subwords of $u$ of length $n$ ending
with $0$. Assuming the limit of the labelled Rauzy digraphs exists, we have
the convergence of
$\frac{\lvert{\mathcal{L}}_{n}^{0}\rvert}{\lvert{\mathcal{L}}_{n}\rvert}$ to
the measure of those digraphs whose unique outgoing edge from the origin is
labelled with $0$.

The complexity $p(n)$ exhibits different regimes of behavior in which
different values of
$\frac{\lvert{\mathcal{L}}_{n}^{0}\rvert}{\lvert{\mathcal{L}}_{n}\rvert}$ may
occur. First, assume that $n$ is such that $a_{i}\coloneqq 2l_{i}\lvert
v_{i}\rvert<n<\tfrac{m_{i}\lvert u_{i}\rvert}{2}\eqqcolon b_{i}$. Let $w_{i}$
be the greatest common suffix of $u_{i}$ and $v_{i}$ and let
$\operatorname{prefix}(x,k)$ denote the prefix of length $k$ of the word $x$.
Let us call a word $x$ _left special_ if it is possible to prolong it to the
left in at least two different ways. The following words are left special and
distinct: $\operatorname{prefix}(w_{i}v_{i}^{l_{i}}u_{i}^{m_{i}},n)$,
$\operatorname{prefix}(w_{i}v_{i}^{n_{i}-1},n)$ and
$\operatorname{prefix}(w_{i}u_{i}^{m_{i}-1},n)$. We claim that there are no
more than three left special words of length $n$, and hence that the above
words are all of them. Indeed, since the language of subwords of $u$ is
prolongable, the difference $p(n+1)-p(n)\leq 3$ is equal to the number of left
special words in ${\mathcal{L}}_{n}$. Similarly, the difference
$\lvert{\mathcal{L}}_{n+1}^{0}\rvert-\lvert{\mathcal{L}}_{n}^{0}\rvert$ is
equal to the number of left special words in ${\mathcal{L}}_{n}$ that end with
$0$. Applying this to every $n\in[a_{i},b_{i}]$, we obtain

$p(b_{i})=p(a_{i})+3(b_{i}-a_{i})=3b_{i}(1+o(1)),$

where the second equality follows from the specific choice of $l_{i}$, $m_{i}$
and $n_{i}$ and the fact that $\tfrac{\lvert v_{i}\rvert}{\lvert
u_{i}\rvert}\leq\tfrac{n_{i-1}}{l_{i.1}}$. We also have

$\lvert{\mathcal{L}}_{b_{i}}^{0}\rvert=\lvert{\mathcal{L}}_{a_{i}}^{0}\rvert+\lvert
A\rvert_{0}+\lvert B\rvert_{0}+\lvert C\rvert_{0},$

where $A$, $B$, and $C$ are certain $(b_{i}-a_{i})$-subwords of
$u_{i}^{m_{i}}$, $v_{i}^{n_{i}-1}$ and $u_{i}^{m_{i}-1}$ respectively and
$\lvert A\rvert_{0}$ is the number of occurence of the letter $0$ in the word
$A$. Therefore,

$\lvert{\mathcal{L}}_{b_{i}}^{0}\rvert=\lvert{\mathcal{L}}_{a_{i}}^{0}\rvert+(2\alpha+\beta)(b_{i}-a_{i})(1+o(1))=(2\alpha+\beta)b_{i}(1+o(1)).$

Finally for this regime we have
$\frac{\lvert{\mathcal{L}}_{n}^{0}\rvert}{\lvert{\mathcal{L}}_{n}\rvert}=(\frac{2}{3}\alpha+\frac{1}{3}\beta)(1+o(1))$.

Similar arguments applied to the case $2m_{i}\lvert
u_{i}\rvert<n<\tfrac{n_{i}\lvert v_{i}\rvert}{2}$ produce the following three
left special words:
$\operatorname{prefix}(w_{i}v_{i}^{l_{i}}u_{i+1}^{m_{i+1}-1},n)$,
$\operatorname{prefix}(w_{i}v_{i}^{l_{i}}u_{i}^{m_{i}}v_{i}^{n_{i}},n)$ and
$\operatorname{prefix}(w_{i}v_{i}^{n_{i}-1},n)$. The same counting argument
shows that for this regime we have

$\frac{\lvert{\mathcal{L}}_{n}^{0}\rvert}{\lvert{\mathcal{L}}_{n}\rvert}=\Bigl{(}\frac{1}{3}\alpha+\frac{2}{3}\beta\Bigr{)}(1+o(1)).$

Therefore, the limit of the labelled Rauzy digraphs can not exist for this
symbolic system.

We can consider subsequential limits instead. Such limits can also be
identified with invariant measures on the natural extension provided the limit
of the unlabelled Rauzy digraphs is $\vec{\mathbf{Z}}$. Subsequential limits
always exist due to the weak compactness of the space of probability measures
on a compact metric space of rooted digraphs. Moreover, in this case, we have
a continuum of such limits. In our case, we have only two ergodic invariant
measures $\mu_{\alpha}$ and $\mu_{\beta}$, hence every invariant measure is a
convex combination $\theta\mu_{\alpha}+(1-\theta)\mu_{\beta}$. We will denote
such measure by $\mu_{\gamma}$, where $\gamma=\theta\alpha+(1-\theta)\beta$.

######  Proposition 5.1.

For any
$\gamma\in[\frac{1}{3}\alpha+\frac{2}{3}\beta,\frac{2}{3}\alpha+\frac{1}{3}\beta]$
the measure $\mu_{\gamma}$ can be obtained as a subsequential limit of
labelled Rauzy digraphs.

###### Proof.

The existence of the subsequential limits, when $\gamma$ is an endpoint of the
interval, follows from the arguments above. For any $\gamma$ in the interior
and for any $N$, we can find some $n>N$ such that
$\bigl{|}\frac{\lvert{\mathcal{L}}_{n}^{0}\rvert}{\lvert{\mathcal{L}}_{n}\rvert}-\gamma\bigr{|}<\frac{1}{N}$.
Indeed, the value of
$\frac{\lvert{\mathcal{L}}_{n}^{0}\rvert}{\lvert{\mathcal{L}}_{n}\rvert}$ is
oscillating between $\frac{1}{3}\alpha+\frac{2}{3}\beta$ and
$\frac{2}{3}\alpha+\frac{1}{3}\beta$, and the difference
$\frac{\lvert{\mathcal{L}}_{n+1}^{0}\rvert}{\lvert{\mathcal{L}}_{n+1}\rvert}-\frac{\lvert{\mathcal{L}}_{n}^{0}\rvert}{\lvert{\mathcal{L}}_{n}\rvert}$
is bounded by $\frac{3}{\lvert{\mathcal{L}}_{n}\rvert}$ which tends to zero.
Taking a subsequential limit over such $n$’s we obtain the measure
$\mu_{\gamma}$. ∎

There are several natural questions that arise in view of Propositions 5.1 and
3.3. In the above Cassaigne-Kaboré example, can one obtain ergodic measures
$\mu_{\alpha}$ and $\mu_{\beta}$ as subsequential Benjamini–Schramm limits of
labelled Rauzy digraphs? More generally, can one get an ergodic measure as
such subsequential limit for any minimal subshift with subexponential
complexity? Can one characterize geometric properties of the set of all such
invariant measures?

## References

  * [1] D. Aldous and R. Lyons.  Processes on Unimodular Random Networks.  Electron. J. Probab., 12: 1454-1508, 2007.
  * [2] P. Arnoux, C. Mauduit, I. Shiokawa, and J. Tamura.  Complexity of sequences defined by billiard in the cube.  Bull. Soc. Math. France, 122(1):1–12, 1994.
  * [3] M. Artigiani, P. Hubert, Ch. Fougeron and A. Skripchenko. A note on double rotations of infinite type. _Trans. of the Moscow Math. Soc._ , 82, 157–-172 (2021).
  * [4] Yu. Baryshnikov.  Complexity of trajectories in rectangular billiards.  Comm. Math. Phys., 174(1):43–56, 1995.
  * [5] I. Benjamini and O. Schramm.  Recurrence of distributional limits of finite planar graphs.  Electron. J. Probab., 6:no. 23, 13, 2001.
  * [6] V. Berthé, A. Siegel, Anne and J. Thuswaldner.  Substitutions, Rauzy fractals and tilings.  Encyclopedia Math. Appl.. 135 (2014).
  * [7] M. Boshernitzan.  A unique ergodicity of minimal symbolic flows with linear block growth.  J. Anal. Math., 44:77–96, 1984.
  * [8] M. Boshernitzan and I. Kornfeld.  Interval translation mappings.  Erg. Th. Dynam. Systems, 15(5):821–832, 1995.
  * [9] H. Bruin and S. Troubetzkoy.  The Gauss map on a class of interval translation mappings.  Israel J. Math., 137:125–148, 2003.
  * [10] J. Cassaigne, P. Hubert, and S. Troubetzkoy.  Complexity and growth for polygonal billiards.  Ann. Inst. Fourier (Grenoble), 52(3):835–847, 2002.
  * [11] J. Cassaigne.  Special factors of sequences with linear subword complexity.  In Developments in language theory, II (Magdeburg, 1995), 25–34. World Sci. Publ., River Edge, NJ, 1996.
  * [12] J. Cassaigne and I. Kaboré.  Word of low complexity without uniform frequencies.  arXiv:2210.02371, 2022.
  * [13] J. Cassaigne and J. Karhumäki.  Toeplitz words, generalized periodicity and periodically iterated morphisms.  European J. Combin., 18(5):497–510, 1997.
  * [14] I. P. Cornfeld, S. V. Fomin, Ya. G. Sinai.  Ergodic Theory.  Springer, Berlin, 1982.
  * [15] R. Devyatov.  On factor complexity of morphic sequences.  Mosc. Math. J., 18(2):211–303, 2018.
  * [16] B. Drummond.  Limits of Rauzy graphs of low-complexity words.  Master’s thesis, University of Ottawa, 2019.
  * [17] A. Ehrenfeucht and G. Rozenberg.  On subword complexities of homomorphic images of languages.  RAIRO Inform. Théor., 16(4):303–316, 1982.
  * [18] A. E. Frid.  On factor graphs of DOL words.  Discrete Appl. Math., 114(1-3):121–130, 2001.
  * [19] D. Gaboriau, G. Levitt and F. Paulin. Pseudogroups of isometries of $\mathbb{R}$ and Rips’ theorem on free actions on $\mathbb{R}$-trees. _Isr. J. Math._ 87: 403–428, 1994.
  * [20] R. Grigorchuk, P.-H. Leemann, and T. Nagnibeda.  Lamplighter groups, de Brujin graphs, spider-web graphs and their spectra.  J. Phys. A, 49(20):205004, 35, 2016.
  * [21] R. Grigorchuk, D. Lenz, and T. Nagnibeda.  Combinatorics of the subshift associated to Grigorchuk’s group.  Tr. Mat. Inst. Steklova, 297(1):138-144, 2017.
  * [22] P. Hubert.  Complexité de suites définies par des billards rationnels.  Bull. Soc. Math. France, 123(2):257–270, 1995.
  * [23] A. Julien.  Complexity and cohomology for cut-and-projection tilings. _Ergodic Theory and Dynamical Systems_ , 30(2):489–523, 2010.
  * [24] V. Kaimanovich.  Invariance, quasi-invariance and unimodularity for random graphs.  Zap. Nauchn. Sem. POMI, 441, 210–238, 2015.
  * [25] M. Keane.  Non-ergodic interval exchange transformations.  Israel Journal of Mathematics, 26:188–196, 1977.
  * [26] M. Koskas.  Complexités de suites de Toeplitz.  Discrete Math., 183(1-3):161–183, 1998.
  * [27] P.-H. Leemann.  On Subgroups and Schreier Graphs of Finitely Generated Groups.  PhD thesis, Université de Genève, 2016.
  * [28] H. Masur.  The growth rate of trajectories of a quadratic differential.  Erg. Th. Dynam. Systems, 10(1):151–176, 1990.
  * [29] J. Oxtoby.  Ergodic sets.  Bull. Amer. Math. Soc., 58:116–136, 1952.
  * [30] G. Rauzy.  Suites à termes dans un alphabet fini.  In Seminar on number theory, 1982–1983 (Talence, 1982/1983), pages Exp. No. 25, 16. Univ. Bordeaux I, Talence, 1983.
  * [31] D. Sell.  Combinatorics of one-dimensional simple Toeplitz subshifts.  Erg. Th. Dynam. Systems, 40(6):1673–1714, 2020.
  * [32] A. Skripchenko.  Renormalization in 1-dimensional dynamics (in Russian).  Russ. Math. Surv. 78:6 (474): 3–46, 2023.
  * [33] R. P. Stanley.  Enumerative Combinatorics, Volume 1, Second Edition.  Cambridge University Press, 2012.
  * [34] S. Tabachnikov.  Geometry and billiards.  Student mathematical library, ISSN 1520-9121, v.30

Paul-Henry Leemann, Department of Pure Mathematics, Xi’an Jiaotong–Liverpool
University, Suzhou, P.R. China
E-mail address<EMAIL_ADDRESS>

Tatiana Nagnibeda, Section de mathématiques, Université de Genève, 1205
Genève, Switzerland
E-mail address<EMAIL_ADDRESS>

Alexandra Skripchenko, Faculty of Mathematics, National Research University
Higher School of Economics, Usacheva St. 6, 119048 Moscow, Russia and Skolkovo
Institute for Science and Technology, Skolkovo Innovation Center, 143026
Moscow, Russia
E-mail address<EMAIL_ADDRESS>

Georgii Veprev, Section de mathématiques, Université de Genève, 1205 Genève,
Switzerland
E-mail address<EMAIL_ADDRESS>