# Coboundaries and eigenvalues of morphic subshifts

Paul MERCAT
Aix-Marseille University, CNRS, I2M, Marseille, France

###### Abstract

We define a morphic subshift as a subshift generated by the image of a
substitution subshift by another substitution. In other words, it is the
subshift associated with a ultimately periodic directive sequence. We present
an efficient algorithm for computing eigenvalues of morphic subshifts using
coboundaries. We show that continuous eigenvalues of $\mathcal{S}$-adic
subshifts for primitive directive sequences are always associated with some
coboundary. For morphic subshifts, we provide a characterization of the
dimension of the $\mathbb{Q}$-vector space generated by eigenvalues.
Additionally, if the substitutions are unimodular and without coboundaries, we
give a necessary and sufficient condition for weak mixing of the subshift.

###### Contents

  1. 1 Introduction
  2. 2 Definitions and notations
    1. 2.1 Words and worms
    2. 2.2 Subshift
    3. 2.3 Return words and coboundaries
    4. 2.4 Matrices
    5. 2.5 Substitution
    6. 2.6 Directive sequences
  3. 3 A general sufficient condition to be an eigenvalue
  4. 4 Eigenvalues of $\mathcal{S}$-adic subshifts
    1. 4.1 Main results
    2. 4.2 Nested sequences
    3. 4.3 Proof of Theorem 4.1
  5. 5 Eigenvalues of morphic subshifts
    1. 5.1 Characterization of eigenvalues of morphic subshifts
    2. 5.2 The algorithm
    3. 5.3 Computation of coboundaries
    4. 5.4 Return substitution
    5. 5.5 Deciding aperiodicity
    6. 5.6 Semi-deciding recognizability
  6. 6 A criterion for weak mixing
    1. 6.1 Proof of Theorem 6.3
  7. 7 Examples
    1. 7.1 Constructing examples with non-trivial coboundary
    2. 7.2 Examples of computation of eigenvalues
    3. 7.3 Examples coming from geometry
  8. 8 Acknowledgement

##  1 Introduction

Eigenvalues of topological or measure-preserving dynamical systems are
important invariants. For example a rational (additive) eigenvalue indicates
that the system is partitioned with a cyclic dynamic on pieces, while an
irrational eigenvalue implies a rotation of the circle as a factor.
Additionally, a minimal system is weakly mixing if and only if the set of its
additive eigenvalues is $\mathbb{Z}$.

Coboundaries can naturally occur. Indeed, it arose when we where studying a
problem of Novikov with Pascal Hubert and Olga Paris-Romaskevich. We found a
renormalization of our dynamical system that allows us to conjugate it with a
$\mathcal{S}$-adic subshift with a coboundary (see Example 7.8).

In 1986, a seminal paper by Host (see [Hos86]) characterized eigenvalues of a
substitution subshift with coboundaries and showed the surprising result that
every eigenvalue is associated with a continuous eigenfunction.

Ten years later, Ferenczi-Mauduit-Nogueira (see [FMN96]) provided a completely
different algebraic characterization of eigenvalues of substitution subshifts,
allowing for explicit computation. However their characterization is
complicated and they even made a calculation error in one of the two examples
they provided (see Example 9.1 in [Mer23] for more details). More recently, I
proposed a simpler algorithm to compute these eigenvalues (see [Mer23]), based
on Host’s characterization and using a algorithm for proprification due to
Durand and Petite (see [DP20]). However, this algorithm only works for pseudo-
unimodular substitutions, and the proprification algorithm can sometimes
produce very large matrices, that can complicate the computation of
eigenvalues.

Much work has been done to extend Host’s result, for example, for linearly
recurrent subshifts (see [CDHM03]), or for minimal Cantor systems (see [BDM05]
and [FD19]), or particular examples (see [CFM08]). But they always assume that
substitutions are left-proper, which avoid coboundaries. In [BBY22], Berthé-
Bernales-Yassawi propose a generalization of Host’s result using coboundaries,
but they make very strong assumptions and their definition of coboundary is
complex and not very general.

I start in Section 2 by giving notations and definitions used in the article.
Then, in Section 3, I give a general criterion ensuring the existence of
eigenvalues for a subshift. In Section 4, I partially extend Host’s result and
show that any continuous eigenvalue of a primitive directive sequence is
associated with some coboundary. I use it in Section 5 to propose a new
algorithm to compute eigenvalues of morphic subshifts that works without
proprification and for more general subshifts. I give an explicit description
of the set of eigenvalues, and algorithms to compute it and to check
aperiodicity and recognizability. In Section 6, I give a characterization of
the dimension of the $\mathbb{Q}$-vector space spanned by eigenvalues of a
morphic subshift. If moreover the iterated substitution is unimodular without
coboundary, I provide a necessary and sufficient condition for the subshift to
be weakly mixing, by looking at the action of some Galois group on pairs of
algebraic numbers. I finish by providing examples and a way to construct
examples with non-trivial coboundaries in Section 7, with some examples coming
from geometrical problems.

##  2 Definitions and notations

###  2.1 Words and worms

An alphabet is defined as a finite set. The set of finite words over an
alphabet $\mathcal{A}$ is denoted $\mathcal{A}^{*}$. It forms a monoid under
concatenation. We use $\left|w\right|$ to represent the length of a word $w$,
and $\left|w\right|_{a}$ to indicate the number of occurrences of the letter
$a$ in $w$. We denote $w_{[i,j)}$ the subword of $w$ between indices $i$
(inclusive) and $j$ (exclusive). The abelian vector of a word
$w\in\mathcal{A}^{*}$ is defined as
$\operatorname{ab}(w)=(\left|w\right|_{a})_{a\in\mathcal{A}}\in\mathbb{Z}^{A}$.
We denote $e_{a}=\operatorname{ab}(a)$, so that $(e_{a})_{a\in\mathcal{A}}$
forms the canonical basis of $\mathbb{R}^{\mathcal{A}}$.

The worm of an infinite word $x\in\mathcal{A}^{\mathbb{N}}$ is
$W(x)=\\{\operatorname{ab}(x_{[0,n)})\mid
n\in\mathbb{N}\\}=\\{\operatorname{ab}(p)\mid p\text{ prefix of }x\\}$.

###  2.2 Subshift

Given an alphabet $\mathcal{A}$, we equip the sets of infinite words
$\mathcal{A}^{\mathbb{N}}$ and bi-infinite words $\mathcal{A}^{\mathbb{Z}}$
with the product toplogy. A subshift is a compact subset $X$ of
$\mathcal{A}^{\mathbb{N}}$ or $\mathcal{A}^{\mathbb{Z}}$ endowed with the
shift map $S:\mathcal{A}^{N}\to\mathcal{A}^{\mathbb{N}}$ or
$S:\mathcal{A}^{\mathbb{Z}}\to\mathcal{A}^{\mathbb{Z}}$. We refer to the
subshift as infinite or bi-infinite. A subshift $(X,S)$ is minimal if every
orbit is dense in $X$. The language of a subshift $(X,S)$ is the set
$\mathcal{L}_{X}$ of finite factors of elements of $X$.

An (additive) eigenvalue of a subshift $(X,S)$ is a real number
$t\in\mathbb{R}$ such that there exists a function
$f:X\to\mathbb{R}/\mathbb{Z}\in L^{2}(\mu)$, where $\mu$ is an $S$-invariant
measure, such that $f\circ S=f+t$. If $f$ is continuous, we refer to $t$ as a
_continuous eigenvalue_.

Let $(X,S)$ be a bi-infinite subshift. Then, we have an associated infinite
subshift $(\tilde{X},S)$ where elements of $\tilde{X}$ are the right-infinite
part of elements of $X$. We have the following (see Proposition 2.1 in
[BBY22]).

######  Proposition 2.1.

Let $(X,S)$ be a minimal subshift. Then, $(X,S)$ and $(\tilde{X},S)$ have the
same continuous eigenvalues.

A subshift $(X,S)$ is linearly recurrent if there exists a constant $K$ such
that for every $x\in X$ and for every $k\in\mathbb{N}$, there exists $0<n<Kk$
such that $x_{[0,k)}=x_{[n,n+k)}$.

###  2.3 Return words and coboundaries

A return word of a subshift $X$ is a word $w$ such that
$ww_{0}\in\mathcal{L}_{X}$ and $\left|w\right|_{w_{0}}=1$, where $w_{0}$
denotes the first letter of $w$. We refer to the subspace $R(X)$ (or just $R$)
of $\mathbb{R}^{\mathcal{A}}$, generated by $\operatorname{ab}(w)$ for return
words $w$, as the return space. The return space on letter $a$ is denoted
$R_{a}(X)$ and is the subspace of $R(X)$ generated by return words on letter
$a$. A coboundary of a subshift $X$ over an alphabet $\mathcal{A}$ is a
morphism $c:\mathcal{A}^{*}\to\mathbb{R}/\mathbb{Z}$ such that $c(w)=0$ for
every return word $w$. Note that the data provided by such a morphism is
equivalent to that of a map
$\tilde{c}:\mathbb{R}^{\mathcal{A}}\to\mathbb{R}/\mathbb{Z}$ such that
$\tilde{c}\circ\operatorname{ab}=c$. Throughout the following, we use the same
notation to represent both maps. A real coboundary of a subshift $X$ over an
alphabet $\mathcal{A}$ is a linear form
$c:\mathbb{R}^{\mathcal{A}}\to\mathbb{R}$ such that $c(\operatorname{ab}w)=0$
for every return word $w$. As for coboundaries, we can see a real coboundary
as a map $\mathcal{A}^{*}\to\mathbb{R}$.

######  Lemma 2.2.

Let $(X,S)$ be a minimal subshift. Any coboundary
$c:\mathcal{A}^{*}\to\mathbb{R}/\mathbb{Z}$ has a representative
$\tilde{c}:\mathbb{R}^{\mathcal{A}}\to\mathbb{R}$ which is a real coboundary.

###### Proof.

Given a coboundary $c$, we construct a directed graph with edges labeled by
$\mathcal{A}$ and vertices in $\mathbb{R}/\mathbb{Z}$, as follows: Start from
vertex $0$ and choose some letter $a\in\mathcal{L}_{X}$. Add an edge
$0\xrightarrow{a}c(a)$. Choose a letter $b\in\mathcal{A}$ such that
$ab\in\mathcal{L}_{X}$, then add the edge $c(a)\xrightarrow{b}c(ab)$. Choose a
letter $c\in\mathcal{A}$ such that $abc\in\mathcal{L}_{X}$, then add the edge
$c(ab)\xrightarrow{c}c(abc)$. Continue this process until every letter has
been considered.

Note that each letter appears in the graph only once, and every word of
$\mathcal{L}_{X}$ starting by letter $a$ corresponds to a path from $0$ in the
automaton. Next, for each vertex of the graph, choose a representative in
$\mathbb{R}$. We define $\tilde{c}(a):=e-s$ for each edge $s\xrightarrow{a}e$.
Then $\tilde{c}$ defines a real coboundary and $c=\tilde{c}$ mod $\mathbb{Z}$.
∎

We call coboundary space of a subshift $(X,S)$ the vector space of real
coboundaries. In other words, it is $R(X)^{\circ}$, where $E^{\circ}=\\{w\in
E^{*}\mid\forall x\in E,\ wx=0\\}$ denotes the annihilator of $E$. Note that
it is completely determined by a graph that we call coboundaries graph with
$d+1$ vertices where $d$ is the dimension of the coboundary space.

######  Example 2.3.

Consider the periodic shift generated by the periodic word $(ab)^{\omega}$.
Then, $(1/2,1/2)$ is a coboundary. The corresponding graph is

$0$$1/2$ab

Next, we obtain the linear form $(1/2,-1/2):\mathbb{R}^{2}\to\mathbb{R}$ that
annihilates return words $\\{ab,ba\\}$. The coboundary space is the one-
dimensional subspace generated by this linear form, and the coboundaries graph
is this graph.

Coboundaries naturally extend to infinite words:

######  Lemma 2.4.

Let $(X,S)$ be a minimal subshift, and let
$c:\mathcal{A}^{*}\to\mathbb{R}/\mathbb{Z}$ be a coboundary. Then we can
extend $c:X\cup\mathcal{A}^{*}\to\mathbb{R}/\mathbb{Z}$ such that
$c(x_{0})=c(x)-c(Sx)$ for every $x\in X\cup\mathcal{A}^{+}$.

###### Proof.

As in the proof of previous lemma, consider a coboundary graph associated with
the coboundary $c$. We define $c$ on $X$ by $c(x)=-v$ where
$v\xrightarrow{x_{0}}\cdot$ is the unique arrow labeled by letter $x_{0}$ in
the graph. Then we have $c(x_{0})=c(x)-c(Sx)$. ∎

Note that it also works with real coboundaries. The extension of $c$ to $X$ is
unique if we set the value $c(x)$ at a point $x\in X$.

###  2.4 Matrices

A matrix $M\in M_{d}(\mathbb{N})$ is

  * •

primitive if there exists $n\geq 1$ such that $M^{n}$ has strictly positive
coefficients,

  * •

irreducible if its characteristic polynomial is irreducible,

  * •

unimodular if its determinant is $\pm 1$,

  * •

pseudo-unimodular if the product of its non-zero eigenvalues is $\pm 1$,
counting multiplicities.

  * •

Pisot if it has one eigenvalue $>1$ and every other eigenvalue has a modulus
strictly less than $1$.

We denote $M>0$ if every coefficient of $M$ is strictly positive. We define
the pseudo-inverse of a square matrix $M$ as the matrix $M^{-1}$ obtained by
inversion of every invertible Jordan block and taking the transpose of the
other ones in the Jordan decomposition of the matrix. When the matrix $M$ is
invertible, this is the usual inverse of the matrix. In restriction to the
eventual image $I=\bigcap_{n\in\mathbb{N}}M^{n}\mathbb{R}^{A}$, the matrix
$\mathchoice{{M\,\smash{\vrule
height=5.46666pt,depth=1.62633pt}}_{\,I}}{{M\,\smash{\vrule
height=5.46666pt,depth=1.62633pt}}_{\,I}}{{M\,\smash{\vrule
height=3.82666pt,depth=1.16167pt}}_{\,I}}{{M\,\smash{\vrule
height=2.73332pt,depth=1.16167pt}}_{\,I}}$ is invertible and its inverse is
the pseudo-inverse $\mathchoice{{M^{-1}\,\smash{\vrule
height=6.91022pt,depth=1.62633pt}}_{\,I}}{{M^{-1}\,\smash{\vrule
height=6.91022pt,depth=1.62633pt}}_{\,I}}{{M^{-1}\,\smash{\vrule
height=4.85777pt,depth=1.16167pt}}_{\,I}}{{M^{-1}\,\smash{\vrule
height=3.76443pt,depth=1.16167pt}}_{\,I}}$.

A number $\beta\in\mathbb{R}$ is Perron if it is an algebraic integer
$\beta>1$ such that every Galois conjugate has modulus strictly less than
$\beta$. It is Pisot if moreover Galois conjugates have modulus strictly less
than $1$.

We have the following well-known theorem.

######  Theorem 2.5.

