\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\DeclareMathOperator{\card}{Card}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
The Constant of Recognizability is  \\
\vskip .1in
Computable for Primitive Morphisms
}
\vskip 1cm
\large
Fabien Durand \\
Laboratoire Ami\'enois de Math\'ematiques Fondamentales et Appliqu\'ees CNRS-UMR 7352 \\
Universit\'{e} de Picardie Jules Verne \\
33 rue Saint Leu \\
80000 Amiens\\
France\\
\href{mailto:fabien.durand@u-picardie.fr}{\tt fabien.durand@u-picardie.fr} \\
\ \\
Julien Leroy\footnote{J. Leroy is an FNRS post-doctoral fellow.} \\
Institut de math\'ematique \\
Universit\'e de Li\`ege \\
All\'ee de la d\'ecouverte 12 (B37) \\
4000 Li\`ege \\
Belgium \\
\href{J.Leroy@ulg.ac.be}{\tt J.Leroy@ulg.ac.be}\\
\end{center}

\vskip .2 in


\def\R{{\mathbb R}}
\def\Z{{\mathbb Z}}
\def\H{{\mathbb H}}
\def\C{{\mathbb C}}
\def\N{{\mathbb N}}
\def\G{{\mathbb G}}
\def\S{{\mathbb S}}
\def\F{{\mathbb F}}
\def\K{{\mathbb K}}
\def\QQ{{\mathbb Q}}
\def\cA{{\mathcal A}}
\def\cB{{\mathcal B}}
\def\cC{{\mathcal C}}
\def\cD{{\mathcal D}}
\def\cF{{\mathcal F}}
\def\cG{{\mathcal G}}
\def\cH{{\mathcal H}}
\def\cK{{\mathcal K}}
\def\cL{{\mathcal L}}
\def\cM{{\mathcal M}}
\def\cN{{\mathcal N}}
\def\cP{{\mathcal P}}
\def\cR{{\mathcal R}}
\def\cS{{\mathcal S}}
\def\cT{{\mathcal T}}

\def\bw{\mathbf{w}}
\def\bx{\mathbf{x}}
\def\by{\mathbf{y}}





\vskip .2 in

\begin{abstract}
Moss\'e proved that primitive morphisms are recognizable. In this paper we give a computable upper bound for the constant of recognizability of such a morphism.
This bound can be expressed using only the cardinality of the alphabet and the length of the longest image of a letter under the morphism.
\end{abstract}


\section{Introduction}

Infinite words, i.e., infinite sequences of symbols from a finite set, usually called the alphabet, 
form a classical object of study. 
They have an important power of representation: they provide a natural way to code elements of an
infinite set using finitely many symbols, e.g., the coding of an orbit in a discrete dynamical system or 
the characteristic sequence of a set of integers. 
A rich family of infinite words, with a simple algorithmic description, 
consists of the words obtained by iterating a morphism $\sigma:A^* \to A^*$ \cite{Choffrut&Karhumaki:1997}, where $A^*$ is the free monoid generated by the finite alphabet $A$.

If $\sigma$ is {\em prolongable} on some letter $a \in A$, that is, if $\sigma(a) = au$ for some non-empty word $u$ and $\lim_{n \to +\infty} |\sigma^n(a)| = +\infty$, then $\sigma^n(a)$ converges to an infinite word $x = \sigma^{\omega}(a) \in A^\mathbb{N}$ that is a fixed point of $\sigma$.
Two-sided fixed points are similarly defined as infinite words of the form $\sigma^{\omega}(a \cdot b) \in A^\Z$, where $\sigma(a) = ua$ and $\sigma(b) = bv$ with $u,v \in A^+$ and $\lim_{n \to +\infty} |\sigma^n(a)| = \lim_{n \to +\infty} |\sigma^n(b)| = +\infty$.
Such a fixed point is said to be {\em admissible} if $ab$ occurs in $\sigma^n(c)$ for some $n \in \N$ and some $c \in A$.
When the morphism is {\em primitive}, i.e., there exists $k \in \mathbb{N}$ such that $b$ occurs in $\sigma^k(c)$ for all $b,c\in A$, then $x$ is {\em uniformly recurrent}: each finite word $u$ that occurs in $x$ occurs infinitely many times in $x$ and the gaps between
two consecutive occurrences of $u$ in $x$ are bounded \cite{Queffelec:2010}.
The converse almost holds: if $x=\sigma^{\omega}(a)$ is uniformly recurrent, then there exist a primitive morphism $\varphi:B^* \to B^*$, a letter $b \in B$ and a morphism $\psi:B^* \to A^*$ such that $x = \psi(\varphi^{\omega}(b))$ \cite{Durand:1998}.
We let $\cL(x)$ denote the set of {\em factors} of $x$, i.e., $\cL(x) = \{u \in A^* \mid \exists p \in A^*, w \in A^\N: x = puw\}$ (with an analogous definition for two-sided fixed points). 
We also let $p_x:\N \to \N$ denote the {\em complexity function} of $x$ defined by $p_x(n) = \card \cL_n(x)$ where $\cL_n(x) = \cL(x) \cap A^n$.
A primitive morphism $\sigma$ is {\em aperiodic} if its fixed points are not periodic, i.e., are not of the form $u^\omega = uuu\cdots$.

{\em Recognizability} is a central notion when dealing with fixed points of morphisms.
It roughly means that any sufficiently long finite word that occurs in $\sigma^{\omega}(a)$ has a unique pre-image under $\sigma$, except for a prefix and a suffix of bounded length.
Recognizability of a morphism is linked to the existence of long powers $u^k$ in $\cL(x)$ \cite{Mignosi&Seebold:1993}.
An infinite word $x \in A^\Z$ is said to be {\em $k$-power-free} if there is no non-empty word $u$ such that $u^k$ belongs to $\cL(x)$.
We refer, for example, to \cite{Canterini&Siegel:2001,Durand&Host&Skau:1999,Pytheas,Holton&Zamboni:1999}.
A fundamental result concerning recognizability is due to Moss\'e, who proved that aperiodic primitive morphisms are recognizable~\cite{Mosse:1992,Mosse:1996}.
In this paper, we present a detailed proof of this result. 
This allows us to give a bound on the constant of recognizability.


\section{Recognizability}

Recognizability of a morphism deals with uniqueness of pre-images of words.
More precisely, given a morphism $\sigma$, an admissible fixed point $x$ of $\sigma$ and a sufficiently long word $w \in \cL(x)$, we would like to find some word $u \in \cL(x)$ such that $w$ appears in $\sigma(u)$ and such that any other word $u' \in \cL(x)$ satisfying the same property has a large part in common with $u$.
This large common part is the pre-image that the notion of recognizability is concerned with.

To find such a pre-image, it suffices to consider the pre-images of the letters. 
As a letter $a$ can appear in several images $\sigma(b)$ and at different positions in $\sigma(b)$, we need to consider it in some {\em context} of length $\ell$, i.e., to consider a word $uav \in \cL(x)$ with $|u|= |v| = \ell$.
We would like that the length of the context ensures the uniqueness of $b$ and of the position $i \in \{0,1,\dots,|\sigma(b)|-1\}$ such that $(\sigma(b))_i = a$. 
This length $\ell$ will be defined as the constant of recognizability in Definition~\ref{def:rec}.
 
Let us consider an example with the morphism $\tau$ defined by $\tau(0) =\tau(1) = 021$ and $\tau(2)=0$.
The letter $0$ appears at the first position in the image of $0$, $1$ and $2$. 
The contexts of length $4$ of $0$ are the words of length 9 that occur in $x=\tau^{\omega}(1\cdot 0)$ and that have 0 for central letter, i.e.,
\[
\begin{array}{c}
	c_1 = 0021\, 0\, 2100;	\\
	c_2 = 0021\, 0\, 2102;	\\
 	c_3 = 0210\, 0\, 2102;	\\
	c_4 = 1021\, 0\, 0210;	\\
 	c_5 = 1021\, 0\, 2100.	
\end{array}
\]
In the contexts $c_1$, $c_2$ and $c_5$, the central occurrence of $0$ is the first letter in the image $\tau(0)$.
Indeed, the first occurrence of $0$ in the word $00$ can only be the image of $2$ and the words $12$, $22$ and $20$ do not occur in $x$.
Therefore we necessarily have the following factorization for $c_1$:
\[
	c_1 = \underbrace{0}_{\tau(2)} \underbrace{021}_{\tau(1)} \underbrace{021}_{\tau(0)} \underbrace{0}_{\tau(2)} 0.
\]
Similar arguments show that in $c_3$ (resp., in $c_4$) the central occurrence of $0$ is the first letter in the image $\tau(1)$ (resp., $\tau(2)$). We have
\[
	c_3 = \underbrace{021}_{\tau(0)} \underbrace{0}_{\tau(2)} \underbrace{021}_{\tau(1)} 02
	\qquad \text{and} \qquad 
	c_4 = 1 \underbrace{021}_{\tau(0)}  \underbrace{0}_{\tau(2)} \underbrace{021}_{\tau(1)} 0.
\]

Let us now formalize the precise definition of recognizability.
Let $x = (x_n)_{n \in \mathbb{Z}} \in A^\Z$ be an infinite word. 
Given two integers $i,j$ with $i \leq j$, we let $x_{[i,j]}$ (resp., $x_{[i,j)}$) denote the factor $x_i x_{i+1} \cdots x_j$ (resp., $x_i x_{i+1} \cdots x_{j-1}$) $x_{[i,i)} = \varepsilon$, where $\varepsilon$ is the empty word, i.e., the identity element of $A^*$.

Assume that the morphism $\sigma:A^* \to A^*$ is non-erasing and has an admissible fixed point $x = (x_n)_{n \in \mathbb{Z}}~\in~A^\Z$.
For all $p \in \N$, we let $f_x^{(p)}$ denote the function
$$
f_x^{(p)}: \Z \to \Z, i \mapsto 
f_x^{(p)} (i) = 
\begin{cases}
	|\sigma^p (x_{[0,i)})|, 	& 	\text{if } i > 0;	\\
	0, 							&	\text{if } i=0;		\\
	-|\sigma^p (x_{[i,0)})|, 	& 	\text{if } i < 0.
\end{cases}
$$
We set $E (x , \sigma^p) = f_x^{(p)}(\mathbb{Z})$.
When it is clear from the context, we write $f^{(p)}$ instead of $f_x^{(p)}$.
Observe that $\sigma$ being non-erasing, all functions $f^{(p)}_x$ are increasing.

\begin{definition} \label{def:rec}
We say that $\sigma$ is {\em recognizable on $x$} if there exists some constant $L > 0$ such that for all $i,m \in \Z$,
\begin{equation} \label{eq:def rec}
(x_{[m-L,m+L]} =  x_{[f^{(1)}(i)-L,f^{(1)}(i)+L]}) 
\Rightarrow 
(\exists j \in \Z)((m = f^{(1)}(j)) \wedge (x_i =x_j)).  
\end{equation}
We say that the factor $x_{[f^{(1)}(i)-L,f^{(1)}(i)+L]}$ {\em uniquely determines the letter $x_i$}.
By extension, we say that the factor $x_{[f^{(1)}(i)-L,f^{(1)}(j)+L]}$ uniquely determines the factor $x_{[i,j]}$. 

The smallest $L$ satisfying Equation~\eqref{eq:def rec} is called the {\em constant of recognizability} of~$\sigma$ for $x$.
When $\sigma$ is recognizable on all its admissible fixed points, we say that it is recognizable and its constant of recognizability is the greatest one.
\end{definition}

In the example above, the arguments given for the contexts of the letter $0$ can be similarly applied for the contexts of length 4 of the letters $1$ and $2$.
Thus those contexts also have unique factorizations as images of $\tau$.
Therefore the constant of recognizability of $\tau$ on the admissible fixed point $\tau^{\omega}(1\cdot 0)$ is at most 4.
A careful inspection of the contexts of length 4 actually shows that the constant is at most 3 (no context of length 3 appears as a subword of two contexts of length 4 having different factorization).
We can finally show that it cannot be equal to 2.
Indeed, the word $21\, 0\, 21$ is a context of length 2 of $0$ but appears as a subword of $c_1$ and $c_3$ that have different decompositions as images of $\tau$.
The constant of recognizability of $\tau$ is thus equal to 3.

\smallskip

The following result shows that any primitive aperiodic morphism is recognizable.


\begin{theorem}
\label{theo:mosse}
Let $\sigma :A^* \to A^*$ be an aperiodic primitive morphism and let $x \in A^\Z$ be an admissible fixed point of $\sigma$.
\begin{enumerate}
\item
\cite{Mosse:1992}
There exists $M>0$ such that, for all $i,m \in \Z$,
$$
	x_{[f^{(1)}(i)-M,f^{(1)}(i)+M]} =  x_{[m-M,m+M]} \Rightarrow m \in E (x, \sigma).  
$$
\item
\cite{Mosse:1996}
There exists $L>0$ such that, for all $i,j \in \Z$, 
$$
x_{[f^{(1)}(i)-L,f^{(1)}(i)+L]} =  x_{[f^{(1)}(j)-L,f^{(1)}(j)+L]} \Rightarrow x_i = x_j.  
$$
\end{enumerate}
\end{theorem}

By a careful reading of the proofs of Moss\'e's results, we can improve the statements as follows. 
The proof of Theorem~\ref{theo:maindetail} is given in Section~\ref{section:detailed result}.
Given a morphism $\sigma:A^* \to A^*$, we define $|\sigma|$ and $\langle \sigma \rangle$ by, respectively,
\[
	|\sigma| = \max_{a \in A} |\sigma(a)|
	\qquad \text{and} \qquad
	\langle\sigma\rangle = \min_{a \in A} |\sigma(a)|.
\]

\begin{theorem}
\label{theo:maindetail}
Let $\sigma :A^* \to A^*$ be a morphism with an admissible fixed point $x \in A^\Z$.
If $x$ is $k$-power-free and if there is some constant $N$ such that for all $n \in \mathbb{N}$, $|\sigma^n| \leq N \langle \sigma^n \rangle$, then $\sigma$ is recognizable on $x$ and its constant of recognizability for $x$ is at most $R |\sigma^{dQ}|+|\sigma^{d}|$, where
\begin{itemize}
\item
$R = \lceil  N^2(k+1)+2N\rceil$;
\item
$Q = 1 + p_x(R)\left(\sum_{\frac{R}{N} \leq i \leq RN+2} p_x(i) \right)$;
\item
$d \in \{1,2,\dots,\card A\}$ is such that for all words $u,v \in \cL(x)$, we have 
\[
	\sigma^{d-1}(u) \neq \sigma^{d-1}(v) \Rightarrow \forall n, \sigma^n(u) \neq \sigma^n(v). 
\] 
\end{itemize}
\end{theorem}

Then, we give some computable bounds for $N$, $R$, $k$, $Q$ and $d$ in the case of primitive morphisms.
These bounds are not sharp but can be expressed using only the cardinality of the alphabet and the maximal length $|\sigma|$.
The proof is given in Section~\ref{section: primitive case}.

\begin{theorem}
\label{theo:main}
Each aperiodic primitive morphism $\sigma :A^* \to A^*$ that has an admissible fixed point $x \in A^\Z$ is recognizable on $x$ and the constant of recognizability for $x$ is at most
\[
	2 |\sigma|^{6(\card A)^2 + 6(\card A) |\sigma|^{28(\card A)^2}} + |\sigma|^{(\card A)}. 
\]
\end{theorem}

The bound given in the previous theorem is far from being sharp. 
When the morphism $\sigma$ is injective on $A$, we can take $d=1$ in Theorem~\ref{theo:maindetail} and the computation in the proof of Theorem~\ref{theo:main} gives the bound 
\[
	2 |\sigma|^{6(\card A)^2 + 6 |\sigma|^{28(\card A)^2}} + |\sigma|. 
\]

The notion of recognizability is also known as {\em circularity} in the terminology of {\em D0L-systems} \cite{Kari&Rozenberg&Salomaa:1997}.
Assume that $\sigma:A^* \to A^*$ is non-erasing (i.e., $\sigma(a) \neq \varepsilon$ for all $a \in A$) and that $a \in A$ is a letter such that the language $\mathrm{Fac}(\sigma,a)$ defined as the set of factors occurring in $\sigma^n(a)$ for some $n$ is infinite.
Given a word $u = u_1 \cdots u_{|u|} \in \mathrm{Fac}(\sigma,a)$, we say that a triple $(p,v,q)$ is an {\em interpretation} of $u$ if $v \in \mathrm{Fac}(\sigma,a)$ and $\sigma(v) = puq$.
Two interpretations $(p,v,q),(p',v',q')$ are said to be {\em synchronized at position $k$} if there exist $i,j$ such that $1 \leq i \leq |v|$, $1 \leq j \leq |v'|$ and
\[
	\sigma(v_1 \cdots v_i) = p u_1 \cdots u_k 
	\quad \text{and} \quad
	\sigma(v_1' \cdots v_j') = p' u_1 \cdots u_k. 
\]
The word $u$ has a {\em synchronizing point (at position $k$)} if all its interpretations are synchronized (at position $k$).
The pair $(\sigma,a)$ is said to be {\em circular} if $\sigma$ is injective on $\mathrm{Fac}(\sigma,a)$ and if there is a constant $C$ such that all words of length at least $C$ have a synchronizing point. 
The smallest such $C$ is called the {\em synchronizing delay} of $\sigma$.
Thus, despite some considerations about whether we deal with fixed points or languages, recognizability and circularity are roughly the same notion and the synchronizing delay $C$ is associated with the constant of recognizability $L$ through $L \leq C \leq 2L+|\sigma|+1$.
Using the terminology of D0L-systems, Klouda and Medkov\'a obtained the following result which greatly improves our bounds, but for restricted cases.

\begin{theorem}[\cite{Klouda&Medkova:2016}]
If $\card A = 2$ and if $(\sigma,a)$ is circular with $\sigma:A^* \to A^*$ a $k$-uniform morphism for some $k \geq 2$, then the synchronizing delay $C$ of $(\sigma,a)$ is bounded as follows, where $d$ is the least divisor of $k$ greater than 1:
\begin{enumerate}
\item
$C \leq 8$, if $k = 2$;
\item
$C \leq k^2+3k-4$, if $k$ is an odd prime number;
\item
$C \leq k^2 \left( \frac{k}{d}-1\right) +5k-4$, otherwise.
\end{enumerate}
\end{theorem}




\section{Proof of Theorem~\ref{theo:maindetail}} \label{section:detailed result}

As is the case in Moss\'e's original proof, the proof of Theorem~\ref{theo:maindetail} goes in two steps. 

As a first step, we express the constant $M$ of Theorem~\ref{theo:mosse} in terms of the constants $N$, $R$, $k$ and $Q$ of Theorem~\ref{theo:maindetail}.
This is done in Proposition \ref{prop:rec1} with a proof following the lines of the proof of~\cite[Proposition 4.35]{Kurka:2003}.
The difference is that we take care of all the needed bounds to express the constant of recognizability.

As a second step, we show that the constant $L$ of Theorem~\ref{theo:mosse} can be taken equal to $M' + |\sigma^{d}|$, where $d$ is defined as in Theorem~\ref{theo:maindetail} and $M'$ is such that for all $i,m \in \Z$,
\[
	x_{[f^{(d)}(i)-M',f^{(d)}(i)+M']} =  x_{[m-M,m+M]} \Rightarrow m \in E (x, \sigma^d).  
\]
We first start with the following lemma.

\begin{lemma}
\label{lemme:longueurs_u_v_REC}
Let $\sigma:A^* \to A^*$ be a non-erasing morphism, $u \in A^*$ be a word and $n$ be a positive integer.
If $v=v_0 \cdots v_{t+1}  \in A^*$ is a word of length $t+2$ such that $\sigma^n(v[1,t])$ is a factor of $\sigma^n(u)$, and $\sigma^n(u)$ is a factor of $\sigma^n(v)$, then
\[
	  \frac{\langle \sigma^n\rangle}{|\sigma^n|} |u|-2 \leq t \leq \frac{|\sigma^n|}{\langle \sigma^n\rangle} |u|.
\]
\end{lemma}

\begin{proof}
Indeed, since $\sigma^n(v{[1,t]})$ is a factor of $\sigma^n(u)$ we have
$t \langle \sigma^n \rangle \leq |\sigma^n(v_{[1,t]})| \leq |\sigma^n(u)| \leq |u| |\sigma^n|$.
Hence $t \leq |u| |\sigma^n|/\langle \sigma^n\rangle$.
Similarly, since $\sigma^n(u)$ is a factor of $\sigma^n(v)$, we have $|u| \leq (t+2) |\sigma^n|/\langle \sigma^n\rangle$. 
We thus have
\[
	|u|\frac{\langle \sigma^n\rangle}{|\sigma^n|}-2 \leq t \leq |u| \frac{|\sigma^n|}{\langle \sigma^n\rangle} .
\]
\end{proof}


\begin{proposition}
\label{prop:rec1}
Let $\sigma :A^* \to A^*$ be a morphism with an admissible fixed point $x \in A^\Z$.
Assuming that $x$ is $k$-power-free and that there is some constant $N$ such that for all $n \in \mathbb{N}$, $|\sigma^n| \leq N \langle \sigma^n \rangle$,
we consider the constants
\begin{itemize}
\item
$R = \lceil N^2(k+1)+2N\rceil$; 
\item
$Q = 1 + p_x(R)\left(\sum_{\frac{R}{N} \leq i \leq RN+2} p_x(i) \right)$.
\end{itemize}
The constant $M = R|\sigma^Q|$ is such that for all $i,m \in \Z$,
\begin{align}
\label{align:recM}
x_{[f^{(1)}(i)-M,f^{(1)}(i)+M]} =  x_{[m-M,m+M]} \Rightarrow m \in E (x, \sigma ).  
\end{align}

\end{proposition}

\begin{proof}
We follow the lines of the proof of \cite[Theorem~\ref{theo:mosse}]{Kurka:2003}.
Obviously, if Equation~\eqref{align:recM} is true when we replace $M$ by some $l \leq M$, then it is true with $M$.
Let us show such an $l$ exists. 
We proceed by contradiction, assuming that for all $l \leq M$, there exist $i,j$ such that $x_{[i-l,i+l]} = x_{[j-l,j+l]}$ with $i \in E(x, \sigma)$ and $j \notin E (x,\sigma )$.
For each integer $p$ such that $0 < p \leq Q$, we consider the integer $l_p=R|\sigma^p| \leq M$.
Let $i_p$ and $j_p$ be some integers such that 
\begin{equation*}
	x_{[i_p-l_p,i_p+l_p]} = x_{[j_p-l_p,j_p+l_p]}, \qquad  \text{with } i_p \in E(x,\sigma ) \text{ and} \, j_p \notin E(x,\sigma ).
\end{equation*}
We let $r_p$ and $s_p$ denote the smallest integers such that
\begin{eqnarray*}
\card \left( [i_p - r_p,i_p)\, \cap E(x,\sigma^p )\right)  
&=&  \left\lceil\frac{R}{2}\right\rceil;
 \\
\card \left( [i_p,i_p + s_p] \cap E(x,\sigma^p ) \right)  
&=&  \left\lfloor\frac{R}{2}\right\rfloor+1.	
\end{eqnarray*}
There is an integer $i_p'$ such that 
\[
	f^{(p)}(i_p') = i_p-r_p
	\qquad \text{and} \qquad
	f^{(p)}(i_p'+R) = i_p+s_p.
\]
We set 
\[
	u_p = x_{[i_p',i_p'+R)}.
\] 
We have $\sigma^p(u_p) = x_{[i_p-r_p,i_p+s_p)}$. 

Notice that any interval of length $l_p$ contains at least $R-1$ elements of $E (x ,  \sigma^p )$.
We thus have $i_p - l_p  \leq i_p - r_p \leq    i_p + s_p \leq i_p + l_p$. 
Consequently we also have 
\begin{align}
\label{align:upq}
x_{[j_p-r_p,j_p+s_p )} = \sigma^p(u_p).
\end{align}
However, $j_p - r_p$ does not need to belong to $E(x, \sigma^p )$.
Let $j_p'$ and $t_p$ denote the unique integers such that
\begin{equation}
\label{eq:bornes jp'}
\begin{array}{rcl}
	f^{(p)}(j_p') < & j_p - r_p & \leq f^{(p)}(j_p'+1)	;	\\
	f^{(p)}(j_p'+t_p+1) \leq & j_p + s_p & < f^{(p)}(j_p'+t_p+2).
\end{array}
\end{equation}
Consequently, the word $\sigma^p (x_{[j_p'+1,j_p'+t_p]})$ is a factor of $\sigma^p (u_p)$ and the word $\sigma^p (u_p)$ is a factor of $\sigma^p (x_{[j_p',j_p'+t_p+1]})$.
By Lemma~\ref{lemme:longueurs_u_v_REC}, we have 
\begin{equation}\label{eq:bornes tp}
	R\frac{\langle \sigma^p \rangle}{|\sigma^p|}-2 \leq t_p \leq R \frac{|\sigma^p|}{\langle \sigma^p \rangle}.
\end{equation}
Hence
\[
	\frac{R}{N}-2 \leq t_p \leq R N.
\]
Let $v_p = x_{[j_p',j_p'+t_p+1]}$.
The number of possible pairs of words $(u_p,v_p)$ is at most
\[
	p_x(R) \left( \sum_{ \frac{R}{N} \leq i \leq {RN+2}} p_x(i)\right) 
	< Q.
\]  
Therefore, there exist $p$ and $q$ in $[1, Q]$ such that $p<q$ and $(u_p,v_p) = (u_q,v_q)$. 
In particular, we also have $t_p=t_q$.
We write 
$$
t=t_p, \qquad u = u_p, \qquad v = v_p, \qquad \tilde{v} = x_{[j_p'+1,j_p'+t]}.
$$
Using the above notation we recall that we have
\begin{eqnarray}
	u	=&	x_{[i_p',i_p'+R)} &= x_{[i_q',i_q'+R)}; \\
\label{eq:W}
	v	=&	x_{[j_p',j_p'+t+1]} &= x_{[j_q',j_q'+t+1]}.	
\end{eqnarray}
Let $A_p$, $B_p$, $A_q$ and $B_q$ be the words 
\begin{eqnarray*}
	A_p &=& x_{[j_p-r_p,f^{(p)}(j_p'+1))};		\\
	B_p &=& x_{[f^{(p)}(j_p'+t+1),j_p+s_p)};	\\
	A_q &=& x_{[j_q-r_q,f^{(q)}(j_q'+1))};		\\
	B_q &=& x_{[f^{(q)}(j_q'+t+1),j_q+s_q)}.
\end{eqnarray*}
We thus have 
\begin{equation}
\label{eq:A_pB_p}
	x_{[j_p-r_p,j_p+s_p)} = A_p \sigma^p(\tilde{v} ) B_p
	\qquad \text{and} \qquad
	x_{[j_q-r_q,j_q+s_q)} = A_q \sigma^q(\tilde{v} ) B_q,
\end{equation}
with, using~\eqref{eq:bornes jp'},
\begin{equation}\label{eq:longueur Ap Bp}
	\max \{|A_p|,|B_p|\} \leq |\sigma^p| 
	\qquad \text{and} \qquad
	\max \{|A_q|,|B_q|\} \leq |\sigma^q|. 
\end{equation}
From~\eqref{align:upq} and~\eqref{eq:A_pB_p}, we obtain
\[
	\sigma^{q-p}(A_p) \sigma^q(\tilde{v}) \sigma^{q-p}(B_p) = A_q \sigma^q(\tilde{v} ) B_q.
\]
We claim that 
\begin{equation}
\label{eq:claim}
A_q = \sigma^{q-p}(A_p) \quad \text{(and hence $B_q = \sigma^{q-p}(B_p)$)}.
\end{equation} 
If not, the word $\sigma^q( \tilde{v}  )$ has a prefix which is a power $w^r$ with $r=\left\lfloor\frac{|\sigma^q(\tilde{v})|}{||A_q| - |\sigma^{q-p}(A_p)||}\right\rfloor$.
Since, using~\eqref{eq:bornes tp} and~\eqref{eq:longueur Ap Bp}, 
\[
	|\sigma^q( \tilde{v})| \geq t \langle \sigma^q\rangle \geq \left(\frac{R}{N}-2\right)\langle \sigma^q\rangle
\quad \hbox{ and } \quad 
	||A_q| - |\sigma^{q-p}(A_p)|| \leq |\sigma^q|,
\]
we deduce from the choice of $R$ that $r \geq k+1$, which contradicts the definition of $k$.
We thus have $A_q = \sigma^{q-p}(A_p)$ and $B_q = \sigma^{q-p}(B_p)$.

We now show that the elements of $E(x,\sigma)$ occur in the two intervals $[i_q-r_q,i_q+s_q]$ and $[j_q-r_q,j_q+s_q]$ at the same relative positions, i.e., 
\begin{equation}
\label{eq:claim end}
	[j_q-r_q,j_q+s_q] \cap E(x,\sigma) = ([i_q-r_q,i_q+s_q] \cap E(x,\sigma)) - (i_q-j_q).
\end{equation}
This will contradict the fact that $i_q$ belongs to $E(x,\sigma)$ and $j_q$ does not.

By~\eqref{eq:W}, we have
\[
	\sigma^p(v) 
	= x_{[f^{(p)}(j_p'),f^{(p)}(j_p'+t+2))} 
	= x_{[f^{(p)}(j_q'),f^{(p)}(j_q'+t+2))}.
\]
Since $\sigma^p(u)$ is a factor of $\sigma^p(v)$, we deduce from~\eqref{eq:bornes jp'} that there exists $m_q \in \Z$ such that 
\begin{align}
\label{align:qqq}
	f^{(p)}(j_q') < m_q -r_p < m_q + s_p < f^{(p)}(j_q'+t+2)
\end{align}
and 
\[
	x_{[m_q-r_p,m_q+s_p)} = \sigma^p(u) = A_p \sigma^p(\tilde{v}) B_p.
\]
By applying $\sigma^{q-p}$, we obtain 
\[
	x_{[f^{(q-p)}(m_q-r_p),f^{(q-p)}(m_q+s_p))} = A_q \sigma^q(\tilde{v}) B_q ,
\]
and, from \eqref{align:qqq}, 
\[
	f^{(q)}(j_q') < f^{(q-p)}(m_q -r_p) < f^{(q-p)}(m_q + s_p) < f^{(q)}(j_q'+t+2) .
\]
As we also have 
\[
	x_{[j_q - r_q,j_q+s_q)} = A_q \sigma^q(\tilde{v}) B_q
\]
with, by~\eqref{eq:bornes jp'},
\[
	f^{(q)}(j_q') <  j_q - r_q \leq f^{(q)}(j_q'+1) \leq f^{(q)}(j_q'+t+1) \leq j_q + s_q < f^{(q)}(j_q'+t+2),
\]
we apply the same argument as to show~\eqref{eq:claim} and get $j_q-r_q = f^{(q-p)}(m_q-r_p)$ (hence $j_q+s_q = f^{(q-p)}(m_q+s_p)$).
We thus get that $j_q-r_q$ belongs to $E(x, \sigma^{q-p}) \subset E(x, \sigma)$.
Since we also have 
\begin{eqnarray*}
	x_{[{f^{(1)}}^{-1}(j_q-r_q),{f^{(1)}}^{-1}(j_q+s_q))} = \sigma^{q-p-1}(x_{[m_q-r_p,m_q+s_p)}) = \sigma^{q-p-1}(A_p \sigma^p(\tilde{v}) B_p), \\
	x_{[{f^{(1)}}^{-1}(i_q-r_q),{f^{(1)}}^{-1}(i_q+s_q))} = \sigma^{q-1}(x_{[i_q',i_q'+R)}) = \sigma^{q-p-1}(A_p \sigma^p(\tilde{v}) B_p),
\end{eqnarray*}
we get 
\[
	x_{[{f^{(1)}}^{-1}(j_q-r_q),{f^{(1)}}^{-1}(j_q+s_q))} = x_{[{f^{(1)}}^{-1}(i_q-r_q),{f^{(1)}}^{-1}(i_q+s_q))},
\]
with $j_q-r_q, i_q-r_q$ belonging to $E(x,\sigma)$.
By applying $\sigma$ to these two words, we thus obtain~\eqref{eq:claim end}, which ends the proof.
\end{proof}


Proposition~\ref{prop:rec1} gives a more precise statement than Item 1 in Theorem~\ref{theo:mosse}.
It also makes Item 2 more precise in the case of morphisms that are injective on $A$ by taking  $L = M+|\sigma|$.
For non-injective morphisms, a key argument in Moss\'e's original proof is to prove the existence of an integer $d$ such that for all $a,b \in A$, if $\sigma^n(a) = \sigma^n(b)$ for some $n$, then $\sigma^d(a)=\sigma^d(b)$.
Theorem~\ref{theo:exponent card A} below ensures that we can take $d = (\card A)-1$.


\begin{theorem}[{\cite[Theorem 3]{Ehrenfeucht&Rozenberg:1978}}]
\label{theo:exponent card A}
Let $\sigma:A^* \to A^*$ be a morphism such that $\sigma(A) \neq \{\varepsilon\}$.
For all words $u,v \in A^*$, we have 
\[
	\sigma^{(\card A)-1}(u) \neq \sigma^{(\card A)-1}(v) \Rightarrow \forall n, \sigma^n(u) \neq \sigma^n(v). 
\] 
\end{theorem}

We now give the proof of Item 2 in Theorem~\ref{theo:mosse}.

\begin{proposition}
\label{prop:rec2}
Let $\sigma :A^* \to A^*$ be a morphism with an admissible fixed point $x \in A^\Z$.
Let $d \in \{1,2,\dots,\card A \}$ be such that for all words $u,v \in \cL(x)$,  
\[
	\sigma^{d-1}(u) \neq \sigma^{d-1}(v) \Rightarrow \forall n, \sigma^n(u) \neq \sigma^n(v). 
\] 
If $M$ is a constant such that for all $i,m \in \Z$,
\[
x_{[f^{d}(i)-M,f^{d}(i)+M]} = x_{[m-M,m+M]} \Rightarrow m \in E (x, \sigma^{d}),
\]
then $\sigma$ is recognizable on $x$ and its constant of recognizability for $x$ is at most $M + |\sigma^{d}|$.
\end{proposition}

\begin{proof}
Let $i,m \in \mathbb{Z}$ such that 
$$
	x_{[f^{(1)}(i)-M-|\sigma^d|,f^{(1)}(i)+M+|\sigma^d|]}
	=
	x_{[m-M-|\sigma^d|, m+M+|\sigma^d|]}.	
$$
By the definition of $M$, there exists $j \in \mathbb{Z}$ such that $m = f^{(1)}(j)$.
Our goal is to show that $x_i = x_j$.

There exists $k \in \mathbb{Z}$ such that 
\[
	f^{(1)}(i)-|\sigma^d | < f^{(d)}(k) \leq f^{(1)}(i) < f^{(d)}(k+1) \leq f^{(1)}(i)+|\sigma^d |. 
\]
In particular, this implies that $f^{(d-1)}(k) \leq i < f^{(d-1)}(k+1)$.

Consider $c = f^{(1)}(i) - f^{(d)}(k)$ and $d = f^{(d)}(k+1) - f^{(1)}(i)$.
We have 
\begin{eqnarray*}
	x_{[f^{(d)}(k)-M,f^{(d)}(k)+M]} 
	&=& 
	x_{[f^{(1)}(j)-c-M,f^{(1)}(j)-c+M]};	\\
	x_{[f^{(d)}(k+1)-M,f^{(d)}(k+1)+M]} 
	&=& 
	x_{[f^{(1)}(j)+d-M,f^{(1)}(j)+d+M]}.
\end{eqnarray*}
By the definition of $M$, there exists $l \in \mathbb{Z}$ such that 
\[
	f^{(d)}(l) = f^{(1)}(j)-c
	\quad \text{and} \quad
	f^{(d)}(l+1) = f^{(1)}(j)+d.
\]
We thus have $f^{(d-1)}(l) \leq j < f^{(d-1)}(l+1)$, and,
\[
	x_{[f^{(d)}(k),f^{(d)}(k+1))} = x_{[f^{(d)}(l),f^{(d)}(l+1))}.
\]
Hence $\sigma^d(x_k) = \sigma^d(x_l)$.
By the definition of $d$, we also have $\sigma^{d-1}(x_k) = \sigma^{d-1}(x_l)$.
Hence 
\[
	x_{[f^{(d-1)}(k),f^{(d-1)}(k+1))} = x_{[f^{(d-1)}(l),f^{(d-1)}(l+1))}.
\]
Since we have $f^{(1)}(i) - f^{(d)}(k) = f^{(1)}(j) - f^{(d)}(l)$, we also have $i - f^{(d-1)}(k) = j - f^{(d-1)}(l)$.
Hence $x_i = x_j$.
\end{proof}








\section{Proof of Theorem~\ref{theo:main}}
\label{section: primitive case}

In this section, we show that the constants appearing in Theorem~\ref{theo:maindetail} can all be bounded by some computable constants.
In all what follows, we assume that $\sigma:A^* \to A^*$ is a primitive morphism. 
By taking a power of $\sigma$ if needed, we can assume that it has an admissible fixed point $x \in A^\Z$.
Furthermore, we have $\cL(x) = \cL(y)$ for all admissible fixed points $y$ of $\sigma$. 
We let $\cL(\sigma)$ denote this set and we write $\cL_n(\sigma) = \cL(\sigma) \cap A^2$.
The constants appearing in Theorem~\ref{theo:maindetail} are thus the same whatever the admissible fixed point we consider and the morphism is recognizable.

With the morphism $\sigma$, one associates its {\em incidence matrix} $M_\sigma$ defined by $(M_\sigma)_{a,b} = |\sigma(b)|_a$, where $|u|_a$ denotes the number of occurrences of the letter $a$ in the word $u$.
If $\sigma$ is a primitive morphism, it is well known that for all $a \in A$ there exists a constant $c_a$ such that $|\sigma^n(a)| \leq c_a \alpha^n$ for all $n$, where $\alpha$ is the dominant eigenvalue of $M_\sigma$ (see~\cite{CharlierLeroyRigo:2016} for a detailed study of $|\sigma^n(a)|$). 

\begin{lemma}[\cite{Horn&Johnson:1990}]
\label{lemma:wielandt}
A $d \times d$ matrix $M$ is primitive if and only if there is an integer $k \leq d^2 -2d +2$ such that $M^k$ contains only positive entries. 
\end{lemma}

Given an infinite word $x \in A^\Z$ and a word $u \in \cL(x)$, a {\em return word} to $u$ in $x$ is a word $r$ such that $ru$ belongs to $\cL(x)$, $u$ is a prefix of $ru$ and $ru$ contains exactly two occurrences of $u$.
The infinite word $x$ is {\em linearly recurrent} if it is {\em recurrent} (all words in $\mathcal{L} (x)$ appear infinitely many times in $x$) and there exists some constant $K$ such that for all $u \in \cL(x)$, any return word to $u$ has length at most $K|u|$.


The next two results give bounds on the constants appearing in Theorem~\ref{theo:maindetail}.

\begin{theorem}[\cite{Durand&Host&Skau:1999}]
\label{theo:encad}
If $x \in A^\Z$ is a aperiodic and linearly recurrent sequence for the constant $K$, then $x$ is $(K+1)$-power-free and $p_x(n) \leq K n$ for all $n$.
\end{theorem}


\begin{proposition}[\cite{Durand:1998}]
\label{prop:sublinrec}
Let $\sigma : A^* \to A^*$ be an aperiodic primitive morphism and $x$ be one of its admissible fixed points. 
Then, for all $n$, we have 
\[
	|\sigma^n| \leq |\sigma|^{(\card A)^2} \langle \sigma^n\rangle.
\]
Furthermore, $x$ is linearly recurrent for some constant 
\[
	K_\sigma < |\sigma|^{4(\card A)^2}.
\]
\end{proposition}
\begin{proof}
Durand \cite{Durand:1998} showed that the constant of linear recurrence $K_\sigma$ is at most equal to $TN|\sigma|$, where 
\begin{itemize}
\item
$N$ is a constant such that $|\sigma^n| \leq N \langle \sigma^n\rangle$ for all $n$;
\item
$T$ is the maximal length of a return word to a word in $\mathcal{L}_2(\sigma)$.
\end{itemize}
Here we only prove that $N \leq |\sigma|^{(\card A)^2}$ and $T \leq 2|\sigma|^{2(\card A)^2}$. 
The constant of linear recurrence is thus at most $2 |\sigma|^{1+3(\card A)^2} < |\sigma|^{4(\card A)^2}$.

Let us write $d = \card A$.
By Lemma~\ref{lemma:wielandt}, the matrix $M_\sigma^{d^2}$ contains only positive entries.
For all $n \geq 0$ and all $a \in A$, we have $|\sigma^{n+d^2}(a)| = \sum_{b \in A} |\sigma^{d^2}(a)|_b|\sigma^n(b)| \geq |\sigma^n|$.
Since this is true for all $a$, we get $|\sigma^n| \leq \langle \sigma^{n+{d^2}}\rangle \leq |\sigma^{d^2}| \langle \sigma^n\rangle$, so $N \leq |\sigma^{d^2}|$.

Let $a \in A$ such that $\sigma$ is prolongable on $a$.
Thus for all $n$, any word that occurs in $\sigma^n(a)$ also occurs in $\sigma^{n+1}(a)$.
Let us show that for all $n > d^2$, any word $u \in \cL_2(\sigma)$ occurs in $\sigma^n(a)$.
For all $n$, the words of $\cL_2(\sigma)$ that occur in $\sigma^{n+1}(a)$ occur in images under $\sigma$ of the words of $\cL_2(\sigma)$ that occur in $\sigma^n(a)$. 
As any word occurring in $\sigma^n(a)$ also occurs in $\sigma^{n+1}(a)$, the words of $\cL_2(\sigma)$ that occur in $\sigma^{n+1}(a)$ are those that occur in $\sigma^n(a)$ together with those occurring in the images under $\sigma$ of these words.
Thus, if there is a word of $\cL_2(\sigma)$ that does not occur in $\sigma^n(a)$, there is a sequence $(u_1,u_2,\dots,u_n)$ of words in $\cL_2(\sigma)$ such that for all $i \leq n$, $u_i$ occurs in $\sigma^i(a)$ and does not occur in $\sigma^{i-1}(a)$.
Hence all words $u_1, \dots, u_n$ are distinct.
For $n > d^2$, this is a contradiction since there are at most $d^2$ words in $\cL_2(\sigma)$.
Thus, for any letter $b \in A$, all words $u \in \cL_2(\sigma)$ occur in $\sigma^{2d^2}(b)$.
We deduce that $T \leq 2|\sigma^{2d^2}|$.  
\end{proof}

\begin{proof}[Proof of Theorem~\ref{theo:main}]
We just have to carry out the computation.
Using Theorem~\ref{theo:encad}, Proposition~\ref{prop:sublinrec} and the notation of Theorem \ref{theo:maindetail}, we can take $d = \card A$ and we successively have 
\begin{eqnarray*}
	k 	&\leq & 1 + K_\sigma 	 \leq  |\sigma|^{4d^2};
	\\
	N 	& \leq & |\sigma|^{d^2};
	\\
	R   & = & \lceil  N^2(k+1)+2N\rceil 	 
		\leq  |\sigma|^{2d^2} (|\sigma|^{4d^2}+1) + 2|\sigma|^{d^2}   
		\leq  2|\sigma|^{6d^2};
	\\
	Q 	&=& 1 + p_x(R) 
	\left(
	\sum_{\frac{R}{N} \leq i \leq RN+2} p_x(i) 
	\right)  
		\leq   K_\sigma 2|\sigma|^{6d^2}
	\left(
	\sum_{0 \leq i \leq 2+2|\sigma|^{7d^2}} i K_\sigma
	\right)  
		\leq  6 |\sigma|^{28d^2}.
\end{eqnarray*}
We finally get that the constant of recognizability of $\sigma$ is at most 
\[
	2 |\sigma|^{6d^2} |\sigma|^{6 d |\sigma|^{28d^2}} + |\sigma|^d 
	= 
	2 |\sigma|^{6d^2 + 6d |\sigma|^{28d^2}} + |\sigma|^d. 
\]
\end{proof}




\section{Recognizability of powers of morphisms}

Theorem~\ref{theo:maindetail} gives a general bound on the constant of recognizability of recognizable morphisms.
Powers of a recognizable morphism $\sigma$ are obviously recognizable.
However, the bound given in Theorem~\ref{theo:maindetail} applied to $\sigma^p$ is far from being optimal. 
In this section we give two results concerning the constant of recognizability of $\sigma^p$. 


\begin{proposition}
If $\sigma:A^* \to A^*$ is recognizable on $x \in A^\Z$ and if $L$ is the constant of recognizability of $\sigma$ for $x$, then for all $p>0$, $\sigma^p$ is recognizable on $x$ and its constant of recognizability for $x$ is at most $L \sum_{i=0}^{p-1} |\sigma^i|$.
\end{proposition}
\begin{proof}
The result holds by induction on $p>0$.
The case $p = 1$ is trivial.
Let us assume that the result holds for $p-1$ and let us prove it for $p$.
The infinite word $x$ is obviously an admissible fixed point of $\sigma^p$.
With $L_p = L \sum_{i=0}^{p-1} |\sigma^i|$, let us show that for all $i \in \Z$, the word 
\[
	x_{[f^{(p)}(i)-L_p,f^{(p)}(i)+L_p]}
\]
uniquely determines the letter $x_i$.

Let $m$ and $M$ be, respectively, the smallest and the largest integer such that 
\begin{equation}\label{eq:encadrement m M}
f^{(p)}(i)-L_p \leq f^{(p-1)}(m)-L_{p-1} < 
f^{(p-1)}(M)+L_{p-1} \leq f^{(p)}(i)+L_p
\end{equation}
and let us show that 
\begin{equation}\label{eq:encadrement m M 2}
	m \leq
	f^{(1)}(i) - L 
	< 
	f^{(1)}(i) + L
	\leq M.
\end{equation}
We consider the first inequality with $m >0$; the other cases are similar.
The integer $m$ being the smallest one satisfying~\eqref{eq:encadrement m M}, we have
\[
	f^{(p-1)}(m-1)-L_{p-1} < f^{(p)}(i)-L_p.
\]	
Since we have $f^{(p-1)}(m) = f^{(p-1)}(m-1) + |\sigma^{p-1}(x_{m-1})|$ and $L_p-L_{p-1} = L |\sigma^{p-1}|$, we get
\begin{equation}\label{eq: minoration f^p(i)}
	f^{(p)}(i) > f^{(p-1)}(m) + L|\sigma^{p-1}| - |\sigma^{p-1}(x_{m-1})| 
	\geq f^{(p-1)}(m) + (L-1)|\sigma^{p-1}|.
\end{equation}
Assume by contradiction that $f^{(1)}(i) < m + L$, hence that $f^{(1)}(i) \leq m + L-1$.
The function $f^{(p-1)}$ being increasing, we have
\[
	f^{(p-1)}(f^{(1)}(i)) = f^{(p)}(i) \leq f^{(p-1)} \left( m + L -1 \right) = f^{(p-1)}(m) + |\sigma^{p-1}(x_{[m,m+L-1)})|.
\]
We thus get
\[
	f^{(p)}(i) \leq f^{(1)}(m) + (L-1)|\sigma^{p-1}|,
\]
which contradicts~\eqref{eq: minoration f^p(i)}.

Let us now finish the proof of the result.
Using the induction hypothesis, the word $x_{[f^{(p-1)}(m)-L_{p-1},f^{(p-1)}(M)+L_{p-1}]}$ uniquely determines $x_{[m,M]}$.
As $x_{[f^{(p-1)}(m)-L_{p-1},f^{(p-1)}(M)+L_{p-1}]}$ is a factor of $x_{[f^{(p)}(i)-L_p,f^{(p)}(i)+L_p]}$ by~\eqref{eq:encadrement m M} and $x_{[f^{(1)}(i)-L,f^{(1)}(i)+L]}$ is a factor of $x_{[m,M]}$ by~\eqref{eq:encadrement m M 2}, the word $x_{[f^{(p)}(i)-L_p,f^{(p)}(i)+L_p]}$ uniquely determines $x_{[f^{(1)}(i)-L,f^{(1)}(i)+L]}$.
We conclude by the definition of recognizability.
\end{proof}



\begin{corollary}
If $\sigma:A^* \to A^*$ is aperiodic primitive and if $L$ is its constant of recognizability on $x \in A^\Z$,
then $\sigma^p$ is recognizable on $x$ and its constant of recognizability for $x$ is at most $L C \frac{\alpha^p-1}{\alpha-1}$, where $\alpha$ is the dominant eigenvalue of $M_\sigma$ and $C$ is a constant such that $|\sigma^p| \leq C \alpha^p$ for all $p$.
In particular, the constant $C$ can be taken equal to 
\[
\frac{\max_{1\leq k \leq \card A} y_k}{\min_{1\leq k\leq \card A} y_k},
\]
where $y = (y_k)_{1 \leq k \leq \card A}$ is a positive eigenvector of $M_\sigma$.
\end{corollary}
\begin{proof}
The proof directly follows from~\cite[Corollary~8.1.33]{Horn&Johnson:1990}.
\end{proof}





\section{Acknowledgments}

This work was supported by the Hubert Curien Partnership Tournesol
entitled ``Algorithmique des substitutions et syst\`emes de
num\'eration''.


\def\ocirc#1{\ifmmode\setbox0=\hbox{$#1$}\dimen0=\ht0 \advance\dimen0
  by1pt\rlap{\hbox to\wd0{\hss\raise\dimen0
  \hbox{\hskip.2em$\scriptscriptstyle\circ$}\hss}}#1\else {\accent"17 #1}\fi}

\begin{thebibliography}{10}

\bibitem{Canterini&Siegel:2001}
V.~Canterini and A.~Siegel, Geometric representation of substitutions of
  {P}isot type, {\em Trans. Amer. Math. Soc.} {\bf 353} (2001), 5121--5144.

\bibitem{CharlierLeroyRigo:2016}
\'E. Charlier, J.~Leroy, and M.~Rigo, Asymptotic properties of free monoid morphisms, {\em Linear Algebra Appl.} {\bf 500} (2016), 119--148.
  
\bibitem{Choffrut&Karhumaki:1997}
C.~Choffrut and J.~Karhum\"aki, Combinatorics of words.
\newblock In {\em Handbook of Formal Languages}, {V}ol.~1, 
Springer, 1997, pp.~329--438. 

\bibitem{Durand:1998}
F.~Durand, A characterization of substitutive sequences using return words,
  {\em Discrete Math.} {\bf 179} (1998), 89--101.

\bibitem{Durand&Host&Skau:1999}
F.~Durand, B.~Host, and C.~Skau, Substitutional dynamical systems, {B}ratteli diagrams and dimension groups, {\em Ergodic Theory Dynam. Systems} {\bf 19} (1999), 953--993.

\bibitem{Ehrenfeucht&Rozenberg:1978}
A.~Ehrenfeucht and G.~Rozenberg, Simplifications of homomorphisms, {\em Inform. and Control} {\bf 38} (1978), 298--309.

\bibitem{Pytheas}
N.~P.~Fogg, {\em Substitutions in Dynamics, Arithmetics and
  Combinatorics}, {Lecture Notes in Mathematics}, Vol.~1794,
  Springer-Verlag, 2002. 

\bibitem{Holton&Zamboni:1999}
C.~Holton and L.~Q. Zamboni, Descendants of primitive substitutions, {\em
  Theory Comput. Syst.} {\bf 32} (1999), 133--157.

\bibitem{Horn&Johnson:1990}
R.~A. Horn and C.~R. Johnson, {\em Matrix Analysis}, Cambridge University
  Press, 1990.

\bibitem{Kari&Rozenberg&Salomaa:1997}
L.~Kari, G.~Rozenberg, and A.~Salomaa, L systems.
\newblock In {\em Handbook of Formal Languages}, Vol.~1, 
Springer, 1997, pp.~253--328.

\bibitem{Klouda&Medkova:2016}
K.~Klouda and K.~Medkov\'a, Synchronizing delay for binary uniform morphisms,
  {\em Theoret. Comput. Sci.} {\bf 615} (2016), 12--22.

\bibitem{Kurka:2003}
P.~K\ocirc{u}rka, {\em Topological and Symbolic Dynamics}, {
  Cours Sp\'ecialis\'es}, Vol.~11, Soci\'et\'e Math\'ematique de France, 2003.

\bibitem{Mignosi&Seebold:1993}
F.~Mignosi and P.~S\'e\'ebold, If a {D0L} language is {$k$}-power free then it is circular.
\newblock In {\em Automata, Languages and Programming},
{Lecture Notes in Comput. Sci.}, Vol.~700, Springer, 1993, pp.~507--518.

\bibitem{Mosse:1992}
B.~Moss\'e, Puissances de mots et reconnaissabilit\'e des points fixes d'une substitution, {\em Theoret. Comput. Sci.} {\bf 99} (1992), 327--334.

\bibitem{Mosse:1996}
B.~Moss\'e, Reconnaissabilit\'e des substitutions et complexit\'e des suites automatiques, {\em Bull. Soc. Math. France} {\bf 124} (1996), 329--346.

\bibitem{Queffelec:2010}
M.~Queff\'elec, {\em Substitution Dynamical Systems---Spectral Analysis},  {Lecture Notes in Mathematics}, Vol.~1294, Springer-Verlag, 2nd edition, 2010.

\end{thebibliography}



\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}: Primary 68R15,
Secondary 68Q01.

\noindent \emph{Keywords:}
combinatorics on words, substitution, recognizability, circularity.

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received October 14 2016;
revised versions received  November 9 2016; January 26 2016; February 6 2017.
Published in {\it Journal of Integer Sequences}, February 10 2017.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                

                                                                                