(Perron-Frobenius) If $M\in M_{d}(\mathbb{N})$ is a primitive matrix, then its
greatest eigenvalue is simple and is a Perron number. Moreover, it has an
associated eigenvector with strictly positive coordinates.

We call this greatest eigenvalue the Perron eigenvalue and an associated
eigenvector is a Perron eigenvector.

For sequences of invertible matrices, we have the following.

######  Theorem 2.6 (Osseledet’s Theorem).

Let $\mu$ be an ergodic invariant measure on the full shift
$(\mathcal{M}^{\mathbb{N}},S)$, where $\mathcal{M}\subset GL_{d}(\mathbb{R})$
is finite. For almost every sequence
$(M_{n})_{n\in\mathbb{N}}\in\mathcal{M}^{\mathbb{N}}$, there exists $0<r\leq
d$, $\theta_{1}>...>\theta_{r}$ and subspaces
$\mathbb{R}^{d}=E_{1}\supsetneqq...\supsetneqq E_{r-1}\supsetneqq
E_{r}=\\{0\\}$ such that

$v\in E_{i}\backslash
E_{i+1}\Longleftrightarrow\lim_{n\to\infty}\frac{1}{n}\log\left\lVert
vM_{[0,n)}\right\rVert=\theta_{i}.$

We call $\theta_{i}$ a Lyapunov exponent of $(M_{n})$ and $E_{i}$ the
corresponding Lyapunov space.

###  2.5 Substitution

Let $\mathcal{A}$ and $\mathcal{B}$ be two alphabets. A word morphism is a
morphism $\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ for the concatenation of
words. It is non erasing if $\forall a\in\mathcal{A},\
\left|\sigma(a)\right|\geq 1$. A substitution is a non-erasing word morphism.
We call $\mathcal{A}$ the domain alphabet and $\mathcal{B}$ the codomain
alphabet of $\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$. If both alphabets of a
substitution $\sigma$ are the same, we denote it $\mathcal{A}_{\sigma}$.

The matrix of a substitution $\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ is the
unique matrix $M_{\sigma}$ (or $\operatorname{ab}(\sigma)$) satisfying
$\operatorname{ab}(\sigma(w))=M_{\sigma}\operatorname{ab}(w)$ for every word
$w\in\mathcal{A}^{*}$.

For example, the matrix of the Tribonnacci substitution $a\mapsto ab,\
b\mapsto ac,\ c\mapsto a$ is $\begin{pmatrix}1&1&1\\\ 1&0&0\\\
0&1&0\end{pmatrix}$.

We say that a substitution is primitive, irreducible, Pisot, pseudo-
unimodular, etc… if its matrix has the corresponding property and if domain
and codomain alphabets are the same.

The language of a substitution $\sigma$ is the set $\mathcal{L}_{\sigma}$ of
factors of $\sigma^{n}(a)$, for $a\in\mathcal{A}$ and $n\in\mathbb{N}$, where
$\mathcal{A}$ is the domain alphabet of $\sigma$. The infinite (resp. bi-
infinite) subshift of a substitution $\sigma$ is the set of infinite (resp.
bi-infinite) words whose factors are in $\mathcal{L}_{\sigma}$. Note that the
language of a primitive substitution is the language of its subshift.

A substitution subshift is the subshift of a primitive substitution. A morphic
subshift is the subshift generated by the image by a substitution of a
substitution subshift.

Let $X$ be a subshift over an alphabet $\mathcal{A}$, and let
$\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ be a morphism. Let $Y$ be the shift
generated by $\sigma(X)$. Every element of $Y$ can be written in the form
$S^{k}\sigma(x)$, with $x\in X$ and $0\leq k<\left|\sigma(x_{0})\right|$. We
say that $\sigma$ is recognizable in $X$ if such a representation is unique
for every element of $Y$. We have the following (see [Mos96] Theorem 1).

######  Theorem 2.7 (Mossé).

Let $\sigma$ be a primitive aperiodic substitution. Then $\sigma$ is
recognizable in the bi-infinite subshift $X_{\sigma}$.

Note that a primitive substitution is aperiodic if its Perron eigenvalue is
not an integer by Remark 5.10.

The prefix-suffix automaton of a substitution
$\sigma:\mathcal{A}^{*}\to\mathcal{A}^{*}$ is a labeled directed graph with
vertices the alphabet $\mathcal{A}$ and with edges $a\xrightarrow{p,s}b$ if
and only if $\sigma(a)=pbs$. The prefix automaton is the same automaton where
labels $p,s$ are replaced by $p$. We denote
$a_{n+1}\xrightarrow{p_{n}}a_{n}...\xrightarrow{p_{0}}a_{0}$ if
$a_{k+1}\xrightarrow{p_{k}}a_{k}$ for every $0\leq k\leq n$.

Every element $x$ of the bi-infinite subshift $X_{\sigma}$ has a prefix-suffix
decomposition

$...\sigma^{3}(p_{3})\sigma^{2}(p_{2})\sigma(p_{1})p_{0}\cdot
a_{0}s_{0}\sigma(s_{1})\sigma^{2}(s_{2})\sigma^{3}(s_{3})...$

This decomposition is not always equal to $x$ since it may not define a bi-
infinite word. If $\sigma$ is recognizable, such a decomposition is unique.
Thus, it permits to define maps $p_{n}:X_{\sigma}\to\mathcal{A}^{*}$.

The following lemma gives a property of real coboundaries of a substitution
subshift.

######  Lemma 2.8.

Let $\sigma$ be a primitive substitution. The coboundary space
$R(X_{\sigma})^{\circ}$ is included in the sum of generalized left-eigenspaces
of $M_{\sigma}$ for eigenvalues roots of unity and zero.

In particular, if $M_{\sigma}$ has no eigenvalue root of unity nor zero, then
$X_{\sigma}$ has no non-trivial coboundary.

###### Proof.

We have $R^{\circ}M_{\sigma}\subseteq R^{\circ}$, since the image by $\sigma$
of a return word is a product of return words. Let $c\in R^{\circ}$. Then
$(cM_{\sigma}^{n})_{n\in\mathbb{N}}$ is bounded. Indeed, for every letter
$a\in\mathcal{A}$, $\sigma^{n}(a)\in\mathcal{L}_{\sigma}$, and
$c(\mathcal{L}_{\sigma})$ is bounded. Thus, $c$ is orthogonal to every
generalized eigenspace of $M_{\sigma}$ for an eigenvalue of modulus $>1$.
Moreover, $R$ is rational, thus $R^{\circ}$ is stable by field morphisms, so
it is orthogonal to every generalized eigenspace of $M_{\sigma}$ for an
eigenvalue not root of unity nor zero. ∎

###  2.6 Directive sequences

A directive sequence is an infinite sequence
$\bm{\sigma}=(\sigma_{n})_{n\in\mathbb{N}}$ of substitutions such that
$\forall n\in\mathbb{N}$,
$\sigma_{n}:\mathcal{A}_{n+1}^{*}\to\mathcal{A}_{n}^{*}$ (i.e. domains and
codomains are compatible to compose $\sigma_{n}\sigma_{n+1}$). We use the
standard notation $\sigma_{[i,j)}=\sigma_{i}...\sigma_{j-1}$.

A directive sequence is finitary if its set of substitutions is finite. We say
that a directive sequence $\bm{\sigma}$ is primitive if $\forall
k\in\mathbb{N}$, $\exists n\in\mathbb{N}$, $M_{[k,k+n)}>0$. It is strongly
primitive if $\exists n\in\mathbb{N},\ \forall k\in\mathbb{N},\
M_{[k,k+n)}>0$.

The language of a directive sequence $\bm{\sigma}$ is the set
$\mathcal{L}_{\bm{\sigma}}$ of factors of $\sigma_{[0,n)}(a)$, for
$n\in\mathbb{N}$, $a\in\mathcal{A}_{n}$. The infinite (resp. bi-infinite)
subshift of a directive sequence $\bm{\sigma}$ is the set $X_{\sigma}$ of
infinite (resp. bi-infinite) words whose factors are in the language of
$\bm{\sigma}$.

We denote $S:\mathcal{S}^{N}\to\mathcal{S}^{\mathbb{N}}$ the shift of
directive sequences over substitutions $\mathcal{S}$. We denote
$X_{\bm{\sigma}}^{(n)}$ (or just $X^{(n)}$) the subshift
$X_{S^{n}\bm{\sigma}}$. Idem for $\mathcal{L}_{\bm{\sigma}}^{(n)}$.

A directive sequence $\bm{\sigma}$ is recognizable if for all
$n\in\mathbb{N}$, $\sigma_{n}$ is recognizable in $X^{(n+1)}$. Note that if
substitutions of $\bm{\sigma}$ are unimodular and $X_{\bm{\sigma}}$ is
aperiodic, then $\bm{\sigma}$ is recognizable by Theorem 3.1 in [BSTY19].

The prefix-suffix diagram is a natural generalization of prefix-suffix
automaton to directive sequences, but it is no longer an automaton; instead it
is a Bratelli diagram with vertices $\mathcal{A}_{n}$ at level $n$ (alphabets
are considered to be disjoint) and edges
$a_{n+1}\xrightarrow{p_{n},s_{n}}a_{n}$ if and only if
$\sigma_{n}(a_{n+1})=p_{n}a_{n}s_{n}$. The prefix diagram is identical but
with only $p_{n}$ on labels of edges. Every element of $X_{\bm{\sigma}}$
admits a prefix-suffix decomposition

$..\sigma_{[0,3)}(p_{3})\sigma_{[0,2)}(p_{2})\sigma_{0}(p_{1})p_{0}\cdot
a_{0}s_{0}\sigma_{0}(s_{1})\sigma_{[0,2)}(s_{2})\sigma_{[0,3)}(s_{3})...$

where $...\xrightarrow{p_{n},s_{n}}a_{n}...\xrightarrow{p_{0},s_{0}}a_{0}$ is
an infinite path in the prefix-suffix diagram. But this decomposition is not
always equal to the original bi-infinite word: if $(p_{n})$ or $(s_{n})$ are
ultimately constant to $\epsilon$, then it does not gives a bi-infinite word.
See [CS01] for more details. When the directive sequence $\bm{\sigma}$ is
recognizable, such decomposition is unique so maps
$p_{n}:X^{(n)}\to\mathcal{A}_{n}^{*}$ and $a_{n}:X^{(n)}\to\mathcal{A}_{n}$
are well-defined.

##  3 A general sufficient condition to be an eigenvalue

We give a general sufficient condition for a number to be an eigenvalue of a
subshift.

######  Proposition 3.1.

Let $(X,S)$ be a minimal subshift over a finite alphabet $\mathcal{A}$. Let
$\varphi:\mathcal{A}^{*}\to\mathbb{R}$ be a morphism such that
$\varphi(\mathcal{L}_{X})$ is bounded and such that $\forall
a,b\in\mathcal{A}$, $\varphi(a)=\varphi(b)$ mod $1$. Then, $\varphi(a)$ is a
continuous eigenvalue of $(X,S)$.

Note that this proposition can be reformulated with $\varphi$ replaced by a
linear form of $\mathbb{R}^{\mathcal{A}}$, with the image of
$\operatorname{ab}(\mathcal{L}_{X})$ bounded. And the hypothesis on $\varphi$
can be replaced by $\varphi(W(x))$ is bounded for one $x\in X$.

To prove the proposition, we need the following.

######  Lemma 3.2.

Let $X$ be a minimal shift over a finite alphabet $\mathcal{A}$. Let
$\varphi\in(\mathbb{R}^{\mathcal{A}})^{*}$ be a linear form such that
$\varphi(\mathcal{L}_{X})$ is bounded. Let $x\in X$. Then, the map defined by
$\forall n\in\mathbb{N}$, $f(S^{n}x)=\varphi(\operatorname{ab}x_{[0,n)})$ can
be extended by continuity to $X$.

###### Proof.

If $x=w^{\omega}$ is periodic, then the hypothesis give
$\varphi(\operatorname{ab}w)=0$, so the map $f$ is well-defined. If the shift
$X$ is periodic, then it is equal to an orbit and the result is obvious.
Otherwise, we follow the proof of Lemma 8.2.5 in [MA20]. ∎

###### Proof of Proposition 3.1.

Let $t=\varphi(a)\in\mathbb{R}/\mathbb{Z}$. Let $x\in X$. We define a map $f$
on the orbit of $x$ by $f(S^{n}x)=nt=\varphi(x_{[0,n)})$ mod $1$. By Lemma
3.2, $f$ can be extended by continuity to $X$. Then, $f$ is a continuous
eigenfunction. ∎

######  Corollary 3.3.

Let $(X,S)$ be a minimal subshift. Let $x\in X$. If $W(x)$ is at bounded
distance of a line, then coordinates of the direction vector of sum $1$ are
continuous eigenvalues of $(X,S)$.

In other words if the discrepancy is bounded (see [Ada04] for a definition),
then frequencies of letters are continuous eigenvalues of the subshift.

######  Example 3.4.

Let $u=(ab)^{\omega}$ or let $u$ be the Thue-Morse sequence. $W(u)$ is at
bounded distance of the line with direction vector $(1,1)$, thus $1/2$ is an
eigenvalue of the generated subshift.

######  Corollary 3.5 (Pisot morphic subshift).

Let $\sigma$ be a Pisot substitution and $\tau$ be any substitution. Let $v$
be a Perron eigenvector of $\operatorname{ab}(\sigma)$, then coordinates of
$\frac{\operatorname{ab}(\tau)v}{\left\lVert\operatorname{ab}(\tau)v\right\rVert_{1}}$
are continuous eigenvalues of the subshift $(X_{\tau\sigma^{\omega}},S)$.

In other words, frequencies of letters are eigenvalues for such subshifts.
This result is due to Host (see (6.2) in [Hos86]) in the particular case where
$\tau$ is the identity.

###### Proof.

Let $f_{a}$ be the coordinate of
$\frac{\operatorname{ab}(\tau)v}{\left\lVert\operatorname{ab}(\tau)v\right\rVert_{1}}$
for letter $a$, which is in fact the frequency of $a$. Let
$\phi=f_{a}(1,...,1)-e_{a}$. Let us show that
$\phi(\operatorname{ab}\mathcal{L}_{\tau\sigma^{\omega}})$ is bounded. It is
equivalent to show that $\phi(W(u))$ is bounded for some $u\in
X_{\tau\sigma^{\omega}}$. We take for example the image by $\tau$ of a
periodic point of $\sigma$. Elements of $W(u)$ are of the form
$\operatorname{ab}(p_{0})+\sum_{n=0}^{N-1}M_{\tau}M_{\sigma}^{n}\operatorname{ab}(p_{n+1})$
for a path $a_{N+1}\xrightarrow{p_{N}}...\xrightarrow{p_{0}}a_{0}$ in the
prefix diagram of $\tau\sigma^{\omega}$. Thanks to the hypothesis, we have
$\phi M_{\tau}M_{\sigma}^{n}\xrightarrow[n\to\infty]{}0$, since $\phi
M_{\tau}M_{\sigma}^{n}v=0$, and this convergence is exponentially fast. Thus,
$\phi(W(u))$ is uniformly bounded. ∎

######  Corollary 3.6 ($\mathcal{S}$-adic with coboundary).

Let $\bm{\sigma}$ be a finitary primitive directive sequence. Let
$\pi:\mathbb{R}^{\mathcal{A}_{0}}\to\mathbb{R}$ and
$c:\mathbb{R}^{\mathcal{A}_{0}}\to\mathbb{R}$ be such that

$\sum_{n\in\mathbb{N}}\left\lVert(\pi+c)M_{[0,n)}\right\rVert<\infty,$

$c(\mathcal{L}_{\bm{\sigma}})$ is bounded and for every
$a,b\in\mathcal{A}_{0}$, $\pi(a)=\pi(b)$ mod $\mathbb{Z}$. Then $\pi(a)$ is a
continuous eigenvalue of $(X_{\bm{\sigma}},S)$.

###### Proof.

The primitivity gives that $(X_{\bm{\sigma}},S)$ is minimal. The hypothesis
tells us that $(\pi+c)(\mathcal{L}_{\bm{\sigma}})$ is bounded, by looking at
prefix-suffix decomposition of elements of $\mathcal{L}_{\bm{\sigma}}$, so
$\pi(\mathcal{L}_{\bm{\sigma}})$ is also bounded. Thus, $\pi$ satisfies the
hypothesis of Proposition 3.1 and it gives the conclusion. ∎

######  Example 3.7 ($\mathcal{S}$-adic with coboundary).

For any Bernouilli measure, almost every primitive directive sequence
$\bm{\sigma}$ over the following set of substitution has a set of eigenvalues
which is the $\mathbb{Z}$-module generated by frequencies of letters.

$\mathcal{S}=\left\\{\begin{array}[]{l}a\mapsto cb\\\ b\mapsto c\\\ c\mapsto
ab\end{array},\begin{array}[]{l}a\mapsto bc\\\ b\mapsto bcb\\\ c\mapsto
ca\end{array}\right\\}$

We easily check that $\bm{\sigma}$ is strongly primitive since every product
of length $4$ of incidence matrices is positive. Moreover, both substitutions
stabilize the graph

$\cdot$$\cdot$abc

thus $\begin{pmatrix}0&1&-1\end{pmatrix}$ is a coboundary of
$(X_{\bm{\sigma}},S)$ and it is a common left-eigenvector of incidence
matrices for eigenvalues $1$ or $-1$. Furthermore, both substitutions are
unimodular, so the sum of Lyapunov exponents is zero:
$\theta_{1}+\theta_{2}+\theta_{3}=0$. We deduce that
$\theta_{1}>\theta_{2}=0>\theta_{3}$. Moreover, for every integer vector
$w\in\mathbb{Z}^{\mathcal{A}}$, there exists $x,y\in\mathbb{R}$ such that
$x\begin{pmatrix}1&1&1\end{pmatrix}+y\begin{pmatrix}0&1&-1\end{pmatrix}-w\in
E_{3}$. The hypothesis of Corollary 3.6 is satisfied with the coboundary
$c=-y\begin{pmatrix}0&1&-1\end{pmatrix}$ and
$\pi=x\begin{pmatrix}1&1&1\end{pmatrix}-w$. Thus, coordinates of $v$ are
continuous eigenvalues, where $v$ is the vector of sum $1$ such that
$\bigcap_{n\in\mathbb{N}}M_{[0,n)}\mathbb{R}_{+}^{\mathcal{A}}=\mathbb{R}_{+}v$.
Moreover, by Theorem 4.1 thereafter there are no more continuous eigenvalues.
In other words, the set of continuous eigenvalues is the $\mathbb{Z}$-module
generated by frequencies of letters. In particular, $(X_{\bm{\sigma}},S)$ is
not weakly mixing.

Proposition 3.1 can be extended to find eigenvalues of $\mathbb{R}$-actions:

######  Proposition 3.8.

Let an $\mathbb{R}$-action on a space $Y$ with a Borel invariant probability
measure. Let $Z\subset Y$ be a subset such that $\forall y\in Y$, $\exists
t\in\mathbb{R}_{+}^{*}$, $t.y\in Z$, and with return times
$(h_{a})_{a\in\mathcal{A}}\in(\mathbb{R}_{+}^{*})^{\mathcal{A}}$ to $Z$, with
$\mathcal{A}$ finite. Let $(Z_{a})_{a\in\mathcal{A}}$ be the partition of $Z$
such that elements of $Z_{a}$ have return time $h_{a}$. Coding of orbits
define a subshift $(X,S)$ over alphabet $\mathcal{A}$. Assume that the coding
map $\operatorname{cod}:Z\to X$ is measurable, that the subshift is minimal,
and that $\pi(\mathcal{L}_{X})$ is bounded, where $\pi=\lambda h+w$, with row
vectors $w\in\mathbb{Z}^{\mathcal{A}}$ and $h=(h_{a})_{a\in\mathcal{A}}$.
Then, $\lambda$ is an eigenvalue of the $\mathbb{R}$-action.

###### Proof.

As in the proof of Proposition 3.1, we define a continuous map
$f:X\to\mathbb{R}/\mathbb{Z}$ such that $\forall x\in X$,
$f(S^{n}x)=\pi(x_{[0,n)})+f(x)=\lambda h\operatorname{ab}(x_{[0,n)})+f(x)$.
Then, $g=f\circ\operatorname{cod}$ is a measurable map such that $\forall z\in
Z$, $\forall t\in\mathbb{R}$ such that $t.z\in Z$, $g(t.z)=\lambda t+g(z)$.
Then, the map $h:Y\to\mathbb{R}/\mathbb{Z}$ defined by $h(t.z)=\lambda t+g(z)$
for every $t\in\mathbb{R}$ and $z\in Z$ is a measurable eigenfunction
associated with $\lambda$. ∎

##  4 Eigenvalues of $\mathcal{S}$-adic subshifts

This section aims to characterize continuous eigenvalues of $\mathcal{S}$-adic
subshift using coboundaries.

###  4.1 Main results

The two following theorems partially extends the result of Host for a single
substitution (see [Hos86] Theorem (1.4)).

######  Theorem 4.1.

Let $\bm{\sigma}$ be a finitary primitive directive sequence. If
$t\in\mathbb{R}/\mathbb{Z}$ is a continuous eigenvalue of
$(X_{\bm{\sigma}},S)$, then there exists $k\in\mathbb{N}$, and a linear form
$c:\mathbb{R}^{\mathcal{A}_{k}}\to\mathbb{R}$ such that
$c(\operatorname{ab}w)\in\mathbb{Z}$ for every return word $w$ of
$\mathcal{L}^{k}$ and such that

$(t(1,...,1)M_{[0,k)}+c)M_{[k,n)}\xrightarrow{n\to\infty}0.$

Note that such a map $c$ give a coboundary of $X_{S^{k}\bm{\sigma}}$. If we
remove the finitary hypothesis and replace it by
$\liminf_{n\to\infty}\left|\mathcal{A}_{n}\right|<\infty$, then we still have
the conclusion but with a convergence modulo $1$.

If the speed of convergence is fast enough, we have the reciprocal, which is a
generalization of Theorem 4.8 and Theorem 4.12 in [BBY22].

######  Theorem 4.2.

Let $\bm{\sigma}$ be a finitary, primitive and recognizable directive
sequence. If there exists $k\in\mathbb{N}$ and a linear form
$c:\mathbb{R}^{\mathcal{A}_{k}}\to\mathbb{R}$ such that
$c(\operatorname{ab}w)\in\mathbb{Z}$ for every return word $w$ of
$\mathcal{L}^{k}$ and such that

$\sum_{n\geq k}(t(1,...,1)M_{[0,k)}+c)M_{[k,n)}$

converges, then $t$ is a continuous eigenvalue of $(X_{\bm{\sigma}},S)$.

######  Remark 4.3.

In Theorem 4.2, if the substitution $\sigma_{[0,k)}$ is unimodular, then the
conclusion of the theorem holds without the recognizability hypothesis.
Indeed, $c$ can be decomposed as the sum of a real coboundary $\tilde{c}$ and
an integer row vector $w$ by Lemma 2.2, and
$\tilde{c}M_{[0,k)^{-1}}(\mathcal{L}_{X})$ is bounded and $wM_{[0,k)}^{-1}$ is
an integer row vector, thus hypotheses of Corollary 3.6 are satisfied with
$\pi=t(1...1)+wM_{[0,k)}^{-1}$.

###### Proof of Theorem 4.2.

Since $\bm{\sigma}$ is recognizable, the maps
$p_{n}:X_{\bm{\sigma}}\to\mathcal{L}^{(n)}$ are well-defined and continuous.
Then, we define a continuous map $f:X_{\bm{\sigma}}\to\mathbb{R}/\mathbb{Z}$
by

$f=\sum_{n=0}^{k-1}t(1...1)M_{[0,n)}\operatorname{ab}p_{n}+\sum_{n\geq
k}(t(1...1)M_{[0,k)}+c)\operatorname{ab}\sigma_{[k,n)}p_{n}+c(\theta_{k}),$

where the last occurrence of $c$ is a map
$c:X_{S^{k}\bm{\sigma}}\to\mathbb{R}/\mathbb{Z}$ such that
$c(Sx)+c(x_{0})=c(x)$, and $\theta_{k}:X_{\bm{\sigma}}\to
X_{S^{k}\bm{\sigma}}$ is the map such that
$\sigma_{[0,k)}(\theta_{k}(x))=\sigma_{[0,k-1)}(p_{k-1}(x))...\sigma_{0}(p_{1}(x))p_{0}(x)x$.
In other words, $\theta_{k}(x)$ is the word obtained after $k$ steps of
desubstitution from $x$. The map $f$ is continuous since the series is
normally convergent. Let us show that $f$ is an eigenfunction for the
eigenvalue $t$. Let $x\in X_{\bm{\sigma}}$ be such that $p_{n}(x)=\epsilon$
for every $n\in\mathbb{N}$. Since $\bm{\sigma}$ is primitive,
$(X_{\bm{\sigma}},S)$ is minimal, and it is enough to prove the equality
$f\circ S=f+t$ on the orbit of $x$. Let $m\in\mathbb{N}$. There exists $N\geq
k$ such that $p_{n}(S^{m}x)=\epsilon$ for every $n\geq N$, thus

$\displaystyle f(S^{m}x)$ $\displaystyle=$
$\displaystyle\sum_{n=0}^{k}t(1...1)\operatorname{ab}\sigma_{[0,n)}\operatorname{ab}p_{n}(S^{m}x)+$
$\displaystyle\quad\sum_{n=k}^{N}(t(1...1)\operatorname{ab}(\sigma_{[0,k)})+c)\operatorname{ab}\sigma_{[k,n)}p_{n}(S^{m}x)+c\theta_{k}(S^{m}x)$
$\displaystyle=$ $\displaystyle
t(1...1)\operatorname{ab}(\sigma_{[0,N)}(p_{N})...\sigma_{0}(p_{1})p_{0})+$
$\displaystyle\quad
c\operatorname{ab}(\sigma_{[k,N)}(p_{N})...\sigma_{k}(p_{k+1})p_{k})+c\theta_{k}(S^{m}x)$
$\displaystyle=$ $\displaystyle mt+c(\theta_{k}(x))=f(x)+mt.$

This before last equality comes from the relations

$\sigma_{[0,N)}(p_{N}(S^{m}x))...\sigma_{0}(p_{1}(S^{m}x))p_{0}(S^{m}x)S^{m}x=x,$
$\sigma_{[k,N)}(p_{N}(S^{m}x))...\sigma_{k}(p_{k+1}(S^{m}x))p_{k}(S^{m}x)\theta_{k}(S^{m}x)=\theta_{k}(x).$

∎

To prove Theorem 4.1, we need to introduce some important notions such as
nested sequences.

###  4.2 Nested sequences

In this subsection, we consider subshifts over infinite words. Let
$\bm{\sigma}$ be a directive sequence over alphabets $(\mathcal{A}_{n})$. In
this subsection we consider only first letters in images of letters, so we can
assume that substitutions of $\bm{\sigma}$ have constant lengths $1$. A nested
sequence is a sequence
$(a_{n})_{n\in\mathbb{N}}\in\Pi_{n\in\mathbb{N}}\mathcal{A}_{n}$ of letters
such that $\forall n\in\mathbb{N},\ \sigma_{n}(a_{n+1})=a_{n}$. We denote by
$\mathcal{N}_{\bm{\sigma}}$ (or just $\mathcal{N}$) the set of nested
sequences.

######  Lemma 4.4.

If alphabets $\mathcal{A}_{n}$ are non-empty, then $\mathcal{N}\neq\emptyset$.

###### Proof.

We assume that for all $n\in\mathbb{N}$, $\sigma_{n}$ has length one, up to
replace $\sigma_{n}(a)$ by its first letter for every $a\in\mathcal{A}_{n}$.
The intersection $\bigcap_{n\in\mathbb{N}}\sigma_{[0,n)}(\mathcal{A}_{n})$ is
non-empty since $(\sigma_{[0,n)}(\mathcal{A}_{n}))$ is a decreasing sequence
of non-empty subsets of $\mathcal{A}_{0}$. We then construct a nested sequence
$(a_{n})$ by induction: if $a_{n}\in\bigcap_{k\geq
n}\sigma_{[n,k)}(\mathcal{A}_{k})$, then we can find $a_{n+1}\in\bigcap_{k\geq
n+1}\sigma_{[n+1,k)}(\mathcal{A}_{k})$ such that $\sigma_{n}(a_{n+1})=a_{n}$.
∎

The following tells us that nested sequences are almost pairwise disjoint.

######  Lemma 4.5.

If $(a_{n})$ and $(b_{n})$ are two different nested sequences, then

$\exists n_{0}\in\mathbb{N},\ \forall n\geq n_{0},\ a_{n}\neq b_{n}.$

###### Proof.

If $a_{n_{0}}=b_{n_{0}}$, then for every $n\leq n_{0}$, $a_{n}=b_{n}$. Thus,
if the conclusion was not true, then the two nested sequences would be equal.
∎

We deduce the following.

######  Lemma 4.6.

$\left|\mathcal{N}\right|\leq\liminf_{n\to\infty}\left|\mathcal{A}_{n}\right|.$

We assume in the following that alphabets $\mathcal{A}_{n}$ are disjoints. For
each $k\in\mathbb{N}$, let
$\mathcal{B}_{k}=\\{a\in\mathcal{A}_{k}\mid\forall(a_{n})\in\mathcal{N},\
\sigma_{[0,k)}(a)\not\in[a_{0}]\\}$. This set corresponds to letters that
never reach a nested sequence. We have the following.

######  Lemma 4.7.

$\exists n_{0}\in\mathbb{N},\ \forall n\geq n_{0},\
\mathcal{B}_{n}=\emptyset.$

###### Proof.

If $a\in\mathcal{B}_{n+1}$, then the first letter of $\sigma_{n}(a)$ is in
$\mathcal{B}_{n}$. Thus, we can define
$\tau_{n}:\mathcal{B}_{n+1}\to\mathcal{B}_{n}$ such that $\tau_{n}(a)$ is the
first letter of $\sigma_{n}(a)$. By definition of the sets $\mathcal{B}_{n}$,
$(\tau_{n})$ has no nested sequence. Thus, by Lemma 4.4, $\exists
n_{0}\in\mathbb{N},\ \mathcal{B}_{n_{0}}=\emptyset$. Then, for every $n\geq
n_{0}$, $\mathcal{B}_{n}=\emptyset$ since
$\tau_{[n_{0},n)}(\mathcal{B}_{n})\subseteq\mathcal{B}_{n_{0}}$. ∎

We deduce the following.

######  Lemma 4.8.

There exists $n_{0}\in\mathbb{N}$ and a map $\alpha:\bigcup_{n\geq
n_{0}}\mathcal{A}_{n}\to\mathcal{N}$ such that $\forall n\geq n_{0},\ \forall
a\in\mathcal{A}_{n},\ \sigma_{[0,n)}(a)\in[\alpha(a)_{0}]$.

###  4.3 Proof of Theorem 4.1

Let $\bm{\sigma}$ be a primitive directive sequence with
$\liminf_{n\to\infty}\left|\mathcal{A}_{n}\right|<\infty$. Thanks to
Proposition 2.1, we can work only with right-infinite subshifts as in previous
subsection.

######  Lemma 4.9.

For every nested sequence $\bm{a}=(a_{n})\in\mathcal{N}$,
$(\sigma_{[0,n)}(a_{n}))$ is a nested sequence of words that converges to an
infinite word $w_{\bm{a}}$.

Let $f$ be a continuous eigenfunction associated with an eigenvalue
$t\in\mathbb{R}/\mathbb{Z}$. Let

$\mathcal{F}=\left\\{f(w_{\bm{a}})\in\mathbb{R}/\mathbb{Z}\mid\bm{a}\in\mathcal{N}\right\\}.$

By Lemma 4.6, the set $\mathcal{F}$ is finite. Let $\epsilon>0$ such that
$\epsilon<\min\\{\left|x-y\right|\mid x\neq y\in\mathcal{F}\\}$. Let
$n_{1}\in\mathbb{N}$ be such that

$\forall\bm{a}\in\mathcal{N},\
\left|f\left(\left[\sigma_{[0,n_{1})}(a_{n_{1}})\right]\right)-f(w_{\bm{a}})\right|\leq\epsilon/4.$

Then, let $n_{0}\in\mathbb{N}$ and $\alpha$ be given by Lemma 4.8 for the
directive sequence $S^{n_{1}}\bm{\sigma}$. We have

$\displaystyle\forall n\geq n_{0},\ \forall x\in X_{\bm{\sigma}}^{(n)},\
\left|f(\sigma_{[0,n)}(x))-v_{x_{0}}\right|\leq\epsilon/4,$ (1)

where we denote $v_{a}=f(w_{\alpha(a)})$.

######  Lemma 4.10.

$\forall n\geq n_{0},\ \forall ab\in\mathcal{L}^{(n)},\
\left|th_{n}(a)+v_{a}-v_{b}\right|\leq\epsilon/2,$

where $h_{n}(a)=\left|\sigma_{[0,n)}(a)\right|=(1...1)M_{[0,n)}e_{a}$.

###### Proof.

For every $n\geq n_{0}$, for every $ab\in\mathcal{L}_{\bm{\sigma}}^{(n)}$ and
for every $u\in[ab]$, we have

$th_{n}(a)+f(\sigma_{[0,n)}(u))=f(S^{h_{n}(a)}\sigma_{[0,n)}(u))=f(\sigma_{[0,n)}(Su)).$

We deduce the result by triangular inequality, using (1). ∎

We define $c_{n}:\mathbb{R}^{\mathcal{A}}\to\mathbb{R}/\mathbb{Z}$ by
$c_{n}(a)=v_{a}-v_{b}$ if $ab\in\mathcal{L}^{(n)}$. It is well defined.
Indeed, if $ab\in\mathcal{L}^{(n)}$ and $ac\in\mathcal{L}^{(n)}$ then by Lemma
4.10 and by triangular inequality, we have
$\left|v_{c}-v_{b}\right|\leq\epsilon<\min\\{\left|x-y\right|\mid x\neq
y\in\mathcal{F}\\}$, thus $v_{b}=v_{c}$. And if $w$ is a return word of
$\mathcal{L}_{n}$, then clearly $c_{n}(w)=0$ since we have
$wa\in\mathcal{L}^{(n)}\Rightarrow c_{n}(w)=v_{w_{0}}-v_{a}$. Thus, $c_{n}$ if
a coboundary of $X_{\bm{\sigma}}^{(n)}$.

######  Lemma 4.11.

For every $n\geq n_{0}$, we have $c_{n+1}=c_{n}\circ\sigma_{n}$.

###### Proof.

Let $ab\in\mathcal{L}^{(n+1)}$. We have $c_{n+1}(a)=v_{a}-v_{b}$. Let $a_{0}$
and $b_{0}\in\mathcal{L}^{(n)}$ be respectively the first letters of
$\sigma_{n}(a)$ and $\sigma_{n}(b)$. We have
$\sigma_{n}(a)b_{0}\in\mathcal{L}^{(n)}$, thus
$c_{n}(\sigma_{n}(a))=v_{a_{0}}-v_{b_{0}}$. Now, by definition we have
$v_{a}=v_{a_{0}}$ and $v_{b}=v_{b_{0}}$ thus
$c_{n+1}(a)=c_{n}(\sigma_{n}(a))$. ∎

Since $\epsilon>0$ could be chosen arbitrarily small, Lemma 4.10 gives

$t(1...1)M_{[0,n)}+c_{n}\xrightarrow{n\to\infty}0\text{ mod }1.$

Thus, by Lemma 4.11 we get
$(t(1...1)M_{[0,n_{0})}+c_{n_{0}})M_{[n_{0},n)}\xrightarrow{n\to\infty}0\text{
mod }1$.

Now we need the following easy generalization of Lemma 1 in [Hos86]. It is
where we use the finitary hypothesis.

######  Lemma 4.12.

Let $(M_{n})_{n\in\mathbb{N}}\in M_{d_{n},d_{n+1}}(\mathbb{Z})$ with bounded
coefficients and with $\forall n\in\mathbb{N},d_{n}\geq 1$. If
$v\in\mathbb{R}^{d_{0}}$ is such that
$vM_{[0,n)}\xrightarrow{n\to\infty}0\text{ mod }1$. Then there exists
$k\in\mathbb{N}$ and $w\in\mathbb{Z}^{d_{k}}$ such that
$(vM_{[0,k)}-w)M_{[k,n)}\xrightarrow{n\to\infty}0$.

###### Proof.

For every $n\in\mathbb{N}$, let $\epsilon_{n}\in(-1/2,1/2]^{d_{n}}$ and
$w_{n}\in\mathbb{Z}^{d_{n}}$ be such that $vM_{[0,n)}=\epsilon_{n}+w_{n}$. We
have
$w_{n}M_{n}-w_{n+1}=\epsilon_{n+1}-\epsilon_{n}M_{n}\xrightarrow{n\to\infty}0$,
and $w_{n}M_{n}-w_{n+1}$ has integer coefficients. Thus there exists
$k\in\mathbb{N}$ such that $\forall n\geq k,\ w_{n}=w_{n+1}M_{n}$. Then,
$(vM_{[0,k)}-w_{k})M_{[k,n)}\xrightarrow{n\to\infty}0$. ∎

Let $\tilde{c}_{n_{0}}:\mathbb{R}^{\mathcal{A}_{n_{0}}}\to\mathbb{R}$ be any
representative of $c_{n_{0}}$. We use this lemma with matrices of the
directive sequence $S^{n_{0}}\sigma$ and with the vector
$t(1...1)M_{[0,n_{0})}+\tilde{c}_{n_{0}}$. Then, it gives a $k\geq n_{0}$ and
a vector $w\in\mathbb{Z}^{\mathcal{A}_{k}}$ such that

$((t(1...1)M_{[0,n_{0})}+\tilde{c}_{n_{0}})M_{[n_{0},k)}-w)M_{[k,n)}\xrightarrow{n\to\infty}0.$

Let $c=\tilde{c}_{n_{0}}M_{[n_{0},k)}-w$. Then, we have

$(t(1...1)M_{[0,k)}+c)M_{[k,n)}\xrightarrow{n\to\infty}0.$

Let $w$ be a return word of $\mathcal{L}^{\mathcal{A}_{k}}$, then we clearly
have $c(w)\in\mathbb{Z}$ since $c=c_{k}$ mod $\mathbb{Z}^{\mathcal{A}_{k}}$.
This ends the proof of Theorem 4.1.

##  5 Eigenvalues of morphic subshifts

Recall that a morphic subshift is the subshift of a directive sequence of the
form $\tau\sigma^{\omega}$. In other words, it is the subshift generated by
$\tau(X_{\sigma})$.

###  5.1 Characterization of eigenvalues of morphic subshifts

The following result allows us to compute eigenvalues of morphic subshifts.

######  Theorem 5.1.

Let $\sigma$ be a primitive aperiodic substitution, and let $\tau$ be a word
morphism recognizable in $X_{\sigma}$. Then, the set of eigenvalues of
$(X_{\tau\sigma^{\omega}},S)$ is

$\left(W\cap\Delta_{M_{\sigma}}\right)v$

where

  * •

$v$ is a generalized eigenvector of $M_{\sigma}$ for an eigenvalue of modulus
$\geq 1$, annihilated by coboundaries (for example the Perron eigenvector) and
normalized such that $(1...1)M_{\tau}v=1$,

  * •

$\Delta_{M_{\sigma}}=\\{w\in\mathbb{Q}^{\mathcal{A}_{\sigma}}\mid\exists
n\in\mathbb{N},\ wM_{\sigma}^{n}\in\mathbb{Z}^{\mathcal{A}_{\sigma}}\\}$,
can be replaced by
$\bigcup_{n\in\mathbb{N}}\mathbb{Z}^{\mathcal{A}_{\sigma}}M_{\sigma}^{-1}$
where $M_{\sigma}^{-1}$ is the pseudo-inverse of $M_{\sigma}$, defined in
Subsection 2.4,

  * •

$W=\\{w\in\mathbb{Q}^{\mathcal{A}_{\sigma}}\mid\exists x\in\mathbb{R}^{d},\
xCV=wV\\}=\mathbb{Q}^{\mathcal{A}_{\sigma}}\cap(C^{\circ}\cap\operatorname{span}(V))^{\circ}$
is a $\mathbb{Q}$-vector space where

    * –

$V$ is a matrix whose columns are bases of generalized eigenspaces for
eigenvalues of modulus $\geq 1$,

    * –

$C$ is a matrix whose first row is $(1...1)M_{\tau}$ and other rows are a
basis of the set of coboundaries $R^{\circ}$ (see definition in Subsection
2.3).

The set $\Delta_{M_{\sigma}}$ is linked with another invariant called
dimension group, see [DP22] for more details.

Note that if we remove the recognizability or aperiodicity hypothesis, then
the set of eigenvalues is between $(W\cap\mathbb{Z}^{\mathcal{A}_{\sigma}})v$
and $(W\cap\Delta_{M_{\sigma}})v$.

We show that eigenvalues of morphic subshifts are continuous.

######  Proposition 5.2.

Under hypotheses of the previous theorem, the following statements are
equivalent

  * •

$t\in\mathbb{R}/\mathbb{Z}$ is a measurable eigenvalue of
$(X_{\tau\sigma^{\omega}},S)$.

  * •

$t\in\mathbb{R}/\mathbb{Z}$ is a continuous eigenvalue of
$(X_{\tau\sigma^{\omega}},S)$.

  * •

There exists an integer $k\in\mathbb{N}$, a real coboundary $c$ of
$X_{\sigma}$, and a row vector $w\in\mathbb{Z}^{\mathcal{A}_{\sigma}}$ such
that for every generalized eigenvector $v$ of $M_{\sigma}$ associated with an
eigenvalue of modulus $\geq 1$,

$(t(1...1)M_{\tau}M_{\sigma}^{k}+c-w)v=0.$

###### Proof of Proposition 5.2.

By Theorem 2.7, $\sigma$ is recognizable in the bi-infinite subshift
$X_{\sigma}$. Thus, the directive sequence $\tau\sigma^{\omega}$ is
recognizable and it is primitive. The last point gives a map
$c:\mathbb{R}^{\mathcal{A}_{\sigma}}\to\mathbb{R}$ such that
$c(r)\in\mathbb{Z}$ for every return word $r$ of $X_{\sigma}$ and such that
$(t(1...1)M_{\tau}M_{\sigma}^{k}+c)M_{\sigma}^{n}\xrightarrow{n\to\infty}0$.
Note that the convergence is exponential. Thus, by Theorem 4.2, this implies
that $t$ is a continuous eigenvalue of $(X_{\tau\sigma^{\omega}},S)$.

Obviously, a continuous eigenvalue is a measurable eigenvalue.

Let $t\in\mathbb{R}/\mathbb{Z}$ be a measurable eigenvalue. We can describe
the shift $(X_{\tau\sigma^{\omega}},S)$ with another directive sequence which
is left-proper, using the notion of return substitution, defined in Subsection
5.4 thereafter. Indeed, we can assume that there exists
$a\in\mathcal{A}_{\sigma}$ such that $\sigma(a)\in[a]$ even if its means
replacing $\sigma$ by a power of itself. Then, a power of the return
substitution $\partial_{a}\sigma$ is left-proper and there exists
$\theta:\mathbb{R}\to\mathcal{A}_{\sigma}^{*}$ such that
$\theta\circ\partial_{a}\sigma=\sigma\circ\theta$. Thus, the directive
sequence $\tau\theta(\partial_{a}\sigma)^{\omega}$ has the same subshift as
$\tau\sigma^{\omega}$. It implies by Theorem 7.3.5 in [DP22] (see also [Dur00]
and [Dur03]) that the shift is linearly recurrent. Then, thanks to Proposition
14 in [CDHM03] the eigenvalue $t$ is continuous.

Let $t\in\mathbb{R}/\mathbb{Z}$ be a continuous eigenvalue of
$(X_{\tau\sigma^{\omega}},S)$. Then, by Theorem 4.1, there exists
$k\in\mathbb{N}$ and a map $c:\mathbb{R}^{\mathcal{A}_{\sigma}}\to\mathbb{R}$
such that $c(r)\in\mathbb{Z}$ for every return word $r$ of $X_{\sigma}$ and
such that

$(t(1...1)M_{\tau}M_{\sigma}^{k}+c)M_{\sigma}^{n}\xrightarrow{n\to\infty}0.$

Then, by Lemma 2.2, $c$ can be decomposed as the difference of a coboundary
$c^{\prime}\in(\mathbb{R}^{\mathcal{A}_{\sigma}})^{*}$ and an integer row
vector $w\in\mathbb{Z}^{\mathcal{A}_{\sigma}}$. And for every row vector $u$
we have $uM_{\sigma}^{n}\xrightarrow{n\to\infty}0\Longleftrightarrow uV=0$
where $V$ is a matrix whose columns are generalized eigenvectors for
eigenvalues of modulus $\geq 1$. Hence, we obtain the third point. ∎

###### Proof of Theorem 5.1.

The set $W$ is indeed a $\mathbb{Q}$-vector subspace of
$\mathbb{Q}^{\mathcal{A}_{\sigma}}$ since we obtain it as the kernel of some
matrix obtained by making the system $xCV=wV$ in echelon form (see Subsection
5.2 for more details).

Let us show that we can replace $\Delta_{M_{\sigma}}$ as claimed. Let
$I=\bigcap_{n\in\mathbb{N}}\mathbb{Q}^{\mathcal{A}_{\sigma}}M_{\sigma}^{n}$ be
the eventual left-image of $M_{\sigma}$ and let
$E_{0}=\bigcup_{n\in\mathbb{N}}\ker_{\operatorname{left}}M_{\sigma}^{n}$ be
its generalized left-eigenspace for the eigenvalue $0$. We have
$I+E_{0}=\mathbb{Q}^{\mathcal{A}_{\sigma}}$. The set $E_{0}$ is included in
both $W$ and $\Delta_{M}$, and $W\cap\Delta_{M}$ is an additive group. Thus,
we have $E_{0}+(W\cap\Delta_{M_{\sigma}}\cap I)=W\cap\Delta_{M_{\sigma}}$. The
set $I$ is invariant by left multiplication by $M_{\sigma}$, and the
restriction of $M_{\sigma}$ to $I$ is invertible, so we have $\Delta_{M}\cap
I=\bigcup_{n\in\mathbb{N}}\mathbb{Z}^{\mathcal{A}_{\sigma}}M_{\sigma}^{-n}\cap
I$. Thus, $(W\cap\Delta_{M_{\sigma}})v=(W\cap\Delta_{M_{\sigma}}\cap
I)v=(W\cap\bigcup_{n\in\mathbb{N}}\mathbb{Z}^{\mathcal{A}_{\sigma}}M_{\sigma}^{-n})v$.

Let $w\in W\cap\Delta_{M_{\sigma}}$. Let us prove that $wv$ is an eigenvalue
of $(X_{\tau\sigma^{\omega}},S)$. By definition of $W$, there exists
$x\in\mathbb{R}^{d}$ such that $xCV=wV$. By definition of $C$, $xC$ is of the
form $t(1...1)M_{\tau}+c$ for some real coboundary $c\in R^{\circ}$ of
$X_{\sigma}$. By definition of $\Delta_{M_{\sigma}}$, there exists
$k\in\mathbb{N}$ such that
$wM_{\sigma}^{k}\in\mathbb{Z}^{\mathcal{A}_{\sigma}}$. Then
$(t(1...1)M_{\tau}+c-w)V=0$, and since generalized eigenspaces are invariant
by $M_{\sigma}$, we have
$(t(1...1)M_{\tau}M_{\sigma}^{k}+c^{\prime}-w^{\prime})V=0$, where
$c^{\prime}=cM_{\sigma}^{k}\in R^{\circ}$ is a real coboundary of $X_{\sigma}$
and $w^{\prime}=wM_{\sigma}^{k}\in\mathbb{Z}^{\mathcal{A}_{\sigma}}$. By
Proposition 5.2, $t$ is an eigenvalue of $(X_{\tau\sigma^{\omega}},S)$.
Furthermore, we have $wv=(t(1...1)M_{\tau}+c)v=t(1...1)M_{\tau}v=t$.

Reciprocally, let $t$ be an eigenvalue. By Proposition 5.2, there exists a
real coboundary $c\in R^{\circ}$, $k\in\mathbb{N}$ and
$w\in\mathbb{Z}^{\mathcal{A}_{\sigma}}$ such that
$(t(1...1)M_{\tau}M_{\sigma}^{k}+c-w)V=0$. Then, since generalized eigenspaces
are invariant by $M_{\sigma}^{-1}$, we have
$(t(1...1)M_{\tau}+c^{\prime}-w^{\prime})V=0$ where
$c^{\prime}=cM_{\sigma}^{-k}$ and $w^{\prime}=wM_{\sigma}^{-k}$, where
$M_{\sigma}^{-1}$ is the pseudo-inverse of $M_{\sigma}$. We have
$w^{\prime}\in\bigcup_{n\in\mathbb{N}}\mathbb{Z}^{\mathcal{A}_{\sigma}}M_{\sigma}^{-n}$.
Now, we have $M_{\sigma}R\subseteq R$ since the image of a return word by
$\sigma$ is a product of return words. So $(R^{\circ}\cap
I)M_{\sigma}\subseteq R^{\circ}\cap I$ where
$I=\bigcap_{n\in\mathbb{N}}\mathbb{Q}^{\mathcal{A}_{\sigma}}M_{\sigma}^{n}$.
Since the restriction of $M_{\sigma}$ to $I$ is invertible, and
$R^{\circ}M_{\sigma}^{n}\subseteq R^{\circ}\cap I$ for $n$ large enough, we
get $(R^{\circ}\cap I)M_{\sigma}=R^{\circ}\cap I$. Hence, $c^{\prime}V\in
R^{\circ}V$. Thus, there exists $x$ such that $xCV=w^{\prime}V$. We deduce
that $w^{\prime}\in W$. Moreover we have
$w^{\prime}v=(t(1...1)M_{\tau}+c^{\prime})v=t(1...1)M_{\tau}v=t$. ∎

###  5.2 The algorithm

Let $\sigma$ and $\tau$ be two substitutions with $\sigma$ primitive aperiodic
and $\tau$ recognizable in $X_{\sigma}$. The algorithm to compute eigenvalues
of $(X_{\tau\sigma^{\omega}},S)$ is the following.

  * •

Compute the coboundary space $R^{\circ}$ of $X_{\sigma}$. See Subsection 5.3
for more details.

  * •

Let $C$ be the matrix with first row $(1...1)M_{\tau}$ and other rows with a
basis of the coboundary space $R^{\circ}$. Let $d$ be the number of rows of
$C$.

  * •

Compute a matrix $V$ whose columns are bases of generalized eigenspaces of
$M_{\sigma}$ for eigenvalues of modulus $\geq 1$, with coordinates in the
algebraic field $\overline{\mathbb{Q}}$.

  * •

Echelon the system $xCV=wV$ with unknowns $x\in\mathbb{R}^{d}$, where $w$ is a
row vector. It gives a matrix whose columns are linear combination of columns
of $V$ and whose left-kernel intersected with
$\mathbb{Q}^{\mathcal{A}_{\sigma}}$ gives $W$. Decompose each columns in a
basis of a common number field of coefficients. It gives a rational matrix
whose left-kernel is $W$. Then we can compute a basis of the
$\mathbb{Q}$-vector space $W$.

  * •

Compute the Perron eigenvector $v$ of $M_{\sigma}$ such that
$(1...1)M_{\tau}v=1$.

  * •

Then, the set of eigenvalues is

$(W\cap\bigcup_{n\in\mathbb{N}}\mathbb{Z}^{\mathcal{A}_{\sigma}}M_{\sigma}^{-k})v$

where $M_{\sigma}^{-1}$ is the pseudo-inverse of $M_{\sigma}$.

Note that we may replace the Perron eigenvector $v$ by any generalized
eigenvector annihilated by coboundaries and such that $(1...1)M_{\tau}v=1$.
Note that in general, the set $(W\cap\Delta_{M_{\sigma}})v$ is not equal to
$Wv\cap\Delta_{M_{\sigma}}v$ since $W$ has no reason to be
$M_{\sigma}$-invariant. However, in many situations, the set of eigenvalues
can be made more explicit:

  * •

If $\sigma$ is pseudo-unimodular (i.e. the product of non-zero eigenvalues is
$\pm 1$), then the set of eigenvalues is
$(W\cap\mathbb{Z}^{\mathcal{A}_{\sigma}})v$.

Indeed, by Lemma 6.4 in [Mer23], if $M_{\sigma}$ is pseudo-unimodular then
$\Delta_{M_{\sigma}}$ is equal to $\mathbb{Z}^{\mathcal{A}_{\sigma}}$ modulo
the generalized eigenspace for the eigenvalue $0$.

  * •

If the matrix $CV$ is invertible, or more generally if $WM_{\sigma}=W$, and if
$v$ is an eigenvector for an eigenvalue $\beta$, then the set of eigenvalues
is

$\mathbb{Z}\left[\frac{1}{\beta}\right](W\cap\mathbb{Z}^{\mathcal{A}_{\sigma}})v.$

Indeed, we have

$\left(W\cap\bigcup_{n\in\mathbb{N}}\mathbb{Z}^{\mathcal{A}_{\sigma}}M_{\sigma}^{-n}\right)v=\bigcup_{n\in\mathbb{N}}(WM_{\sigma}^{n}\cap\mathbb{Z}^{\mathcal{A}_{\sigma}})v/\beta^{n}.$

  * •

If $(1...1)M_{\tau}$ is a left-eigenvector of $M_{\sigma}$ for an eigenvalue
$\beta$, then we fall into the previous case. Indeed, it gives that $C$ and
$CM_{\sigma}$ have same row space modulo the generalized left-eigenspace of
$M_{\sigma}$ for the eigenvalue $0$ and we have
$xCV=wV\Leftrightarrow(xC-w)M_{\sigma}V=0\Leftrightarrow
xCM_{\sigma}V=wM_{\sigma}V$, so $WM_{\sigma}=W$.

Note that when $\tau=\operatorname{id}_{\mathcal{A}_{\sigma}}$, it corresponds
to the constant length case.

  * •

If there exists $n\in\mathbb{N}$ such that $M_{\sigma}^{n}=0$ mod
$\det(M_{\sigma})$. Then, the set of eigenvalues is

$\mathbb{Z}\left[\frac{1}{\det(M_{\sigma})}\right](W\cap\mathbb{Z}^{\mathcal{A}_{\sigma}})v.$

Indeed, under this hypothesis we have
$\Delta_{M}=\bigcup_{n\in\mathbb{N}}\frac{1}{\det(M_{\sigma})^{n}}\mathbb{Z}^{\mathcal{A}_{\sigma}}$.

See Section 7 for examples of computations of eigenvalues. Algorithms of this
paper have been implemented in the package eigenmorphic (see
https://gitlab.com/mercatp/eigenmorphic) for the Sage math software (see
https://www.sagemath.org/). It can be installed with the command line

⬇

$ sage -pip install eigenmorphic

Examples of computations with this package can be found here:
https://www.i2m.univ-amu.fr/perso/paul.mercat/SubshiftsEigenvalues.pdf

###  5.3 Computation of coboundaries

The following lemma permits to reduce the computation of the return space to
the one of return space on only one letter, if we want to compute coboundaries
only modulo the generalized left eigenspace $E_{0}$ for the eigenvalue $0$. It
is indeed what we need in the computation of eigenvalues of morphic subshifts
since $E_{0}V=0$.

######  Lemma 5.3.

Let $\sigma$ be a primitive substitution over alphabet $\mathcal{A}$ and let
$a\in\mathcal{A}$. Let $R$ be the return space and $R_{a}$ be the return space
on letter $a$. Let
$I=\bigcap_{n\in\mathbb{N}}M_{\sigma}^{n}\mathbb{Q}^{\mathcal{A}}$. Then

$I\cap R=I\cap R_{a}\quad\text{ and }\quad
R^{\circ}+E_{0}=R_{a}^{\circ}+E_{0},$

where $E_{0}=I^{\circ}$ is the generalized left-eigenspace of $M_{\sigma}$ for
the eigenvalue $0$.

###### Proof.

The image of a return word by a substitution is a product of return words.
Thus $M_{\sigma}R\subseteq R$. Since $\mathchoice{{M_{\sigma}\,\smash{\vrule
height=5.46666pt,depth=1.62633pt}}_{\,I}}{{M_{\sigma}\,\smash{\vrule
height=5.46666pt,depth=1.62633pt}}_{\,I}}{{M_{\sigma}\,\smash{\vrule
height=3.82666pt,depth=1.16167pt}}_{\,I}}{{M_{\sigma}\,\smash{\vrule
height=2.73332pt,depth=1.16167pt}}_{\,I}}$ is invertible, we have
$M_{\sigma}(R\cap I)=R\cap I$. Let $k\in\mathbb{N}$ such that
$M_{\sigma}^{k}>0$. Let $(w)_{w\in J}$ be a family of return words such that
$(\operatorname{ab}w)_{w\in J}$ is a basis of $R\cap I$. Then,
$(M_{\sigma}^{k}\operatorname{ab}w)_{w\in J}$ is also a basis of $R\cap I$.
Let $w\in J$. Let $p,s\in\mathcal{A}^{*}$ such that $\sigma^{k}(w_{0})=pas$.
The word $\sigma^{k}(ww_{0})$ is in the language of $\sigma$, so
$as\sigma^{k}(Sw)p$ is a product of return word on letter $a$. Moreover,
$\operatorname{ab}(as\sigma^{k}(Sw)p)=\operatorname{ab}(\sigma^{k}(w))$. Thus
$R\cap I\subseteq R_{a}\cap I$. The other inclusion is obvious. Then, we have
$R^{\circ}+E_{0}=(R\cap I)^{\circ}=(R_{a}\cap I)^{\circ}=R_{a}^{\circ}+E_{0}$.
∎

The computation of the set $\mathcal{R}_{a}$ of return words on letter $a$ can
be done by computing a substitution called return substitution and whose
alphabet is the set of return words on letter $a$. This is done in the next
subsection.

######  Remark 5.4.

The coboundary space can be computed more efficiently by computing the
coboundary graph, that is the largest invariant oriented graph with edges
labeled by letters where each letter appears exactly once.

###  5.4 Return substitution

The notion of return substitution comes from F. Durand (see [Dur98]). We
recall the definition and how to compute it even if it is well-know, in order
to have a complete algorithm. Let $\sigma$ be a primitive substitution, and
let $a\in\mathcal{A}_{\sigma}$ be a letter such that $\sigma(a)=a$. Note that
such a letter always exists up to replacing $\sigma$ with a power of itself.
The return substitution on letter $a$ is denoted as $\sigma_{a}$ or
$\partial_{a}\sigma$. Its alphabet is the set $\mathcal{R}_{a}$ of return
words on letter $a$, and its satisfies
$\sigma_{a}\circ\varphi_{a}=\varphi_{a}\circ\sigma$, where
$\varphi_{a}:\mathcal{R}_{a}\to\mathcal{A}_{\sigma}^{*}$ maps an element of
$\mathcal{R}_{a}$ to the corresponding word. We can also extend this
definition in an obvious manner: if $w$ is a prefix of a fixed point of
$\sigma$, then we the define the return substitution $\sigma_{w}$ accordingly.

We can compute the return substitution with the following algorithm:

  * •

Compute $\sigma^{n}(a)$ from $n=1$ and up to find a first return word on
letter $a$.

  * •

Take the image of a return word $r$ by $\sigma$: it is a product of return
words. We deduce what is $\sigma_{a}(r)$.

  * •

Continue the previous step with every new return word found.

When this algorithm stops, then we have found every return word on letter $a$.
Indeed, if $x$ is the fixed point of $\sigma$ starting by letter $a$ and if
$A$ is such that $\varphi_{a}(A)$ is the first return word found, then $x$ is
equal to $\varphi_{a}(y)$ where $y$ is the fixed point of $\sigma_{a}$
starting by letter $A$. Since $\sigma$ is primitive, every return word appears
in $x$, thus the alphabet of $\sigma_{a}$ is the set of return words on letter
$a$.

######  Example 5.5.

Consider the Thue-Morse substitution

$\sigma:a\mapsto ab,\ b\mapsto ba.$

If we compute $\sigma^{2}(a)=abba$, we see that $abb$ is a return word. Then,
we compute $\sigma(abb)=abbaba$. We found two new return words: $\\{ab,a\\}$.
We compute $\sigma(ab)=abba$ and $\sigma(a)=ab$. There are no more return
words. Thus the return substitution is

$\sigma_{a}:A\mapsto ABC,\ B\mapsto AC,\ C\mapsto B$

with $\varphi_{a}:A\mapsto abb,\ B\mapsto ab,\ C\mapsto a$.

###  5.5 Deciding aperiodicity

Let $\sigma$ be a primitive substitution. Using return substitutions, we can
provide an algorithm to decide if $(X_{\sigma},S)$ is periodic. The fact that
aperiodicity is decidable is already well-know, but we give an algorithm for
completeness.

Assume that $\sigma(a)=a$, up to replacing $\sigma$ by a power of itself. We
define the $n$-th derivative of $\sigma$ for the letter $a$ by induction on
$n\in\mathbb{N}$: if $n=0$, $\partial_{a}^{n}\sigma=\sigma$; and if $n>0$,
$\partial_{a}^{n}=\partial\partial_{a}^{n-1}\sigma$, where the return
substitution is taken for the first letter, ensuring that the fixed point with
this first letter is mapped to the fixed point of the original substitution
starting with $a$.

######  Lemma 5.6.

$(X_{\sigma},S)$ is periodic if and only if there exists $n\in\mathbb{N}$ such
that the alphabet of $\partial_{a}^{n}\sigma$ has only one letter.

###### Proof.

Since $\sigma$ is primitive, the shift is periodic if and only if the fixed
point $x$ starting by letter $a$ is periodic. And a word is periodic if and
only if the sequence of its derivatives (i.e. rewriting the word as product of
its return words on first letter) becomes constant to the word with only one
letter. ∎

Such criterion can be algorithmically tested, since the sequence
$\partial_{a}^{n}\sigma$ is ultimately periodic thank to the following
proposition (see Proposition 7.6.7 in [DP22]), and since $\partial^{n}\sigma$
is of the form $\sigma_{p}$ for some prefix $p$ of a fixed point of $\sigma$.

######  Proposition 5.7.

Let $x$ be a fixed point of a primitive substitution $\sigma$. Then the set
$\\{\sigma_{w}\mid w\text{ prefix of }x\\}$ is finite.

######  Example 5.8.

Consider the Thue-Morse substitution

$\sigma:a\mapsto ab,\ b\mapsto ba.$

Its consecutive return substitutions on letter $a$ are

$\displaystyle\partial_{a}\sigma:$ $\displaystyle A\mapsto ABC,\ B\to AC,\
C\mapsto B$ $\displaystyle\partial_{a}^{2}\sigma:$ $\displaystyle 0\mapsto
01,\ 1\to 23,\ 2\mapsto 013,\ 3\mapsto 2$

Then, we have $\partial_{a}^{3}\sigma=\partial_{a}^{2}\sigma$. We conclude
that $(X_{\sigma},S)$ is aperiodic.

######  Example 5.9.

Consider the substitution $\sigma:a\mapsto ab\ b\mapsto c\ c\mapsto abc$. Its
derivative is $\partial_{a}\sigma:A\mapsto AA$ thus $(X_{\sigma},S)$ is
periodic.

######  Remark 5.10.

If $\sigma$ is primitive periodic, then its Perron eigenvalue is an integer.
Indeed, if $X_{\sigma}$ is of the form
$\bigcup_{k=0}^{\left|w\right|-1}S^{k}w^{\omega}$, then $\operatorname{ab}(w)$
is a Perron eigenvector of $M_{\sigma}$ since it is the limit of
$\left|w\right|\operatorname{ab}(\sigma^{n}(w_{0}))/\left|\sigma^{n}(w_{0})\right|$.

###  5.6 Semi-deciding recognizability

Given a substitution $\sigma$ and a morphism $\tau$, the fact that $\tau$ is
recognizable in $X_{\sigma}$ is semi-decidable thank to the following.

######  Proposition 5.11.

Let $\sigma$ be a primitive substitution and $\tau$ be a word morphism. Let
$X_{\sigma}$ be the bi-infinite shift associated with $\sigma$. The
substitution $\tau$ is recognizable in $X_{\sigma}$ if and only if

$\begin{split}\exists\epsilon>0,\ \forall x,y\in X_{\sigma},\ \forall 0\leq
p<\left|\tau(x_{0})\right|,\ \forall 0\leq q<\left|\tau(y_{0})\right|,\\\
d(S^{p}\tau(x),S^{q}\tau(y))\leq\epsilon\ \Longrightarrow\ p=q\text{ and
}x_{0}=y_{0}.\end{split}$

In other words, we can uniquely desubstitute if we know the bi-infinite word
in a large enough window. It permits to semi-decide the recognizability of
$\tau$ in $X_{\sigma}$ since for each $\epsilon>0$ there are only a finite
number of possibilities to test.

###### Proof.

Let $\epsilon>0$ be as in the last statement. Let us prove that $\tau$ is
recognizable in $X_{\sigma}$. Let $x$, $y\in X_{\sigma}$, $0\leq
p<\left|\tau(x_{0})\right|$ and $0\leq q<\left|\tau(y_{0})\right|$ be such
that $S^{p}\tau(x)=S^{q}\tau(y)$. We have
$d(S^{p}\tau(x),S^{q}\tau(y))=0<\epsilon$ so $p=q$ and $x_{0}=y_{0}$. Then, if
we shift $x$ and $y$, we have $d(\tau(Sx),\tau(Sy))=0$, thus $x_{1}=y_{1}$.
And we can also shift in the other direction: we have
$d(S^{-1}\tau(x),S^{-1}\tau(y))=0$, thus $x_{-1}=y_{-1}$. By induction, we get
that $x=y$. Thus $\tau$ is recognizable in $X_{\sigma}$.

Reciprocally, assume that such $\epsilon>0$ does not exists. For each
$\epsilon=\frac{1}{n}>0$ it gives $x^{(n)}$ and $y^{(n)}\in X_{\sigma}$,
$0\leq p_{n}<\left|\tau(x^{(n)}_{0})\right|$ and $0\leq
q_{n}<\left|\tau(y^{(n)}_{0})\right|$ such that
$d(S^{p_{n}}\tau(x^{(n)}),S^{q_{n}}\tau(y^{(n)}))<1/n$ and ($p_{n}\neq q_{n}$
or $x^{(n)}_{0}\neq y^{(n)}_{0}$). Then, by compacity there exists
subsequences $x^{(\phi(n))}$ and $y^{(\phi(n))}$ that converges and such that
$x_{0}^{(\phi(n))}$, $y_{0}^{(\phi(n))}$, $p_{\phi(n)}$ and $q_{\phi(n)}$ are
constant to $a$, $b$, $p$ and $q$ respectively, with either $a\neq b$ or
$p\neq q$. Let $x=\lim_{n\to\infty}x^{(\phi(n))}$ and
$y=\lim_{n\to\infty}y^{(\phi(n))}$. We have $x,y\in X_{\sigma}$ since
$X_{\sigma}$ is compact. Furthermore $S^{p}\tau(x)=S^{q}\tau(y)$ and ($p\neq
q$ or $x_{0}\neq y_{0}$) thus $\tau$ is not recognizable in $X_{\sigma}$. ∎

##  6 A criterion for weak mixing

We use our description of the set of eigenvalues to deduce a characterization
of the dimension of the set of eigenvalues. Moreover, we provide a necessary
and sufficient condition ensuring weak mixing, for primitive unimodular
substitutions without coboundary. First, we need to introduce some notations.

Let $\mathcal{B}$ be a set of algebraic integers. We denote
$\operatorname{Gal}(\mathcal{B})$ the Galois group of
$\mathbb{K}_{\mathcal{B}}:\mathbb{Q}$, where $\mathbb{K}_{\mathcal{B}}$ is the
splitting field of the product of minimal polynomials of elements of
$\mathcal{B}$.

######  Definition 6.1.

Let $\mathcal{B}$ be a set of algebraic integers. We define the graph of
$\mathcal{B}$ by

  * •

vertices that are elements of $\mathcal{B}$ and their conjugates,

  * •

edges between $\gamma$ and $\delta$ if and only if there exists
$f\in\operatorname{Gal}(\mathcal{B})$ such that $f(\gamma)\in\mathcal{B}$ and
$f(\delta)\in\mathcal{B}$.

We say that $\mathcal{B}$ is connected if its graph is connected.

Note that if $\beta$ has degree $d$ and $\operatorname{Gal}(\\{\beta\\})$
contains a $d$-cycle $f$, then $\\{\beta,f(\beta)\\}$ is connected. For
example, if the degree of $\beta$ is a prime number and $\gamma$ is a
conjugate of $\beta$, then $\\{\beta,\gamma\\}$ is connected.

Note that if $\mathcal{B}$ contains more than half of the conjugates of an
algebraic integer, then it is connected. For example, if $\beta$ is a Salem
number, its set of conjugates of modulus $\geq 1$ is connected.

Note that if $\mathcal{B}$ is connected, then any set of algebraic integers
containing $\mathcal{B}$ is connected.

######  Theorem 6.2 (Criterion for weak mixing).

Let $\sigma$ be a primitive aperiodic unimodular substitution with no non-
trivial coboundary. Let $\tau$ be a word morphism recognizable in
$X_{\sigma}$, and such that $\gcd((1...1)M_{\tau})=1$. Let $\mathcal{B}$ be
the set of eigenvalues of $M_{\sigma}$ of modulus greater than or equal to $1$
associated with at least one generalized eigenvector $v$ with
$(1...1)M_{\tau}v\neq 0$. Then, the subshift $(X_{\tau\sigma^{\omega}},S)$ is
weakly mixing if and only if $\mathcal{B}$ is connected.

This criterion is a consequence of the following theorem that characterizes
the dimension of the $\mathbb{Q}$-vector space spanned by eigenvalues of the
subshift.

######  Theorem 6.3.

Let $\sigma$ be a primitive aperiodic substitution, and let $\tau$ be a word
morphism recognizable in $X_{\sigma}$. Let $\pi_{0}\pi_{1}...\pi_{n}$ be the
decomposition of the minimal polynomial of $M_{\sigma}$ with $\pi_{0}$ the
product of all cyclotomic factors, and with $\pi_{i}$, $1\leq i\leq n$, the
remaining powers of irreducible factors in $\mathbb{Q}$. Let

$\mathcal{B}=\\{\beta\in\overline{\mathbb{Q}}\mid\exists i\in\\{0,...,n\\},\
(1...1)M_{\tau}G_{i}\neq\\{0\\},\ \pi_{i}(\beta)=0\text{ and
}\left|\beta\right|\geq 1\\},$

where $G_{0}=R(X_{\sigma})\cap\ker\pi_{0}(M_{\sigma})$, and $\forall i\geq 1$,
$G_{i}=\ker\pi_{i}(M_{\sigma})$.

Then, the dimension of the $\mathbb{Q}$-vector space spanned by the
eigenvalues of the subshift $(X_{\tau\sigma^{\omega}},S)$ is the number of
connected components of the graph of $\mathcal{B}$.

###### Proof of Theorem 6.2.

Assume that $\mathcal{B}$ is connected. Since $\sigma$ is unimodular, the set
of eigenvalues of the subshift is of the form
$(W\cap\mathbb{Z}^{\mathcal{A}})v_{0}$, where $v_{0}$ is the Perron
eigenvector normalized such that $(1...1)M_{\tau}v_{0}=1$. By Theorem 6.3 and
Lemma 6.5, the dimension of the $\mathbb{Q}$-vector space $W$ is $1$. Thanks
to the hypothesis $\gcd((1...1)M_{\tau})=1$, we deduce that
$W\cap\mathbb{Z}^{\mathcal{A}}=\mathbb{Z}(1...1)M_{\tau}$. Thus the set of
eigenvalues of the subshift is $\mathbb{Z}$.

Reciprocally, if the subshift is weakly mixing, then the $\mathbb{Q}$-vector
space spanned by its eigenvalues has dimension $1$, thus by Theorem 6.3,
$\mathcal{B}$ is connected. ∎

###  6.1 Proof of Theorem 6.3

This subsection is devoted to the proof of Theorem 6.3. We need the following
proposition, which is a particular case of Proposition 16.7 in [Mil15].

######  Proposition 6.4.

Let $F$ be a linear subspace of $\mathbb{K}^{\mathcal{A}}$ stable by the
Galois group $G=\operatorname{Gal}(\mathbb{K}:\mathbb{Q})$. Then,
$F=\mathbb{K}(F\cap\mathbb{Q}^{\mathcal{A}})$.

By Theorem 5.1, the $\mathbb{Q}$-vector space spanned by eigenvalues of
$(X_{\tau\sigma^{\omega}},S)$ is $Wv$, where $v$ is the Perron eigenvector of
sum $1$, and

$W=\mathbb{Q}^{\mathcal{A}}\cap(H\cap\mathbb{K}R(X_{\sigma})\cap\operatorname{span}_{\mathbb{K}}(V))^{\circ},$

where $H=((1...1)M_{\tau})^{\circ}$ and $\mathbb{K}$ is the splitting field of
the minimal polynomial of $M_{\sigma}$.

######  Lemma 6.5.

$\dim_{\mathbb{Q}}(Wv)+\dim_{\mathbb{Q}}(E_{0}+R^{\circ})=\dim_{\mathbb{Q}}(W)$,
where $E_{0}$ is the left generalized eigenspace of $M_{\sigma}$ for the
eigenvalue $0$ and $R=R(X_{\sigma})$.

###### Proof.

Let $\varphi:W\to Wv$ be the linear map defined by $\varphi(w)=wv$. This map
is onto. Let us show that $\ker(\varphi)=E_{0}+R^{\circ}$. Let
$w\in\ker(\varphi)$. Then, by definition of $W$ we have $w(v-v^{\prime})=0$ so
$wv^{\prime}=0$, for every generalized eigenvector $v^{\prime}\in R$
associated with an eigenvalue of modulus $\geq 1$ normalized such that
$(1...1)M_{\tau}v^{\prime}=1$. Then, since $w\in\mathbb{Q}^{\mathcal{A}}$, we
also have $wv^{\prime\prime}=0$ for every image $v^{\prime\prime}$ of
$v^{\prime}$ by a Galois element. Moreover, the Galois group act transitively
on conjugates and stabilize $R$. Thus, we have $w\in E_{0}+R^{\circ}$. The
other inclusion is obvious. ∎

We decompose the non-contracting space as $\operatorname{span}(V)=F_{u}\oplus
F_{1}\oplus...\oplus F_{n}$, where $F_{u}$ is the sum of every generalized
eigenspace for an eigenvalue root of unity, and $F_{1}$, …, $F_{n}$ are the
remaining generalized eigenspaces associated with eigenvalues of modulus $\geq
1$. By Lemma 2.8, $\mathbb{K}R$ contains $F_{1}\oplus...\oplus F_{n}$, thus

$\mathbb{K}R\cap\operatorname{span}(V)=(\mathbb{K}R\cap F_{u})\oplus
F_{1}\oplus...\oplus F_{n}.$

######  Lemma 6.6.

If $\mathbb{K}R\cap F_{u}\not\subset H$, then eigenvalues of
$(X_{\tau\sigma^{\omega}},S)$ are rational.

###### Proof.

Since the set $\mathbb{K}R\cap F_{u}$ is invariant by the Galois group
$\operatorname{Gal}(\mathbb{K}:\mathbb{Q})$, there exists a rational vector
$v\in R\cap F_{u}$ such that $(1...1)M_{\tau}v=1$. Then, the set of
eigenvalues of $X_{\tau\sigma^{\omega}}$ is included in $Wv=\mathbb{Q}$. ∎

If $\mathbb{K}R\cap F_{u}\not\subset H$, then $\mathcal{B}$ contains a root of
unity $\beta$. But it also contains every conjugate of $\beta$, so
$\mathcal{B}$ is connected, and we get the wanted equality.

In the following, we assume that $\mathbb{K}R\cap F_{u}\subset H$. Let
$\mathcal{B}^{\prime}$ be the set of conjugates of elements of $\mathcal{B}$,
including $\mathcal{B}$ (i.e. it is the set of vertices of the graph of
$\mathcal{B}$). We choose a set $(v_{\beta})_{\beta\in\mathcal{B}^{\prime}}$
of vectors such that for every $\beta\in\mathcal{B}^{\prime}$, $v_{\beta}$ is
a generalized eigenvector associated with $\beta$, with
$(1...1)M_{\tau}v_{\beta}=1$, and such that
$\forall\beta,\gamma\in\mathcal{B}^{\prime}$, $\varphi(v_{\beta})=v_{\gamma}$
where $\varphi:\mathbb{Q}(\beta)\to\mathbb{Q}(\gamma)$ is the morphism of
fields sending $\beta$ to $\gamma$.

Let
$D=\operatorname{span}_{\mathbb{K}}\\{v_{\beta}-v_{\gamma}\mid\beta,\gamma\in\mathcal{B}\\}$.
We have

$H\cap\mathbb{K}R(X_{\sigma})\cap\operatorname{span}_{\mathbb{K}}(V)=(\mathbb{K}R(X_{\sigma})\cap
F_{u})\oplus(F_{1}\cap H)\oplus...\oplus(F_{n}\cap H)\oplus D$

thanks to the following.

######  Lemma 6.7.

Let $\varphi:E\to\mathbb{K}$ be a linear form and let $(A_{i})_{i\in I}$ be a
finite family of subspaces of $E$. Then,

$\ker(\varphi)\cap\bigoplus_{i\in I}A_{i}=\left(\bigoplus_{i\in
I}\ker(\varphi)\cap
A_{i}\right)\oplus\operatorname{span}_{\mathbb{K}}\\{v_{i}-v_{j}\mid i,j\in
I\\},$

where for all $i\in I$, $v_{i}\in A_{i}$ is such that $\varphi(v_{i})=1$ if
$\varphi(A_{i})\neq\\{0\\}$, and $v_{i}=0$ otherwise.

###### Proof.

For each $i\in I$, let $B_{i}$ be a basis of $\ker(\varphi)\cap A_{i}$. Let
$J=\\{i\in I\mid\varphi(A_{i})\neq\\{0\\}\\}$. If $J=\emptyset$, then the
result is obvious. Let $k\in J$. Since $\bigcup_{i\in I}B_{i}\cup\bigcup_{i\in
J}\\{v_{i}\\}$ is a basis of $\bigoplus_{i\in I}A_{i}$, the family
$\\{v_{k}\\}\cup\bigcup_{i\in I}B_{i}\cup\bigcup_{i\in
J\backslash\\{k\\}}\\{v_{i}-v_{k}\\}$ is also a basis of $\bigoplus_{i\in
I}A_{i}$. Thus, $\bigcup_{i\in I}B_{i}\cup\bigcup_{i\in
J\backslash\\{k\\}}\\{v_{i}-v_{k}\\}$ is a basis of
$\ker(\varphi)\cap\bigoplus_{i\in I}A_{i}$ and $\bigcup_{i\in
J\backslash\\{k\\}}\\{v_{i}-v_{k}\\}$ is a basis of
$\operatorname{span}_{\mathbb{K}}\\{v_{i}-v_{j}\mid i,j\in I\\}$. ∎

Let $G=\operatorname{Gal}(\mathbb{K}:\mathbb{Q})$.

######  Lemma 6.8.

Let $E$ be a subspace of $\mathbb{K}^{n}$. Then,

$\dim_{\mathbb{Q}}(\mathbb{Q}^{n}\cap
E^{\circ})=n-\dim_{\mathbb{K}}(GE)=n-\dim_{\mathbb{Q}}(\mathbb{Q}^{n}\cap
GE).$

###### Proof.

It is a consequence of Proposition 6.4. ∎

Hence, to find the dimension of $W$, we have to find the dimension of $G(H\cap
R(X_{\sigma})\cap\operatorname{span}_{\mathbb{K}}(V))$. For every
$i\in\\{1,...,n\\}$ and every $g\in G$, $g(E_{i}\cap H)=g(E_{i})\cap H$ since
$H$ is stable by the Galois group $G$, thus

$G(H\cap\mathbb{K}R(X_{\sigma})\cap\operatorname{span}_{\mathbb{K}}(V))=(\mathbb{K}R(X_{\sigma})\cap
F_{u})\oplus\left(\sum_{g\in G}\sum_{i=1}^{n}H\cap g(F_{i})\right)\oplus GD.$

Note that each $\mathbb{K}G_{i}$ is equal to some $\sum_{g\in G}g(F_{j})$, and
that
$(1...1)M_{\tau}G_{i}=\\{0\\}\Longleftrightarrow(1...1)M_{\tau}F_{j}=\\{0\\}$.
We can decompose the sum as a direct sum

$\sum_{g\in G}\sum_{i=1}^{n}H\cap
gF_{i}=\left(\bigoplus_{\beta\in\mathcal{B}^{\prime}}H\cap
F_{\beta}\right)\oplus\bigoplus_{\beta\in\mathcal{C}}F_{\beta}$

whose dimension is
$\left|\mathcal{A}\right|-\left|\mathcal{B}^{\prime}\right|-\dim(F_{u})-\dim(F_{0})$,
where $\mathcal{C}$ is the set of eigenvalues of $M_{\sigma}$ not root of
unity, not zero and not in $\mathcal{B}^{\prime}$ and $F_{\beta}$ is the
generalized eigenspace associated with $\beta$. Indeed, for every
$\beta\in\mathcal{B}^{\prime}$, $\dim(H\cap F_{\beta})=\dim(F_{\beta})-1$.

######  Lemma 6.9.

$\dim(GD)=\left|\mathcal{B}^{\prime}\right|-k$ where $k$ is the number of
connected components of the graph of $\mathcal{B}$.

###### Proof.

Let $c$ be a connected component of the graph of $\mathcal{B}$. Then, the
dimension of
$D_{c}=\operatorname{span}\\{v_{\beta}-v_{\gamma}\mid\beta\text{---}\gamma\text{
edge of }c\\}$ is $\left|c\right|-1$. Indeed, $D_{c}$ contains every
difference $v_{\beta}-v_{\gamma}$ for $\beta,\gamma\in c$, and if we choose
any $\beta\in c$ then $(v_{\beta}-v_{\gamma})_{\gamma\in
c\backslash\\{\beta\\}}$ is a basis of $D_{c}$. Moreover
$GD=\operatorname{span}\\{v_{\beta}-v_{\gamma}\mid\beta\text{---}\gamma\text{
edge}\\}=\bigoplus_{c}D_{c}$. ∎

We obtain

$\displaystyle\dim W$ $\displaystyle=$
$\displaystyle\left|\mathcal{A}\right|-\dim(\mathbb{K}R\cap
F_{u})-(\left|\mathcal{A}\right|-\left|\mathcal{B}^{\prime}\right|-\dim(F_{u})-\dim(F_{0}))-(\left|\mathcal{B}^{\prime}\right|-k)$
$\displaystyle=$ $\displaystyle k+\dim(F_{u})+\dim(F_{0})-\dim(\mathbb{K}R\cap
F_{u})$ $\displaystyle=$ $\displaystyle k+\dim(E_{0}+R^{\circ}),$

since
$E_{0}+R^{\circ}=\left(\mathbb{K}R\cap(F_{u}\oplus\bigoplus_{\beta\in\mathcal{C}}F_{\beta})\right)^{\circ}=\left((\mathbb{K}R\cap
F_{u})\oplus\bigoplus_{\beta\in\mathcal{C}}F_{\beta}\right)^{\circ}.$ Thus, by
Lemma 6.5, the dimension of the $\mathbb{Q}$-vector space spanned by
eigenvalues of $(X_{\tau\sigma^{\omega}},S)$ is $\dim(Wv)=k$. It finishes the
proof of Theorem 6.3.

##  7 Examples

In this section, we give examples with non-trivial coboundaries and with
explicit computation of eigenvalues.

###  7.1 Constructing examples with non-trivial coboundary

We provide a recipe for constructing examples with non-trivial coboundaries:

Begin by selecting any directed graph where edges are labeled with letters,
ensuring that each letter appears only once. Next, choose any map $f:V\to V$,
where $V$ is the set of vertices. Construct a substitution $\sigma$ as follow:
For each letter $a\in\mathcal{A}$, we choose $\sigma(a)$ to be labels of a
path from $f(s)$ to $f(e)$, where $s\xrightarrow{a}e$ is the edge labeled by
$a$ in the graph.

For example, consider the graph

$\cdot$$\cdot$abc

We can construct the following substitutions preserving this graph:

$\left\\{\begin{array}[]{l}a\mapsto bc\\\ b\mapsto ab\\\ c\mapsto
caa\end{array},\begin{array}[]{l}a\mapsto caab\\\ b\mapsto c\\\ c\mapsto
ab\end{array},\begin{array}[]{l}a\mapsto bc\\\ b\mapsto aa\\\ c\mapsto
bca\end{array}\right\\}.$

Then, the coboundary $\begin{pmatrix}0&1&-1\end{pmatrix}$ associated with the
graph is an eigenvector of incidence matrices. In the first case, it is
associated with the eigenvalue $1$ because it preserves each vertex. In the
second case, the eigenvalue is $-1$ because it exchanges vertices. In the
third case, the eigenvalue is $0$ since both vertices are mapped to the same
vertex. Any directive sequence of substitutions constructed using this recipe
for a given graph yields a subshift that have coboundaries determined by the
graph.

###  7.2 Examples of computation of eigenvalues

We give examples of computation of eigenvalues of morphic subshifts using the
algorithm of Subsection 5.2.

######  Example 7.1 (Thue-Morse).

Let $\sigma:a\mapsto ab,\ b\mapsto ba$. Its incidence matrix
$\begin{pmatrix}1&1\\\ 1&1\end{pmatrix}$ has only one eigenvalue of modulus
$\geq 1$ which is $2$ associated with the eigenvector
$v=\begin{pmatrix}1/2&1/2\end{pmatrix}^{t}$. There is no non-trivial
coboundary, thus following the algorithm, $CV$ is a $1\times 1$ invertible
matrix, so $W=\mathbb{Q}^{2}$. Moreover,
$\Delta_{M_{\sigma}}v=\mathbb{Z}\left[\frac{1}{2}\right]$, thus the set of
eigenvalues is $\mathbb{Z}\left[\frac{1}{2}\right]$. The set
$\mathcal{B}=\\{2\\}$ is connected.

######  Example 7.2 (Regular paper folding).

Let $\sigma:a\mapsto ab,\ b\mapsto cb,\ c\mapsto ad,\ d\mapsto cd$ and
$\tau:a\mapsto 11,\ b\mapsto 01,\ c\mapsto 10,\ d\mapsto 00$. Thanks to the
algorithm of Subsection 5.6, we can check that $\tau$ is recognizable in
$X_{\sigma}$ and we check also that $\sigma$ is not periodic. The set of
coboundaries
$R^{\circ}=\operatorname{span}\\{\begin{pmatrix}1&-1&1&-1\end{pmatrix}\\}$ of
$X_{\sigma}$ is included in the generalized eigenspace $E_{0}$ for the
eigenvalue $0$, thus we take
$C=\begin{pmatrix}1&1&1&1\end{pmatrix}M_{\tau}=\begin{pmatrix}2&2&2&2\end{pmatrix}$.
We have $V=\begin{pmatrix}1&0\\\ 1&1\\\ 1&0\\\ 1&-1\end{pmatrix}$ so
$CV=\begin{pmatrix}8&0\end{pmatrix}$. Hence, $W$ is the left-kernel of
$\begin{pmatrix}0&1&0&-1\end{pmatrix}^{t}$. Since $C$ is a left-eigenvector of
$M_{\sigma}$ for the eigenvalue $2$, the set of eigenvalues is
$\mathbb{Z}\left[\frac{1}{2}\right](W\cap\mathbb{Z}^{4})v$ where
$v=\frac{1}{4}\begin{pmatrix}1&1&1&1\end{pmatrix}^{t}$. It gives the set
$\mathbb{Z}\left[\frac{1}{2}\right]$. $\mathcal{B}=\\{1,2\\}$ is connected.

######  Example 7.3 (Constant-length with coboundary).

Let $\sigma:a\mapsto aca\ b\mapsto acb\ c\mapsto cbc$. Its coboundary space is
$R^{\circ}=\operatorname{span}\\{\begin{pmatrix}1&1&-1\end{pmatrix}\\}$. The
incidence matrix

$M=\left(\begin{array}[]{rrr}2&1&0\\\ 0&1&1\\\ 1&1&2\end{array}\right)$

has eigenvalues $2$ and $1$ and is not diagonalizable. Then, we have

$C=\begin{pmatrix}1&1&1\\\ 1&1&-1\end{pmatrix}\quad\text{, }\quad
V=\left(\begin{array}[]{rrr}1&0&1\\\ 0&1&1\\\
-1&-1&2\end{array}\right)\quad\text{ and }\quad CV=\begin{pmatrix}0&0&4\\\
2&2&0\end{pmatrix}.$

We found that $W$ is the left-kernel of
$\begin{pmatrix}1&-1&0\end{pmatrix}^{t}$, that is the $\mathbb{Q}$-vector
space spanned by
$\\{\begin{pmatrix}1&1&0\end{pmatrix},\begin{pmatrix}0&0&1\end{pmatrix}\\}$.
Let $v=\begin{pmatrix}1/4&1/4&1/2\end{pmatrix}$ be the Perron eigenvector of
sum $1$. Since $\sigma$ has constant-length $3$, the set of eigenvalues of
$(X_{\sigma},S)$ is
$\mathbb{Z}\left[\frac{1}{3}\right](W\cap\mathbb{Z}^{3})v=\frac{1}{2}\mathbb{Z}\left[\frac{1}{3}\right]$.

######  Example 7.4 (Weakly mixing subshift with coboundary).

Let $\sigma:a\mapsto d\ b\mapsto ca\ c\mapsto bd\ d\mapsto abc$. Its matrix is

$\left(\begin{array}[]{rrrr}0&1&0&1\\\ 0&0&1&1\\\ 0&1&0&1\\\
1&0&1&0\end{array}\right).$

The coboundary space is
$R^{\circ}=\operatorname{span}\\{\begin{pmatrix}0&1&-1&0\end{pmatrix}\\}$.
Following the algorithm let $C=\begin{pmatrix}1&1&1&1\\\
0&1&-1&0\end{pmatrix}$. Then, the set of eigenvalues of modulus $\geq 1$ is
$\\{-1,2\\}$. The generalized eigenspace for the eigenvalue $-1$ has dimension
$2$, the matrix is not diagonalizable. The generalized vector
$v=\begin{pmatrix}1&1&1&-2\end{pmatrix}^{t}$ for the eigenvalue $-1$ is
annihilated by the coboundary and is such that
$\begin{pmatrix}1&1&1&1\end{pmatrix}v=1$. Since $\Delta_{M}v=\mathbb{Z}$, the
set of eigenvalues if $\mathbb{Z}$. We conclude that $(X_{\sigma},S)$ is
weakly mixing.

######  Example 7.5 (Unimodular substitution with coboundary).

Let $\sigma:a\mapsto aba\ b\mapsto cb\ c\mapsto cba$. Its coboundary space is
$R^{\circ}=\operatorname{span}\\{\begin{pmatrix}1&-1&0\end{pmatrix}\\}$. The
characteristic polynomial of the incidence matrix is $(x-1)(x^{2}-3x+1)$. We
have

$C=\begin{pmatrix}1&1&1\\\ 1&-1&0\end{pmatrix}\quad,\quad
V=\begin{pmatrix}1&1\\\ 1&0\\\ 1-\varphi&-1\end{pmatrix}\quad\text{ and }\quad
CV=\begin{pmatrix}1+\varphi&0\\\ 0&1\end{pmatrix}$

The matrix $CV$ is invertible thus $W=\mathbb{Q}^{3}$. The matrix $M_{\sigma}$
is unimodular thus $\Delta_{M}=\mathbb{Z}^{3}$. The normalized Perron
eigenvector is
$v=\begin{pmatrix}2-\varphi&2-\varphi&2\varphi-3\end{pmatrix}^{t}$ where
$\varphi$ is the golden ratio. Thus the set of eigenvalues is
$\mathbb{Z}\left[\varphi\right]$

######  Example 7.6 (Reducible substitution with non-trivial graph of
$\mathcal{B}$).

Let $\sigma:1\mapsto 16,2\mapsto 122,3\mapsto 12,4\mapsto 3,5\mapsto
124,6\mapsto 15$. The characteristic polynomial of the incidence matrix is
$(x^{3}-3x^{2}+2x-1)(x^{3}-x-1)$. The substitution has no non-trivial
coboundary and $\mathcal{B}=\\{\rho,\rho+1\\}$ where $\rho$ is the plastic
ratio such that $\rho^{3}=\rho+1$. The graph of $\mathcal{B}$ has $3$
connected components of size $2$. The set of eigenvalues is
$\mathbb{Z}\\{1,3\rho,3\rho^{2}\\}$.

######  Example 7.7 (Irreducible substitution with non-trivial graph of
$\mathcal{B}$).

This example comes from [FMN96] (see also [Mer23]). The substitution
$\sigma:a\mapsto abdd,b\mapsto bc,c\mapsto d,d\mapsto a$ is irreducible,
unimodular and has no non-trivial coboundary. The set $\mathcal{B}$ is
$\\{\beta,1-\beta\\}$ where $\beta$ is the greatest root of
$x^{4}-2x^{3}-x^{2}+2x-1$. The Galois group $\operatorname{Gal}(\mathcal{B})$
has order $8$, and the graph of $\mathcal{B}$ has two connected components.
The set of eigenvalues is $\mathbb{Z}[\sqrt{2}]$.

###  7.3 Examples coming from geometry

In this subsection, we give examples of subshift that naturally arise from
interval exchange transformations, or interval translation maps, or other
geometrical problems.

######  Example 7.8 ($\mathcal{S}$-adic with coboundary coming from a problem
of Novikov).

The following substitutions

$\left\\{\begin{array}[]{l}0\mapsto 0\\\ 1\mapsto 1\\\ 2\mapsto 361\\\
3\mapsto 3\\\ 4\mapsto 4\\\ 5\mapsto 5\\\ 6\mapsto 527\\\ 7\mapsto
7\end{array},\begin{array}[]{l}0\mapsto 527\\\ 1\mapsto 520\\\ 2\mapsto 0\\\
3\mapsto 1\\\ 4\mapsto 361\\\ 5\mapsto 461\\\ 6\mapsto 4\\\ 7\mapsto
5\end{array},\begin{array}[]{l}0\mapsto 361\\\ 1\mapsto 3\\\ 2\mapsto 4\\\
3\mapsto 427\\\ 4\mapsto 527\\\ 5\mapsto 7\\\ 6\mapsto 0\\\ 7\mapsto
360\end{array},\begin{array}[]{l}0\mapsto 4\\\ 1\mapsto 427\\\ 2\mapsto 527\\\
3\mapsto 520\\\ 4\mapsto 0\\\ 5\mapsto 360\\\ 6\mapsto 361\\\ 7\mapsto
461\end{array},\begin{array}[]{l}0\mapsto 0\\\ 1\mapsto 052\\\ 2\mapsto 2\\\
3\mapsto 3\\\ 4\mapsto 4\\\ 5\mapsto 614\\\ 6\mapsto 6\\\ 7\mapsto
7\end{array},\begin{array}[]{l}0\mapsto 0\\\ 1\mapsto 1\\\ 2\mapsto 2\\\
3\mapsto 274\\\ 4\mapsto 4\\\ 5\mapsto 5\\\ 6\mapsto 6\\\ 7\mapsto
036\end{array}\right\\}$

preserves the graph

$\cdot$$\cdot$$0,4$$1,7$$2,6$$3,5$

thus $\left(1,\,0,\,-1,\,0,\,1,\,0,\,-1,\,0\right)$ is a coboundary of the
subshift for any primitive directive sequence. Our algorithm allows us to
compute eigenvalues of the subshift for every primitive pre-periodic directive
sequence. For example, the subshift of the second substitution has eigenvalues
$\mathbb{Z}\left\\{\frac{1}{2}\beta^{2}+\frac{1}{2},\
\frac{1}{2}\beta^{2}+\frac{1}{2}\beta,\ \beta^{2}\right\\}$ where $\beta$ is
root of $x^{3}-2x^{2}-1$. These substitutions come from a renormalization of a
dynamical system on a non-orientable surface. The coboundary comes from a
symmetry of the surface.

######  Example 7.9 (Weakly mixing Interval Translation Maps).

In [BR23], it is shown that every primitive pre-periodic directive sequence
with substitutions $1\mapsto 2,2\mapsto 31^{k},3\mapsto 31^{k-1}$, $k\geq 1$,
gives a weakly mixing subshift. But their proof relies on awful calculations.
Thanks to our criterion, we can give a different proof without calculation.
There are no non-trivial coboundaries since any product of two of these
substitutions is left-proper. They prove that the incidence matrix of the
periodic part has two eigenvalues of modulus $\geq 1$ (see Proposition 3.1 in
[BR23]). Moreover, it is unimodular, so it is irreducible, and
$\left|\mathcal{B}\right|=2>3/2$, so $\mathcal{B}$ is connected. By Theorem
6.2, the subshift is weakly mixing.

######  Example 7.10 (Arnoux-Yoccoz IET).

The Arnoux-Yoccoz interval exchange transformation is defined by permutation
$(2547631)$ and lengths

$\left(-\frac{1}{2}\beta+\frac{1}{2},\ \beta-\frac{1}{2},\ \frac{1}{2}\beta,\
\frac{1}{2}\beta^{2},\ \frac{1}{2}\beta^{2},\
-\frac{1}{2}\beta^{2}-\frac{1}{2}\beta+\frac{1}{2},\
-\frac{1}{2}\beta^{2}-\frac{1}{2}\beta+\frac{1}{2}\right),$

where $\beta^{3}+\beta^{2}+\beta=1$. See [JHLV07] for more details.

This IET is pre-periodic for the Rauzy-Veech induction with pre-period
$110110100101$ and period $101011010101001110000$. It corresponds respectively
to substitutions $\tau:1\mapsto 15,2\mapsto 2,3\mapsto 1734335,4\mapsto
163434,5\mapsto 1635,6\mapsto 1634335,7\mapsto 1734$ and $\sigma:1\mapsto
15172,2\mapsto 172,3\mapsto 1734365172,4\mapsto 15643472,5\mapsto
1565172,6\mapsto 1564365172,7\mapsto 173472$. Thank to our algorithm, we found
that the set of eigenvalues of the IET is $\mathbb{Z}[\beta]$. This was
expected since this IET is measurably conjugate to a translation on the torus
$\mathbb{T}^{2}$. There is no non-trivial coboundary and the graph of
$\mathcal{B}=\\{\beta\\}$ has $3$ vertices and no edge.

Note that if we consider the shift of $\sigma$, without the pre-period, then
$\mathcal{B}$ contains $1$ so it is connected, thus by Theorem 6.2, the shift
of $\sigma$ is weakly mixing.

######  Example 7.11 (Family of weakly mixing IET).

This example comes from 4.3.1 in [DS16]. Consider the family of interval
exchange transformation be defined by permutation $(7654321)$ and loop
$10101(0^{k-1})10011100001111100000(1^{k-1})0$ for the Rauzy-Veech induction,
with $k\geq 2$. The associated substitution

$1\mapsto 1617,2\mapsto 16252617,3\mapsto 16253(4^{k-1})352617,4\mapsto
16253(4^{k})352617,$ $5\mapsto
1625352617,6\mapsto(1626)^{k}17,7\mapsto(1626)^{k-1}17$

is unimodular, and it has no non-trivial coboundary since it is left-proper.
We easily check that
$(\begin{array}[]{ccccccc}1&-1&1&-1&1&-1&1\end{array})^{t}$ is an eigenvector
of the incidence matrix for the eigenvalue $1$. Hence, $\mathcal{B}$ contains
$1$ so it is connected. By Theorem 6.2, the associated subshift is weakly
mixing.

Note that every pre-periodic directive sequence with these substitutions also
give a weakly mixing subshift for the same reason.

More examples of computations of eigenvalues of subshifts can be found here:
https://www.i2m.univ-amu.fr/perso/paul.mercat/SubshiftsEigenvalues.pdf It uses
Sage math and the package eigenmorphic. See end of Subsection 5.2 for more
details.

##  8 Acknowledgement

I thank Pascal Hubert for his careful reading of this article and for
interesting discussions that helped me to found Theorem 6.2 and Theorem 6.3. I
also thank Chanxi Wu for his collaboration to the recognizability result (see
Subsection 5.6).

## References

  * [Ada04] Boris Adamczewski.  Symbolic discrepancy and self-similar dynamics.  Annales de l’Institut Fourier, 54(7):2201–2234, 2004.
  * [BBY22] Valérie Berthé, Paulina Cecchi Bernales, and Reem Yassawi.  Coboundaries and eigenvalues of finitary s-adic systems, 2022.
  * [BDM05] XAVIER BRESSAUD, FABIEN DURAND, and ALEJANDRO MAASS.  Necessary and sufficient conditions to be an eigenvalue for linearly recurrent dynamical cantor systems.  Journal of the London Mathematical Society, 72(3):799–816, 2005\.
  * [BR23] Henk Bruin and Silvia Radinger.  Interval translation maps with weakly mixing attractors, 2023.
  * [BSTY19] Valérie Berthé, Wolfgang Steiner, Jörg M. Thuswaldner, and Reem Yassawi.  Recognizability for sequences of morphisms.  Ergodic Theory and Dynamical Systems, 39(11):2896–2931, 2019.
  * [CDHM03] Maria Isabel Cortez, Fabien Durand, Bernard Host, and Alejandro Maass.  Continuous and measurable eigenfunctions of linearly recurrent dynamical cantor systems.  Journal of the London Mathematical Society, 67(3):790–804, 2003\.
  * [CFM08] Julien Cassaigne, Sébastien Ferenczi, and Ali Messaoudi.  Weak mixing and eigenvalues for Arnoux-Rauzy sequences.  Annales de l’Institut Fourier, 58(6):1983–2005, 2008.
  * [CS01] Vincent Canterini and Anne Siegel.  Automate des préfixes-suffixes associé à une substitution primitive.  Journal de théorie des nombres de Bordeaux, 13(2):353–369, 2001\.
  * [DP20] Fabien Durand and Samuel Petite.  Conjugacy of unimodular pisot substitutions subshifts to domain exchanges, 2020.
  * [DP22] Fabien Durand and Dominique Perrin.  Dimension Groups and Dynamical Systems: Substitutions, Bratteli Diagrams and Cantor Systems.  Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2022.
  * [DS16] Hieu Trung Do and Thomas A. Schmidt.  New infinite families of pseudo-anosov maps with vanishing sah-arnoux-fathi invariant.  Journal of Modern Dynamics, 10(2):541–561, 2016.
  * [Dur98] Fabien Durand.  A characterization of substitutive sequences using return words.  Discrete Mathematics, 179(1):89–101, 1998.
  * [Dur00] Fabien Durand.  Linearly recurrent subshifts have a finite number of non-periodic subshift factors.  Ergodic Theory and Dynamical Systems, 20(4):1061–1078, 2000.
  * [Dur03] Fabien Durand.  Corrigendum and addendum to ‘linearly recurrent subshifts have a finite number of non-periodic factors’.  Ergodic Theory and Dynamical Systems, 23(2):663–669, 2003.
  * [FD19] Alejandro Maass Fabien Durand, Alexander Frank.  Eigenvalues of minimal cantor systems.  Eur. Math. Soc, 21(3):727–775, 2019.
  * [FMN96] Sébastien Ferenczi, Christian Mauduit, and Arnaldo Nogueira.  Substitution dynamical systems : algebraic characterization of eigenvalues.  Annales scientifiques de l’École Normale Supérieure, Ser. 4, 29(4):519–533, 1996.
  * [Hos86] B. Host.  Valeurs propres des systèmes dynamiques définis par des substitutions de longueur variable.  Ergod. Th. & Dynam. Syst., 1986.
  * [JHLV07] G. Poggiaspalla J. H. Lowenstein and F. Vivaldi.  Interval exchange transformations over algebraic number fields: the cubic arnoux–yoccoz model.  Dynamical Systems, 22(1):73–106, 2007.
  * [MA20] Paul Mercat and Shigeki Akiyama.  Yet Another Characterization of the Pisot Substitution Conjecture, pages 397–448.  Springer International Publishing, Cham, 2020.
  * [Mer23] Paul Mercat.  Geometrical representation of subshifts for primitive substitutions.  Ergodic Theory and Dynamical Systems, pages 1–28, 2023.
  * [Mil15] J.S. Milne.  Algebraic geometry, 2015.
  * [Mos96] Brigitte Mossé.  Reconnaissabilité des substitutions et complexité des suites automatiques.  Bulletin de la Société Mathématique de France, 124(2):329–346, 1996.