\def\Z{\mathbb Z} \def\R{\mathbb R} \def\Q{\mathbb Q} \def\N{\mathbb N} \def\A{\mathcal A} \def\B{\mathcal B} \def\C{\mathcal C} \newcommand{\Zp}{{\Z}^{+}_{\beta}} \def\pf{\begin{proof}} \def\pfk{\end{proof}} \newcommand{\ddb}{d_\beta(1)} \documentclass[12pt]{article} \usepackage{amssymb,amsmath,amsthm,epic} \textwidth= 6.25in \textheight= 9.0in \topmargin = -10pt \evensidemargin=10pt \oddsidemargin=10pt \headsep=25pt \parskip=10pt \font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9 %\theoremstyle{theorem} \newtheorem{lem}{Lemma}[section] \newtheorem{obs}[lem]{Observation} \newtheorem{prop}[lem]{Proposition} \newtheorem{thm}[lem]{Theorem} \newtheorem{coro}[lem]{Corollary} \theoremstyle{definition} \newtheorem{de}[lem]{Definition} \newtheorem{pozn}[lem]{Remark} \newtheorem{ex}{Example} \begin{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \vspace*{-40pt} \centerline{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 5 (2005), \#A14} \vskip 40pt \begin{center} {\bf COMPLETE CHARACTERIZATION OF SUBSTITUTION INVARIANT STURMIAN SEQUENCES} \vskip 20pt {\bf Peter Bal\'a\v zi, Zuzana Mas\'akov\'a\footnote{Corresponding author. Email: {\tt masakova@km1.fjfi.cvut.cz}}, Edita Pelantov\'a}\\ {\smallit Department of Mathematics, Czech Technical University, \\ Trojanova 13, 120 00 Praha 2, Czech Republic}\\ \end{center} \vskip 30pt \centerline{\smallit Received: 2/18/04, Revised: 5/25/05, Accepted: 7/6/05, Published: 7/8/05} \vskip 30pt \centerline{\bf Abstract} \noindent We provide a complete characterization of substitution invariant inhomogeneous bi-directional pointed Sturmian sequences. The result is analogous to that obtained by Berth\'e et al.~\cite{berthe} and Yasutomi~\cite{yasutomi} for one-directional Sturmian words. The proof is constructive, based on the geometric representation of Sturmian words by a cut-and-project scheme. \pagestyle{myheadings} \markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 5 (2005), \#A14\hfill} \thispagestyle{empty} \baselineskip=15pt \vskip 30pt %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section*{\normalsize 1. Introduction} \addtocounter{section}{+1} Sturmian words have been extensively studied from many aspects. Several equivalent definitions as aperiodic words of minimal complexity ${\C}(n)=n+1$, as balanced aperiodic sequences or as mechanical words have been derived already in~\cite{coven,hedlund}. Recently, new characterizations have been developed using return words~\cite{vuil} or using palindromic structure~\cite{palin}. For a survey of results known on Sturmian words we refer, for example, to~\cite{lothaire,berstel2}. Among the properties of Sturmian words that have been in focus during the past few years is their invariance under non-trivial substitutions and a weaker property of substitutivity, according to the {\em slope} $\alpha$ and {\em intercept} $\beta$ of the Sturmian word. If $\beta=0$, the Sturmian word is called homogeneous, otherwise inhomogeneous. The first results of this kind are found in~\cite{brown}. Then it has been shown independently by several authors~\cite{crisp,ito,komatsu,seebold} that a homogeneous one-directional Sturmian word is invariant under a substitution if and only if the slope $\alpha$ is a Sturm number. Parvaix~\cite{parvaix} has given a sufficient condition for an inhomogeneous one-directional Sturmian word to be substitution invariant. However, his condition does not include all substitution invariant Sturmian words. In another paper~\cite{parvaix2} he studies inhomogeneous bi-directional non-pointed Sturmian words and proves that they are invariant under substitution if and only if the slope $\alpha$ is a Sturm number and the intercept $\beta$ belongs to the field $\Q(\alpha)$. Yasutomi~\cite{yasutomi} solved the question of substitution invariance of inhomogeneous one-directional Sturmian sequences. Berth\'e et al.~\cite{berthe} give an alternative proof and describe the matrices of the corresponding substitutions. The question of substitutivity of Sturmian words seems to be less difficult to solve. It has been derived in~\cite{berthe2} that Sturmian words are substitutive if and only if their slope $\alpha$ is a quadratic number and the intercept $\beta$ belongs to $\Q(\alpha)$. This is in fact a result analogous to~\cite{adam}, which provides a characterization of substitutive words coding 3-interval exchanges. In our paper we provide a complete characterization of substitution invariant inhomogeneous bi-directional pointed Sturmian sequences. The result is analogous to that of~\cite{yasutomi,berthe}. However, the method used here is rather simpler and novel in the study of substitution properties of Sturmian words. It is based on the geometric representation of Sturmian words by a cut-and-project scheme. It is worth noting that similar reasoning can be used for characterizing substitution invariant infinite words that code an orbit under a 3-interval exchange transformation. An important advantage is that our paper is self-contained and does not use any deep results from elsewhere, except the simple fact that incidence matrix of Sturmian morphisms has unit determinant, which follows from~\cite{seebold}. The main result proved in our paper is the following. \begin{thm}\label{t1} Let $\alpha$ be an irrational number, $\alpha\in(0,1)$, $\beta\in[0,1)$. The pointed bi-directional Sturmian word with slope $\alpha$ and intercept $\beta$ is invariant under a non-trivial substitution if and only if the following three conditions are satisfied: \begin{itemize} \item[{\rm (i)}] $\alpha$ is a quadratic irrational with conjugate $\alpha'\notin(0,1)$, i.e. $\alpha$ is a Sturm number, \item[{\rm (ii)}] $\beta\in\Q(\alpha)$, \item[{\rm (iii)}] $\alpha'\leq \beta' \leq 1-\alpha'$ or $1-\alpha'\leq \beta' \leq \alpha'$, where $\beta'$ is the image of $\beta$ under the Galois automorphism of the quadratic field $\Q(\alpha)$. \end{itemize} \end{thm} For the proof of Theorem~\ref{t1} we need to recall the basic notion of substitutions (Section 2), define a geometric representation of a Sturmian word and show that it can be recast in an algebraic formalism (Section 3). Then we prove a necessary and sufficient condition for substitution invariance of Sturmian words in terms of fixed points of a map $g_\lambda$. This result is stated as Theorem~\ref{t} in Section 4 and proved in Section 5. Using the study of fixed points of $g_\lambda$ (Section 6) we show that the condition of Theorem~\ref{t} is equivalent to the simple algebraic criterion given in Theorem~\ref{t1} (Section 7). Note that the proof given here is constructive. For a given Sturmian word with slope $\alpha$ and intercept $\beta$ that satisfies conditions (i)--(iii) of Theorem~\ref{t1} one can determine the substitution as described in Section 8. We use the notation $\N$ for the set of positive integers and $\N_0=\{0\}\cup\N$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section*{\normalsize 2. Preliminaries}\addtocounter{section}{+1} \addtocounter{lem}{-1} In this paper we study pointed bi-directional Sturmian words $$ (u_n)_{n\in\Z} = \cdots u_{-2}u_{-1}|u_0u_1u_2\cdots $$ For every such word $(u_n)_{n\in\Z}$ there exists an irrational $\alpha\in(0,1)$ (slope) and a real $\beta\in[0,1)$ (intercept) such that $$ \begin{array}{lll} \hbox{ either }&\qquad u_n=\underline{s}_{\alpha,\beta}(n):= \lfloor (n+1)\alpha + \beta \rfloor - \lfloor n\alpha+\beta \rfloor\,,&\qquad\hbox{ for }\ n\in\Z,\\[2mm] \hbox{ or }&\qquad u_n=\overline{s}_{\alpha,\beta}(n):= \lceil (n+1)\alpha + \beta \rceil - \lceil n\alpha+\beta \rceil\,,&\qquad\hbox{ for }\ n\in\Z. \end{array} $$ It is obvious that $(u_n)_{n\in\Z}$ is a binary word on the alphabet $\{0,1\}$. One can show that the densities of letters $0$ and $1$ in the word $(u_n)_{n\in\Z}$ defined above are well defined \begin{eqnarray*} \varrho(0)&:=&\lim_{n\to\infty}\frac{\hbox{number of 0 in the word } u_{-n}\cdots u_{-1}|u_0u_1\cdots u_n}{2n+1} \ = \ 1-\alpha\,,\\ \varrho(1)&:=&\lim_{n\to\infty}\frac{\hbox{number of 1 in the word } u_{-n}\cdots u_{-1}|u_0u_1\cdots u_n}{2n+1} \ = \ \alpha\,. \end{eqnarray*} Denote $\A^*$ the free monoid generated by the alphabet $\A=\{0,1\}$ endowed with the operation of concatenation. A map $\varphi$ of $\A^*$ into itself such that $\varphi(uv)=\varphi(u)\varphi(v)$ for all pairs of finite words $u,v$ is called a morphism. The morphism is non-erasing, if $\varphi(i)$ is not an empty word for any $i\in\A$. A non-erasing morphism $\varphi$ is called a substitution. The action of $\varphi$ can be extended to infinite words $(u_n)_{n\in\Z} = \cdots u_{-2}u_{-1}|u_0u_1u_2\cdots$ by $\cdots \varphi(u_{-2})\varphi(u_{-1})|\varphi(u_0)\varphi(u_1)\varphi(u_2)\cdots$. We say that the word $(u_n)_{n\in\Z}$ is invariant under the substitution $\varphi$, if $$ \cdots \varphi(u_{-2})\varphi(u_{-1})|\varphi(u_0)\varphi(u_1)\varphi(u_2)\cdots= \cdots u_{-2}u_{-1}|u_0u_1u_2\cdots $$ One can associate with every substitution on a binary alphabet a matrix ${\mathbb A}\in\Z^{2\times2}$ by $$ {\mathbb A}_{ij} = \hbox{ number of letters $j$ in the word } \varphi(i)\,,\qquad i,j\in\{0,1\}\,. $$ This matrix is called the incidence matrix of the substitution. Note that the term incidence matrix is sometimes used for the transpose ${\mathbb A}^T$. If $\varphi$ is a morphism that maps a Sturmian word to a Sturmian word, it is called Sturmian morphism. Every Sturmian morphism is clearly non-erasing, i.e. is a substitution. As a consequence of~\cite{seebold} the incidence matrix ${\mathbb A}$ of a non-trivial (i.e.~non-identic) Sturmian morphism is irreducible and has determinant $\pm1$. If $(u_n)_{n\in\Z}$ is invariant under substitution $\varphi$ and if the densities of letters 0 and 1 are well defined, then the vector $(\varrho(0),\varrho(1))$ is a left eigenvector of ${\mathbb A}$. In particular, if a bi-directional Sturmian word of slope $\alpha$ is invariant under a substitution, then $(1-\alpha,\alpha)$ is a left eigenvector of the non-negative irreducible integer matrix ${\mathbb A}$. This eigenvector corresponds according to Perron-Frobenius theorem to the dominant eigenvalue, say $\lambda$, of ${\mathbb A}$, which is called the substitution factor. The characteristic polynomial of the matrix ${\mathbb A}$ is a monic quadratic polynomial with integer coefficients. The substitution factor $\lambda$ is thus a quadratic integer. Let us denote by $\lambda'$ the algebraic conjugate of $\lambda$, i.e. the other root of the characteristic polynomial. Since $\det{\mathbb A}=\pm1$, we have $\lambda\lambda'=\pm1$. The substitution factor $\lambda$ is thus an algebraic unit $\lambda>1$ and $\lambda'\in(-1,1)$. Without loss of generality we consider the matrix ${\mathbb A}$ of determinant $+1$, hence $\lambda'\in(0,1)$. (If $(u_n)$ is invariant under some substitution $\varphi$ with matrix ${\mathbb A}$, then it is invariant also under $\varphi^2$ with matrix ${\mathbb A}^2$.) Necessarily, the components of the eigenvector $(1-\alpha,\alpha)$ belong to the quadratic field $\Q(\lambda)=\{a+b\lambda\mid a,b\in\Q\}$. The Galois automorphism on this field is defined by the prescription $$ x=a+b\lambda \quad\mapsto\quad x'=a+b\lambda'\,. $$ Since ${\mathbb A}$ has integer components, its second eigenvalue is $\lambda'$ and left eigenvectors corresponding to $\lambda'$ are scalar multiples of $(1-\alpha',\alpha')$. As a consequence of the Perron-Frobenius theorem, the components of this eigenvector must have opposite signs, i.e. $\alpha'(1-\alpha')<0$, which implies that $\alpha'\notin(0,1)$. We have thus derived by a simple argument a necessary condition in order that a Sturmian word is invariant under a non-trivial substitution. \begin{prop}\label{brumbrum} If a Sturmian word with irrational slope $\alpha\in(0,1)$ and intercept $\beta\in[0,1)$ is invariant under a non-trivial substitution, then $\alpha$ is a quadratic irrational number with algebraic conjugate $\alpha'\notin(0,1)$. \end{prop} Note that the condition given in the above proposition means that $\alpha$ is a Sturm number. Sturm numbers can be defined using continued fractions~\cite{crisp}, here we use the characterization of Allauzen~\cite{allauzen}. For $\beta=0$ the condition is also sufficient, as it was shown by several authors~\cite{seebold,crisp,ito,komatsu}. From now on we consider Sturmian words the slope of which is a Sturm number. As we have said, bi-directional Sturmian words can be described using mechanical words $\underline{s}_{\alpha,\beta}$ or $\overline{s}_{\alpha,\beta}$. Let $(u_n)_{n\in\Z}$ be a pointed bi-directional word in the alphabet $\{0,1\}$. Let us define a word $(v_n)_{n\in\Z}$ by $v_n=u_{-n-1}$, i.e. $\cdots v_{-2}v_{-1}|v_0v_1v_2\cdots \quad=\quad \cdots u_2u_1u_0|u_{-1}u_{-2}\cdots$. We define also an infinite word $(w_n)_{n\in\Z}$ by $w_n=1-v_n$ for all $n\in\Z$. Obviously, either all the three pointed bi-directional infinite words $(u_n)_{n\in\Z}$, $(v_n)_{n\in\Z}$, $(w_n)_{n\in\Z}$ are invariant under a non-trivial substitution, or none of them is. It is easy to see that $$ u_n=\underline{s}_{\alpha,\beta}(n)=\lfloor (n+1)\alpha + \beta \rfloor - \lfloor n\alpha+\beta \rfloor $$ implies \begin{eqnarray*} v_n&=&\overline{s}_{\alpha,1-\beta}(n)=\lceil (n+1)\alpha +1-\beta\rceil - \lceil n\alpha +1 -\beta\rceil\,,\\ w_n&=&\underline{s}_{1-\alpha,\beta}(n) = \lfloor(n+1)(1-\alpha)+\beta\rfloor - \lfloor n(1-\alpha)+\beta\rfloor\,. \end{eqnarray*} Therefore in the study of invariance of pointed bi-directional Sturmian sequences under a substitution we shall focus on the words $\underline{s}_{\alpha,\beta}$. Since $\underline{s}_{\alpha,\beta}$ is invariant under a non-trivial substitution if and only if $\underline{s}_{1-\alpha,\beta}$ is, we consider without loss of generality words \begin{equation}\label{ZP} \begin{align} &u_n= \lfloor (n+1)\alpha + \beta \rfloor - \lfloor n\alpha+\beta \rfloor,\quad n\in\Z,\quad \nonumber\\ &\alpha\in(0,1) \ \hbox{ quadratic irrational},\qquad \alpha'<0,\quad\\ &\beta\in[0,1).\nonumber \end{align} \end{equation} If an infinite word is invariant under a non-trivial substitution, it can be geometrically represented using a selfsimilar set $\Sigma\subset\R$. We say that $\Sigma$ is selfsimilar, if there exists $\lambda>1$ (called the selfsimilarity factor of $\Sigma$) such that $\lambda\Sigma\subset\Sigma$. The selfsimilar set which represents a substitution invariant word is defined in the following way. Denote by $\ell(0)$ and $\ell(1)$ the components of a positive right eigenvector of the incidence matrix ${\mathbb A}$ corresponding to the dominant eigenvalue $\lambda$. Define $$ \begin{array}{ll} t_0=0, &\\[2mm] \displaystyle{t_n=\sum_{i=0}^{n-1}\ell(u_i)} &\hbox{ for }\ n\geq 1,\\ \displaystyle{t_n=-\sum_{i=n}^{-1}\ell(u_i)} &\hbox{ for }\ n\leq -1. \end{array} $$ Then the set $\Sigma=\{t_n \mid n\in\Z\}$ satisfies \begin{equation}\label{eq:selfs} \lambda\Sigma\subset\Sigma\,. \end{equation} From the construction of the sequence $(t_n)_{n\in\Z}$ we have $$ t_{n+1}-t_n = \ell(u_n)\qquad\hbox{ for all }\ n\in\Z. $$ \begin{pozn}\label{ouvej} The fact that $\binom{\ell(0)}{\ell(1)}$ is a right eigenvector of the incidence matrix ${\mathbb A}$ corresponding to the eigenvalue $\lambda$ ensures that for every $n\in\Z$ such that $t_{n+1}-t_n=\ell(0)$, the sequence of distances in the set $\Sigma$ between points $\lambda t_n$ and $\lambda t_{n+1}$ is the same. Similar statement is true for all $n\in\Z$ such that $t_{n+1}-t_n=\ell(1)$. This fact is illustrated on Figure~\ref{f1}. \end{pozn} \begin{figure}[ht] \begin{center} \begin{picture}(370,155) \put(4,28){\line(1,0){364}} \put(4,100){\line(1,0){364}} % \put(7,25){\line(0,1){80}} \put(23,20){\makebox(0,0){$1$}} \put(23,107){\makebox(0,0){$1$}} \put(40,25){\line(0,1){80}} \put(7,28){\circle*{5}} \put(56,20){\makebox(0,0){$1$}} \put(56,107){\makebox(0,0){$1$}} \put(72,25){\line(0,1){80}} \put(82,20){\makebox(0,0){$0$}} \put(82,107){\makebox(0,0){$0$}} \put(92,20){\line(0,1){85}} \put(92,28){\circle*{5}} \put(92,100){\circle*{5}} \put(108,20){\makebox(0,0){$1$}} \put(112,106){\makebox(0,0){$1$}} \put(124,25){\line(0,1){80}} \put(124,100){\circle*{5}} \put(134,20){\makebox(0,0){$0$}} \put(136,107){\makebox(0,0){$0$}} \put(144,20){\line(0,1){125}} \put(144,100){\circle*{5}} \put(160,20){\makebox(0,0){$1$}} \put(160,107){\makebox(0,0){$1$}} \put(176,25){\line(0,1){80}} %\put(145,125){\makebox(0,0){$0$}} \put(144,144.45){\circle*{5}} %\put(144,144.45){\line(0,-1){10}} \put(144,28){\circle*{5}} \put(176,100){\circle*{5}} \put(192,20){\makebox(0,0){$1$}} \put(160,88){\makebox(0,0){$\underbrace{\hspace*{30pt}}_{\hbox{\footnotesize $\ell(1)$}}$}}%% \put(134,89){\makebox(0,0){$\underbrace{}_{\hbox{\footnotesize $\,\ell(0)$}}$}}%%% \put(189,106){\makebox(0,0){$1$}} \put(208,25){\line(0,1){80}} \put(208,100){\circle*{5}} \put(218,20){\makebox(0,0){$0$}} \put(218,107){\makebox(0,0){$0$}} \put(228,20){\line(0,1){85}} \put(228,100){\circle*{5}} \put(244,20){\makebox(0,0){$1$}} \put(244,107){\makebox(0,0){$1$}} \put(260,25){\line(0,1){80}} \put(228,28){\circle*{5}} %\put(225,100){\circle*{5}} \put(276,20){\makebox(0,0){$1$}} \put(276,107){\makebox(0,0){$1$}} \put(292,25){\line(0,1){80}} \put(302,20){\makebox(0,0){$0$}} \put(302,107){\makebox(0,0){$0$}} \put(312,25){\line(0,1){80}} \put(312,28){\circle*{5}} \put(328,20){\makebox(0,0){$1$}} \put(328,107){\makebox(0,0){$1$}} \put(344,25){\line(0,1){80}} \put(354,20){\makebox(0,0){$0$}} \put(354,107){\makebox(0,0){$0$}} \put(364,25){\line(0,1){80}} \put(364,28){\circle*{5}} % \qbezier(144,144.45)(92,100)(7,28) \qbezier(144,144.45)(124,100)(92,28) \qbezier(144,144.45)(176,100)(228,28) \qbezier(144,144.45)(208,100)(312,28) \qbezier(144,144.45)(228,100)(364,28) \put(186,5){\makebox(0,0) {$\underbrace{\hspace*{83pt}}_{\hbox{$\lambda\ell(1)$}}$}} \put(118,5){\makebox(0,0) {$\underbrace{\hspace*{51pt}}_{\hbox{$\lambda \ell(0)$}}$}} \end{picture} \caption{Action of a substitution on the geometric representation of its fixed point.} \label{f1} \end{center} \end{figure} Recall that if $(u_n)_{n\in\Z}$ satisfies conditions~\eqref{ZP} and is invariant under a non-trivial substitution with matrix ${\mathbb A}$, then $(1-\alpha,\alpha)$ is a left eigenvector of ${\mathbb A}$ corresponding to the eigenvalue $\lambda$, and $(1-\alpha',\alpha')$ is a left eigenvector of ${\mathbb A}$ corresponding to the eigenvalue $\lambda'$. Since left and right eigenvectors corresponding to different eigenvalues are mutually orthogonal, every right eigenvector of the matrix ${\mathbb A}$ corresponding to the eigenvalue $\lambda$ must be orthogonal to $(1-\alpha',\alpha')$. However, this determines the eigenvector uniquely to be, up to a scalar multiple, $\binom{-\alpha'}{1-\alpha'}$. Since $\alpha$ is a Sturm number and satisfies~\eqref{ZP}, both components of this vector are positive, for the geometric representation $\Sigma$ of the infinite word $(u_n)_{n\in\Z}$ we can choose the lengths $\ell(0)=-\alpha'$ and $\ell(1)=1-\alpha'$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section*{\normalsize 3. Geometric representation of Sturmian words} \addtocounter{section}{+1} \addtocounter{lem}{-2} Let the word $(u_n)_{n\in\Z}$, and numbers $\alpha$, $\beta$ satisfy conditions~\eqref{ZP}. The set $$ \Sigma_{\alpha,\beta}:=\{ t_n \mid n\in\Z\}\,, $$ where $$ t_0=0\qquad\hbox{ and }\qquad t_{n+1}-t_n = \left\{ \begin{array}{cl} -\alpha', &\hbox{ if }\ u_n=0\,,\\[2mm] 1-\alpha', &\hbox{ if }\ u_n=1\,, \end{array}\right. $$ is called the geometric representation of the word $(u_n)_{n\in\Z}$. Note that the distances between adjacent points of $\Sigma_{\alpha,\beta}$ depend only on the slope and not on the intercept of the corresponding Sturmian word $(u_n)_{n\in\Z}$. The distance $-\alpha'$ corresponding to the letter $0$ is shorter, we will use the notation $S=-\alpha'$. The longer distance corresponding to the letter $0$ is denoted by $L=1-\alpha'$. \begin{pozn}\label{pozn:posledni} From what has been said and from Remark~\ref{ouvej} it is obvious that $(u_n)_{n\in\Z}$ is invariant under a non-trivial substitution if and only if there exists a quadratic unit $\lambda>1$, with conjugate $\lambda'\in(0,1)$, such that $\lambda\Sigma_{\alpha,\beta}\subset\Sigma_{\alpha,\beta}$, and for every $n$, such that $u_n=0$, the segments of the set $\Sigma_{\alpha,\beta}$ between points $\lambda t_n$ and $\lambda t_{n+1}$ are the same, and for every $n$, such that $u_n=1$, the segments of the set $\Sigma_{\alpha,\beta}$ between points $\lambda t_n$ and $\lambda t_{n+1}$ are the same. \end{pozn} Let us therefore study the properties of $\Sigma_{\alpha,\beta}$. \begin{prop} Let $\alpha$, $\beta$ satisfy~\eqref{ZP}. Then $$ \Sigma_{\alpha,\beta} = \{a-b\alpha' \mid a-b\alpha \in (\beta-1,\beta]\}\,. $$ \end{prop} \pf If $a-b\alpha\in(\beta-1,\beta]$, then $a=\lfloor b\alpha+\beta\rfloor$. Therefore $$ \{a-b\alpha' \mid a-b\alpha \in (\beta-1,\beta]\} = \{y_n:=\lfloor n\alpha+\beta\rfloor - n\alpha' \mid n\in\Z\}\,. $$ From~\eqref{ZP}, $(y_n)_{n\in\Z}$ is a strictly increasing sequence and $y_0=0$. Let us calculate the distances between consecutive points $y_n$, $y_{n+1}$. $$ y_{n+1}-y_n= \lfloor (n+1)\alpha+\beta\rfloor - \lfloor n\alpha+\beta\rfloor - \alpha' = u_n-\alpha'\,. $$ Thus $(y_n)_{n\in\Z} = (t_n)_{n\in\Z}$, as desired. \pfk It is useful to introduce for a quadratic $\alpha$ and its algebraic conjugate $\alpha'$ the sets $$ \Z[\alpha] = \{a+b\alpha \mid a,b\in\Z\}\qquad\hbox{ and }\qquad \Z[\alpha'] = \{a+b\alpha' \mid a,b\in\Z\}\,. $$ The above sets are generally distinct additive abelian groups, generally not closed under multiplication. (For example, the Sturm number $\alpha$, root of the polynomial $2x^2-1$, is not an algebraic integer and satisfies $\alpha^2=\frac12\notin\Z[\alpha]$.) Clearly $\Z[\alpha]$ and $\Z[\alpha']$ are subsets of the field $\Q(\alpha)=\Q(\alpha')$. Restriction of the Galois automorphism of $\Q(\alpha)$ on $\Z[\alpha]$, resp. $\Z[\alpha']$ is an isomorphism between these groups. Obviously, we have $$ \bigl(\Z[\alpha]\bigr)'=\Z[\alpha']\qquad\hbox{ and }\qquad \bigl(\Z[\alpha']\bigr)'=\Z[\alpha]. $$ The set $\Sigma_{\alpha,\beta}$ representing the Sturmian word $(u_n)_{n\in\Z}$ can therefore be written as $$ \Sigma_{\alpha,\beta} = \{ x\in\Z[\alpha'] \mid x'\in (\beta-1,\beta]\}. $$ Let us mention that $\Sigma_{\alpha,\beta}$ is a particular case of the so-called cut-and-project set. In fact, the abelian groups $\Z[\alpha]$, $\Z[\alpha']$ arise by projection of points of the lattice $\Z^2$ to the lines with slopes $\alpha'$, $\alpha$ respectively. More precisely, every lattice point $(-b,a)\in\Z^2$ can be written as $$ (-b,a)=(a+b\alpha)\vec{x}_1 + (a+b\alpha')\vec{x}_2\,, $$ where $$ \vec{x}_1=\frac{1}{\alpha'-\alpha}(1,\alpha')\quad\hbox{ and }\quad \vec{x}_2=\frac{1}{\alpha-\alpha'}(1,\alpha)\,. $$ The isomorphism $a+b\alpha \mapsto (a+b\alpha)'=a+b\alpha'$ between $\Z[\alpha]$ and $\Z[\alpha']$ is a correspondence between two projections of the same lattice point. A cut-and-project sequence is constructed by first projection of lattice points which have the second projection in a bounded interval $\Omega$; this amounts to $$ \Sigma_\alpha (\Omega) = \{x\in\Z[\alpha'] \mid x'\in\Omega\}\,. $$ In this notation, we have $\Sigma_{\alpha,\beta}=\Sigma_\alpha\bigl((\beta-1,\beta]\bigr)$. The construction of $\Sigma_{\alpha,\beta}$ as a cut-and-project set is illustrated on Figure~\ref{f:f}. For more details about the general definition of cut-and-project sets we refer to~\cite{meyer}, the onedimensional case useful for our considerations is described together with its properties in~\cite{kombi}. \begin{figure}[hbt]\begin{center} \setlength{\unitlength}{1mm} \begin{picture}(105, 95)(-5, 5) \put(-2.8,19.05){$\Omega\ \biggl\{$} %\drawline(99.7,51.9)(99.3,54.8) %\drawline(99.8,52.1)(97.8,54.1) \put(20,80){slope $\alpha'$} \put(98,70){slope $\alpha$} \put(105,50){$\Sigma_{\alpha,\beta}$} \put(23.2,6.6){$L$} \put(32.5,11.5){$S$} \put(41.8,16.8){$L$} \put(51.1,22.1){$S$} \put(61.4,27.8){$L$} \put(73,34){$L$} \put(83.5,39.5){$S$} \put(93.0,44.8){$L$} \put(10,5){\line(0,1){70}} \put(20,5){\line(0,1){70}}\put(30,5){\line(0,1){70}} \put(50,5){\line(0,1){70}} \put(60,5){\line(0,1){70}}\put(70,5){\line(0,1){70}} \put(80,5){\line(0,1){70}}\put(90,5){\line(0,1){70}} \put(5,10){\line(1,0){90}} \put(5,20){\line(1,0){90}}\put(5,30){\line(1,0){90}} \put(5,50){\line(1,0){90}} \put(5,60){\line(1,0){90}}\put(5,70){\line(1,0){90}} \qbezier(5,15.25)(50,39.5)(100,66.4) \qbezier(5,25.75)(50,49)(100,76.9) \qbezier(61.25,0)(31.7,55)(17.29,81.5) \put(10,20){\circle*{1.5}} \qbezier(10,20)(10.7,19)(16.9,7.58) \put(16.95,7.58){\circle*{1.5}} \put(20,30){\circle*{1.5}} \qbezier(20,30)(22.5,25)(29,14) \put(29,14){\circle*{1.5}} \put(30,30){\circle*{1.5}} \qbezier(30,30)(32.5,25)(36.6,18) \put(36.6,18){\circle*{1.5}} \put(48.2,24.3){\circle*{1.5}} \put(40,40){\circle*{1.5}} \qbezier(50,40)(52.5,35)(56.1,28.5) \put(56.1,28.5){\circle*{1.5}} \put(50,40){\circle*{1.5}} \qbezier(60,50)(62.5,45)(68.2,35) \put(68.2,35){\circle*{1.5}} \put(60,50){\circle*{1.5}} \qbezier(70,60)(72.5,55.3)(80.2,41.5) \put(80.2,41.5){\circle*{1.5}} \put(70,60){\circle*{1.5}} \qbezier(80,60)(82.5,55)(87.8,45.7) \put(87.8,45.7){\circle*{1.5}} \put(80,60){\circle*{1.5}} \qbezier(90,70)(92.5,65.3)(99.8,51.9) \put(99.8,51.9){\circle*{1.5}} \put(90,70){\circle*{1.5}} \linethickness{0.9pt} \put(40,0){\line(0,1){80}} \put(0,40){\line(1,0){100}} \linethickness{0.7pt} \qbezier(10,3.75)(55,28)(105,54.9) \end{picture} \medskip \caption{Construction of a cut-and-project sequence.} \label{f:f} \end{center}\end{figure} The following proposition shows the relation of the selfsimilarity factor of $\Sigma_{\alpha,\beta}$ to the abelian group $\Z[\alpha']$. \begin{prop}\label{haf} Let $\alpha,\beta$ satisfy conditions~\eqref{ZP} and let $\lambda>1$ be a quadratic unit with $\lambda'\in(0,1)$. Then $\lambda\Sigma_{\alpha,\beta}\subset\Sigma_{\alpha,\beta}\ $ if and only if $\ \lambda\Z[\alpha']=\Z[\alpha']$. \end{prop} \pf First let us show that the selfsimilarity of $\Sigma_{\alpha,\beta}$ implies $\lambda\Z[\alpha']=\Z[\alpha']$. Find $n,m\in\Z$, so that $t_{n+1}-t_n=-\alpha'$, $t_{m+1}-t_m=1-\alpha'$. $$ \left. \begin{array}{rcr} \lambda t_{n+1}, \lambda t_n\in\Sigma_{\alpha,\beta} \subset\Z[\alpha'] &\implies& -\lambda (t_{n+1}-t_n) = \lambda \alpha' \in \Z[\alpha']\\[2mm] \lambda t_{m+1}, \lambda t_m\in\Sigma_{\alpha,\beta} \subset\Z[\alpha'] &\implies& \lambda (1-\alpha') \in \Z[\alpha'] \end{array} \right\} \implies \quad \lambda \in\Z[\alpha']. $$ Since $\lambda\cdot 1$ and $\lambda\alpha'$ belong to $\Z[\alpha']$ and from the fact that $\Z[\alpha']$ is closed under addition, it follows that $\lambda\Z[\alpha']\subset \Z[\alpha']$. Since $\lambda$ is a unit, it satisfies $\lambda^2+A\lambda + 1=0$ for some $A\in\Z$. We thus have $\lambda^{-1}=-(\lambda+A)\in\Z[\alpha']$ and $\lambda^{-1}\alpha' =- (\lambda+A)\alpha'\in\Z[\alpha']$, which together imply $\lambda^{-1}\Z[\alpha'] \subset \Z[\alpha']$, which completes the first part of the proof. For the opposite implication let us show that $\lambda\Z[\alpha'] = \Z[\alpha']$ implies $\lambda\Sigma_\alpha(\Omega) = \Sigma_\alpha(\lambda'\Omega)$ for every bounded interval $\Omega$. It is a consequence of the following equalities, $$ \begin{aligned} \lambda\Sigma_\alpha(\Omega) &= \lambda \{x\in\Z[\alpha'] \mid x'\in\Omega\} = \{\lambda x\in\lambda\Z[\alpha'] \mid \lambda'x'\in\lambda'\Omega\} =\\ &= \{y\in\Z[\alpha'] \mid y'\in\lambda'\Omega\} = \Sigma_\alpha(\lambda'\Omega)\,. \end{aligned} $$ Directly from the definition of $\Sigma_\alpha(\Omega)$ it follows that $\Sigma_\alpha(\Omega_1)\subset\Sigma_\alpha(\Omega_2)$ if $\Omega_1\subset\Omega_2$. Since $0\in(\beta-1,\beta]$ and $\lambda'\in(0,1)$, we have $\lambda'(\beta-1,\beta] \subset(\beta-1,\beta]$ and therefore $$ \lambda\Sigma_{\alpha,\beta}=\Sigma_\alpha\bigl(\lambda'(\beta-1,\beta]\bigr) \subset\Sigma_{\alpha}\bigl((\beta-1,\beta]\bigr) = \Sigma_{\alpha,\beta}\,. $$ \pfk As a byproduct of the proof of the above proposition we have the following result. \begin{coro}\label{kvak} Let $\alpha$ satisfy~\eqref{ZP} and let $\lambda\Z[\alpha']=\Z[\alpha']$. Then $\lambda\Sigma_\alpha(\Omega) = \Sigma_\alpha(\lambda'\Omega)$ for every bounded interval $\Omega$. \end{coro} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section*{\normalsize 4. A necessary and sufficient condition}\addtocounter{section}{+1} \addtocounter{lem}{-4} Let us study the structure of the set $\Sigma_{\alpha,\beta}$. Since $\Sigma_{\alpha,\beta}\subset\Z[\alpha']$, every element of $\Sigma_{\alpha,\beta}$ is of the form $x'$, where $x'$ is the image of an $x\in\Z[\alpha]\cap(\beta-1,\beta]$ under the Galois automorphism of $\Q(\alpha)$. The distances between adjacent elements of $\Sigma_{\alpha,\beta}$ take values $L=1-\alpha'$ or $S=-\alpha'$. Therefore the right neighbour of a given $x'\in\Sigma_{\alpha,\beta}$ is either $x'+1-\alpha'$ or $x'-\alpha'$, according to whether $x+1-\alpha\in(\beta-1,\beta]$ or $x-\alpha\in(\beta-1,\beta]$. We can thus define a function $f:(\beta-1,\beta]\to(\beta-1,\beta]$ by $$ f(x) = \left\{ \begin{array}{cccr} x+1-\alpha & \hbox{ if } & x\in(\beta-1\,,\,\beta-1+\alpha] &=: \ \Omega_L,\\[2mm] x-\alpha & \hbox{ if } & x\in(\beta-1+\alpha\,,\,\beta] &=:\ \Omega_S. \end{array} \right. $$ From the graph of the function $f$, illustrated of Figure~\ref{f2}, it is obvious that $f$ is a 2-interval exchange transformation~\cite{rauzy}. The Sturmian word $(u_n)_{n\in\Z}$, defined by equation~\eqref{ZP} and represented by $\Sigma_{\alpha,\beta}$ is a coding of the orbit of $0$ under the map $f$, i.e.\ $u_n=0$ if $f^{n}(0)\in\Omega_S$, and $u_n=1$ if $f^{n}(0)\in\Omega_L$. \begin{pozn}\label{miau} In terms of the sequence $(t_n)_{n\in\Z}$, which represents the set $\Sigma_{\alpha,\beta}$, we have $f(t'_n) = t'_{n+1}$. For the left end-point of the short distance $t_{n+1}-t_n = -\alpha'$ we have $t'_n\in\Omega_S$. Similarly, for the left end-point of the long distance $t_{n+1}-t_n = 1-\alpha'$ we have $t'_n\in\Omega_L$. \end{pozn} \begin{pozn} Since $\alpha$ is irrational, we have $f^{n}(x)\neq x$ for every $n\in\Z\setminus\{0\}$ and every $x\in(\beta-1,\beta]$. The reason is that since $f^{n}(x)=x+n_1(-\alpha) + n_2(1-\alpha)$ for some $n_1,n_2\in\Z$ such that $n_1+n_2=n$, we obtain from $f^{n}(x) = x$ that $n_1(-\alpha)+n_2(1-\alpha)=0$, which implies $n_1=n_2=n=0$. \end{pozn} \begin{figure}[ht] \begin{center} \begin{picture}(175,156) \put(20,20){\vector(1,0){160}} \put(30,10){\vector(0,1){152}} \put(17,155){\makebox(0,0){$f(x)$}} \put(177,10){\makebox(0,0){$x$}} \put(140,20){\line(0,1){110}} \put(30,130){\line(1,0){110}} \put(80,20){\line(1,1){60}} \put(30,80){\line(1,1){50}} \put(15,11){\makebox(0,0){$\beta-1$}} % \put(75,141){\makebox(0,0){$c\!+\!d\!-\!1\!+\!\varepsilon$}} \put(80,10){\makebox(0,0){$\beta-1+\alpha$}} \put(140,10){\makebox(0,0){$\beta$}} \put(22,129){\makebox(0,0){$\beta$}} \put(10,80){\makebox(0,0){$\beta-\alpha$}} \put(80,20){\circle{5}} \put(30,80){\circle{5}} \put(140,80){\circle*{5}} \put(80,130){\circle*{5}} \dashline{3}(80,20)(80,130) \dashline{3}(30,80)(140,80) \end{picture} % \caption{The graph of the function $f$.} \label{f2} \end{center} \end{figure} As a motivation for definition of another important function $g_\lambda(x)$, note another property of the geometric representation of the word $(u_n)_{n\in\Z}$. The selfsimilarity $\lambda\Sigma_{\alpha,\beta}\subset\Sigma_{\alpha,\beta}=\{t_n\mid n\in\Z\}$ implies that $$ \forall\, t_n\in\Sigma_{\alpha,\beta}\quad \exists\, m\in\Z\quad\hbox{ such that }\quad \lambda t_m\leq t_n<\lambda t_{m+1}\,, $$ see also Figure~\ref{f1}. This however implies that there exists an index $i\geq 0$ such that $\lambda t_m=t_{n-i}$. For such $t_{n-i}$ we have $$ \lambda't'_m = t'_{n-i} = f^{-i}(t'_n)\in\lambda'(\beta-1,\beta] \qquad\implies\qquad t'_m = \frac1{\lambda'} f^{-i}(t'_n)\,. $$ \begin{de}\label{d:g} Let $\alpha,\beta$ satisfy conditions~\eqref{ZP} and let $\lambda>1$ be a quadratic unit with conjugate $\lambda'\in(0,1)$ such that $\lambda\Z[\alpha']=\Z[\alpha']$. For $x\in(\beta-1,\beta]$ let $$ {\rm ind}(x) := \min\{i\in\N_0 \mid f^{-i}(x)\in\lambda'(\beta-1,\beta]\} \qquad\hbox{ and }\qquad g_\lambda(x) =\frac1{\lambda'} f^{-{\rm ind}(x)}(x)\,. $$ \end{de} From what was said before the definition, it is obvious that the function $g_\lambda(x)$ is well defined for $x\in\{t'_n\mid n\in\Z\} = \Z[\alpha]\cap (\beta-1,\beta]$. Since $\Z[\alpha]$ is dense in $\R$ and the function $f$ is piece-wise linear, the function $g_\lambda(x)$ has sense for all $x\in(\beta-1,\beta]$. The following remark identifies two fixed points of $g_\lambda$ in $\Z[\alpha]\cap (\beta-1,\beta]$. \begin{pozn}\label{r:pevnebody}\ \begin{enumerate} \item[(a)] Since ${\rm ind}(0)=0$, we have $g_\lambda(0)=0$. \item[(b)] Since $t_0=0$, we have $\lambda t_{-1}1$ with conjugate $\lambda'\in(0,1)$ such that $\lambda\Z[\alpha']=\Z[\alpha']$ and $$ g_\lambda\bigl(\{\beta,\beta-1+\alpha\}\bigr) \subset \{\beta,\beta-1+\alpha\}\,. $$ \end{thm} The proof of the above theorem is a technical one, but its ideas are rather important and novel. Therefore we put it in a separate Section 5. \begin{pozn}\label{r:mocnina} Consider $(u_n)_{n\in\Z}$, $\alpha$, $\beta$ satisfying~\eqref{ZP}. If a quadratic unit $\lambda>1$ with conjugate $\lambda'\in(0,1)$ verifies $\lambda\Z[\alpha']=\Z[\alpha']$ and $g_\lambda\bigl(\{\beta,\beta-1+\alpha\}\bigr) \subset \{\beta,\beta-1+\alpha\}$, then $(u_n)_{n\in\Z}$ is invariant under a non-trivial substitution, say $\varphi$ and $\lambda$ is its substitution factor. Therefore the sequence $(u_n)_{n\in\Z}$ is invariant also under the substitution $\varphi^k$ for arbitrary $k\in\N$, which has the substitution factor $\lambda^k$. According to Theorem~\ref{t}, the substitution factor must satisfy $g_{\lambda^k}\bigl(\{\beta,\beta-1+\alpha\}\bigr) \subset \{\beta,\beta-1+\alpha\}$. As a consequence, while verifying the necessary and sufficient condition of Theorem~\ref{t}, we may limit our considerations, without loss of generality, to suitable powers $\lambda^k$. \end{pozn} Theorem~\ref{t} easily implies several facts proved by other authors by different means. We state them as Corollary~\ref{c:1} (cf.~\cite{parvaix2}) and Corollary~\ref{c:2} (cf.~\cite{crisp,ito,komatsu,seebold}). The definition of $g_\lambda$ and the condition $g_\lambda\bigl(\{\beta,\beta-1+\alpha\}\bigr) \subset \{\beta,\beta-1+\alpha\}$ implies the following result. \begin{coro}\label{c:1} Let $(u_n)_{n\in\Z}$ be a Sturmian word with slope $\alpha\in(0,1)$ and intercept $\beta$. If $(u_n)_{n\in\Z}$ is invariant under a non-trivial substitution, then $\beta\in\Q(\alpha)$. \end{coro} If $\beta=0$, then $t_0=\beta=0$. The definition of $f$ implies $f(\beta-1+\alpha)=f(-1+\alpha)=0=\beta=t_0$, and thus $t_{-1}=-1+\alpha'$. Since according to Remark~\ref{r:pevnebody}, $t_0$ and $t_{-1}$ are fixed points of $g_\lambda$, we obtain $g_\lambda\{0,-1+\alpha\}\subset\{0,-1+\alpha\}$, by which the necessary and sufficient condition of Theorem~\ref{t} is satisfied. For the following corollary it suffices to realize that conditions~\eqref{ZP} for $\alpha$ say that $\alpha$ is a Sturm number. \begin{coro}\label{c:2} Let $(u_n)_{n\in\Z}$ be a Sturmian word with slope $\alpha\in(0,1)$ and intercept $\beta=0$. Then $(u_n)_{n\in\Z}$ is invariant under a substitution if and only if $\alpha$ is a Sturm number. \end{coro} We shall further discuss the case $\beta\neq0$. Then $\beta\notin\lambda'(\beta-1,\beta]$, and therefore ${\rm ind}(\beta)\neq 0$. Since $f^{-1}(\beta)=\beta-1+\alpha$, we have $g_\lambda(\beta-1+\alpha)=g_\lambda(\beta)$. The condition $g_\lambda\bigl(\{\beta,\beta-1+\alpha\}\bigr) \subset \{\beta,\beta-1+\alpha\}$ is therefore equivalent to the fact that either $\beta-1+\alpha$ or $\beta$ is a fixed point of the function $g_\lambda$. \begin{pozn}\label{pozn:achichouvej} For intercept $\beta\neq 0$, Theorem~\ref{t} can be stated as follows:\\ {\it Let the sequence $(u_n)_{n\in\Z}$ and numbers $\alpha,\beta$ satisfy conditions~\eqref{ZP} and let $\beta\neq0$. Then $(u_n)_{n\in\Z}$ is invariant under a non-trivial substitution, if and only if there exists a quadratic unit $\lambda>1$ with conjugate $\lambda'\in(0,1)$ such that $\lambda\Z[\alpha']=\Z[\alpha']$ and $$ \beta \quad\hbox{ or }\quad \beta-1+\alpha \quad\hbox{ is a fixed point of }\quad g_\lambda\,. $$ } \end{pozn} Determining the fixed points of $g_\lambda$ in $\Q(\alpha)\cap(\beta-1,\beta]$ will be the subject of Section 6. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section*{\normalsize 5. Proof of Theorem~\ref{t}} \addtocounter{section}{+1} \addtocounter{lem}{-9} The proof of Theorem~\ref{t} will be divided into two parts. The necessity of the condition is given as Proposition~\ref{p:nec} and the sufficiency of the condition as Proposition~\ref{p:suf}. \begin{prop}\label{p:nec} Let $(u_n)_{n\in\Z}$, $\alpha,\beta$ satisfy conditions~\eqref{ZP} and let $(u_n)_{n\in\Z}$ be invariant under a non-trivial substitution. Then there exists a quadratic unit $\lambda>1$ with conjugate $\lambda'\in(0,1)$ such that $\lambda\Z[\alpha']=\Z[\alpha']$ and \begin{equation}\label{achich} g_\lambda\bigl(\{\beta,\beta-1+\alpha\}\bigr) \subset \{\beta,\beta-1+\alpha\}\,. \end{equation} \end{prop} \pf In Section 2 we have explained that substitution invariance implies the existence of a factor $\lambda>1$ being a quadratic unit, with conjugate $\lambda'\in(0,1)$, such that $\lambda\Sigma_{\alpha,\beta} \subset\Sigma_{\alpha,\beta}=\{t_n\mid n\in\Z\}$. In fact, $\lambda$ is the dominant eigenvalue of the incidence matrix. Proposition~\ref{haf} implies that $\lambda\Z[\alpha']=\Z[\alpha']$. Let us show that the factor $\lambda$ satisfies~\eqref{achich}. Important for our considerations is the partition of the interval $(\beta-1,\beta]$, given by the discontinuity of the function $f$, into $(\beta-1,\beta]=\Omega_L\cup\Omega_S$. Recall that $$ \Omega_L=(\beta-1,\beta-1+\alpha]\,,\qquad \Omega_S=(\beta-1+\alpha,\beta]\,. $$ Recall also that if $t_{n+1}-t_n=-\alpha'$, then according to Remark~\ref{miau}, the conjugate $t'_n$ of $t_n$ satisfies $t'_n\in\Omega_S$. Using the invariance under substitution, as explained in Remark~\ref{pozn:posledni}, we also know that the sequences of distances between points $\lambda t_n$ and $\lambda t_{n+1}$ for all such $n$ coincide. It follows using Remark~\ref{miau} that there exists an integer $k_S$ given as the length of the word $\varphi(0)$ such that \begin{equation}\label{e1} \begin{array}{lc} \hbox{for } i\in\{0,1,\dots,k_S-1\}\qquad &\hbox{ either }\ f^{i}(\lambda'\Omega_S)\subset\Omega_S \ \hbox{ or }\ f^{i}(\lambda'\Omega_S)\subset\Omega_L\,, \\[2mm] \hbox{and } &f^{k_S}(\lambda'\Omega_S)\subset\lambda'(\beta-1,\beta]\,. \end{array} \end{equation} Similarly, for all $n$ such that $t_{n+1}-t_n=1-\alpha'$, i.e. for all $n$ such that $t'_n\in\Omega_L$, there exists an integer $k_L$ given as the length of the word $\varphi(1)$ such that \begin{equation}\label{e2} \begin{array}{lc} \hbox{for } j\in\{0,1,\dots,k_L-1\}\qquad &\hbox{ either }\ f^{j}(\lambda'\Omega_L)\subset\Omega_S \ \hbox{ or }\ f^{j}(\lambda'\Omega_L)\subset\Omega_L\,, \\[2mm] \hbox{and } &f^{k_L}(\lambda'\Omega_L)\subset\lambda'(\beta-1,\beta]\,. \end{array} \end{equation} %$f^{(j)}(\lambda'\Omega_L)\subset\Omega_S$ or %$f^{(j)}(\lambda'\Omega_L)\subset\Omega_L$ for every $j\in\{0,1,\dots,k_L-1\}$ and %$f^{(k_L)}(\lambda'\Omega_L)\subset\lambda'(\beta-1,\beta]$. In the statements~\eqref{e1} and~\eqref{e2} we have used a simple fact which follows from the piece-wise linearity of the function $f$, namely that if $I_1,I_2\subset(\beta-1,\beta]$ are right-semi-closed intervals, then $f(I_1\cap\Z[\alpha])\subset I_2\cap\Z[\alpha]$ implies $f(I_1)\subset I_2$. Now realize that every element of $(\Sigma_{\alpha,\beta})'=(\beta-1,\beta]\cap \Z[\alpha]$ is covered by an iteration $$ f^{i}(\lambda't'_n)\quad\hbox{ for some $n\in\Z$ and some }\ i\in \left\{\begin{array}{ll} \{0,1,\dots,k_S-1\}&\hbox{ if } t_{n+1}-t_n = -\alpha'\,,\\[2mm] \{0,1,\dots,k_L-1\}&\hbox{ if } t_{n+1}-t_n = 1-\alpha'\,. \end{array}\right. $$ Therefore \begin{equation}\label{e3} \bigcup_{i=0}^{k_S-1} f^{i}(\lambda'\Omega_S) \quad\cup\quad \bigcup_{j=0}^{k_L-1} f^{j}(\lambda'\Omega_L) \quad=\quad(\beta-1,\beta]\,, \end{equation} where the union of $k_S+k_L$ intervals on the left hand side is disjoint. As a consequence of~\eqref{e1} and~\eqref{e2} the discontinuity point $\beta-1+\alpha$ of the function $f$ and the boundary point $\beta$ of the interval $(\beta-1,\beta]$ must be covered in the union~\eqref{e3} by the boundary point of some interval $f^{i}(\lambda'\Omega_S)$ or $f^{j}(\lambda'\Omega_L)$. More precisely, we must have \begin{equation}\label{e4} \begin{array}{lll} \hbox{either }\quad&\beta =f^{i}(\lambda'\beta) &\hbox{ for some } i\in\{0,1,\dots,k_S-1\}\,,\\ \hbox{ or } &\beta =f^{j}\bigl(\lambda'(\beta-1+\alpha)\bigr)\quad &\hbox{ for some } j\in\{0,1,\dots,k_L-1\}\,, \end{array} \end{equation} and \begin{equation}\label{e5} \begin{array}{lll} \hbox{either }\quad &\beta-1+\alpha =f^{i}(\lambda'\beta) &\hbox{ for some } i\in\{0,1,\dots,k_S-1\}\,,\\ \hbox{ or } &\beta-1+\alpha =f^{j}\bigl(\lambda'(\beta-1+\alpha)\bigr)\quad &\hbox{ for some } j\in\{0,1,\dots,k_L-1\}\,. \end{array} \end{equation} Let us study~\eqref{e4}. If $\beta= f^{i}(\lambda'\beta)$ for $i\in\{0,1,\dots,k_S-1\}$, then $$ {\rm ind}(\beta)=i\quad\hbox{ and }\quad \beta = \frac1{\lambda'} f^{-{\rm ind}(\beta)}(\beta) = g_\lambda(\beta)\,. $$ On the other hand, if $\beta=f^{j}\bigl(\lambda'(\beta-1+\alpha)\bigr)$ for $j\in\{0,1,\dots,k_L-1\}$, then $$ {\rm ind}(\beta)=j\quad\hbox{ and }\quad \beta+\alpha-1 = \frac1{\lambda'} f^{-{\rm ind}(\beta)}(\beta) = g_\lambda(\beta)\,. $$ This implies $g_\lambda(\beta)\in\{\beta,\beta-1+\alpha\}$. In the same way we derive from~\eqref{e5} that $g_\lambda(\beta-1+\alpha)\in\{\beta,\beta-1+\alpha\}$. \pfk Let us now show that the condition in Theorem~\ref{t} is sufficient. Thus from now on, until the end of the present section we assume that for $(u_n)_{n\in\Z}$, $\alpha,\beta$ satisfying~\eqref{ZP} there exists a quadratic unit $\lambda$ with conjugate $\lambda'\in(0,1)$ such that $\lambda\Z[\alpha']=\Z[\alpha']$ and $g_\lambda\bigl(\{\beta,\beta-1+\alpha\}\bigr)\subset\{\beta,\beta-1+\alpha\}$. First we introduce an indicator of how many iterations of the function $f$ are necessary to get from a point $x\in\lambda'(\beta-1,\beta]$ back to this interval. Formally, for an $x\in\lambda'(\beta-1,\beta]$ we let \begin{equation}\label{i} {\rm rt}(x):=\min\{i\in\N \mid f^{i}(x)\in\lambda'(\beta-1,\beta]\}. \end{equation} The mapping which assigns to $x\in\lambda'(\beta-1,\beta]$ the image $f^{{\rm rt}(x)}(x)\in\lambda'(\beta-1,\beta]$ is in symbolic dynamics known as the first return map. The assignment $x\mapsto {\rm rt}(x)$ is called return time. The fact that this mapping is well defined follows from Corollary~\ref{kvak}. As a consequence of Corollary~\ref{kvak} and Remark~\ref{miau} the function ${\rm rt}(x)$ is piece-wise constant. The following observation about the relation between ${\rm rt}(x)$ and ${\rm ind}(x)$ will be useful. \begin{obs}\label{o} For all $x\in\lambda'(\beta-1,\beta]$ and all $j\in\{0,1,\dots,{\rm rt}(x)-1\}$, $$ {\rm ind}\bigl(f^{j}(x)\bigr)=j\,. $$ \end{obs} We are now in position to complete the proof of Theorem~\ref{t} by showing the sufficiency of the condition. \begin{prop}\label{p:suf} Let $(u_n)_{n\in\Z}$, $\alpha,\beta$ satisfy conditions~\eqref{ZP}. Let $\lambda>1$ be a quadratic unit with conjugate $\lambda'\in(0,1)$ such that $\lambda\Z[\alpha']=\Z[\alpha']$ and $$ g_\lambda\bigl(\{\beta,\beta-1+\alpha\}\bigr) \subset \{\beta,\beta-1+\alpha\}\,. $$ Then $(u_n)_{n\in\Z}$ is invariant under a non-trivial substitution. \end{prop} \pf We show that there exists a substitution with the factor $\lambda$, under which the Sturmian word $(u_n)_{n\in\Z}$ is invariant. From Proposition~\ref{haf} it is clear that the geometric representation $\Sigma_{\alpha,\beta}=\{t_n\mid n\in\Z\}$ of the word $(u_n)_{n\in\Z}$ is selfsimilar with the selfsimilarity factor $\lambda$. According to Remark~\ref{pozn:posledni}, for existence of a substitution with the factor $\lambda$ under which $(u_n)_{n\in\Z}$ is invariant, it suffices to prove that for every $n\in\Z$ such that $u_n=0$, the segments of the set $\Sigma_{\alpha,\beta}$ between points $\lambda t_n$ and $\lambda t_{n+1}$ are the same, and for every $n\in\Z$ such that $u_n=1$, the segments between points $\lambda t_n$ and $\lambda t_{n+1}$ are the same. Let $n_0\in\Z$ be such that $u_{n_0}=0$, i.e. $t_{n_0+1}-t_{n_0}=S=-\alpha'$. Let us denote by $p$ and $q$ the number of distances $S$ and $L$ respectively in the segment of $\Sigma_{\alpha,\beta}$ between points $\lambda t_{n_0}$ and $\lambda t_{n_0+1}$. As a consequence of Corollary~\ref{kvak} and Remark~\ref{miau} it holds that ${\rm rt}(\lambda' t'_{n_0})=p+q$ and $\lambda(t_{n_0+1}-t_{n_0})=-\lambda\alpha'=p(-\alpha')+q(1-\alpha')$. Since $-\alpha'$ and $1-\alpha'$ are linearly independent over $\Q$, the expression of the number $-\lambda\alpha'$ in the base $\{-\alpha',1-\alpha'\}$ is unique. Since $\lambda(t_{n+1}-t_n)=-\lambda\alpha'$ for all $n$ such that $u_n=0$, we have shown that the number of distances $S$, $L$ between points $\lambda t_{n}$ and $\lambda t_{n+1}$ are constantly equal to $p$, $q$ respectively for all $n$ such that $u_n=0$. We need to show that the ordering of these distances $S$ and $L$ between points $\lambda t_{n}$ and $\lambda t_{n+1}$ is constant. This ordering determines the substitution word for the letter $0$. Since ${\rm rt}(\lambda't'_n)$ is equal to the number of distances between points $\lambda t_{n}$ and $\lambda t_{n+1}$, we have ${\rm rt}(x)=p+q$ for all $x\in\lambda'\Omega_S$. Let us denote this constant by $j_S$, i.e. $$ j_S:={\rm rt}(x) \ \hbox{ for some }\ x\in\lambda'\Omega_S\,. $$ In order to show that the ordering of the distances $S$ and $L$ between points $\lambda t_{n}$ and $\lambda t_{n+1}$ is constant, it suffices to prove that \begin{equation}\label{Z} \hbox{for all }j\in\{0,1,\dots,j_S-1\}\qquad\hbox{ either }\quad f^{j}(\lambda'\Omega_S)\subset \Omega_S\quad\hbox{ or }\quad f^{j}(\lambda'\Omega_S)\subset \Omega_L\,. \end{equation} For contradiction, take the minimal index $j\leq j_S-1$ such that $f^{j}(\lambda'\Omega_S)\not\subset\Omega_S$ and $f^{j}(\lambda'\Omega_S)\not\subset\Omega_L$. Then $f^{j}(\lambda'\Omega_S)$ is an interval and its interior contains the discontinuity point $\beta-1+\alpha$. This means that there exists an $x\in\lambda'(\beta-1+\alpha,\beta)= (\lambda'\Omega_S)^{\circ}$ such that $f^{j}(x) = \beta-1+\alpha$. Therefore $f^{-j}(\beta-1+\alpha) =x\in \lambda'(\beta-1+\alpha,\beta)$. Since $j1$ whose conjugate $\lambda'\in(0,1)$ satisfies $\lambda'\Z[\alpha]=\Z[\alpha]$ (cf. Definition~\ref{d:g}). Therefore $g_\lambda$ has $\frac1{q}\Z[\alpha]\cap(\beta-1,\beta]$ as an invariant subset. Let us divide the set $\frac1{q}\Z[\alpha]$ into a disjoint union of subsets - classes of the following equivalence. \begin{de} Let $q\in\N$. We define an equivalence relation on $\frac1{q}\Z[\alpha]$ by $$ x\sim_q y \qquad\iff\qquad x-y\in\Z[\alpha]\qquad\hbox{ for }\ x,y\in\frac1{q}\Z[\alpha]. $$ \end{de} It is obvious that the equivalence classes of $\sim_q$ are of the form $$ T_{ij}:=\frac{i+j\alpha}{q} + \Z[\alpha]\,,\qquad i,j\in\{0,1,\dots,q-1\}\,, $$ and thus their number is $q^2$. Recall that $f$ acts as translation by $1-\alpha$ or $\alpha$. Therefore for every equivalence class $T_{ij}$, the set $T_{ij}\cap(\beta-1,\beta]$ is invariant under $f$. However, since the definition of $g_\lambda$ uses except the function $f$ also multiplication by the factor $\lambda'$, the set $T_{ij}\cap(\beta-1,\beta]$ is generally not invariant under $g_\lambda$. In order to determine for which $\lambda$ the set $T_{ij}\cap(\beta-1,\beta]$ is invariant under $g_\lambda$, it suffices to study the conditions, under which the class $T_{ij}$ is closed under multiplication by $\lambda'$. \begin{prop}\label{p:tridy} Let $\alpha$ satisfy~\eqref{ZP}, let $\gamma\in\R$ such that $\gamma\Z[\alpha]=\Z[\alpha]$ and let $q\in\N$. Then there exists an integer $k\in\N$ such that $\gamma^kT_{ij}=T_{ij}$ for every equivalence class $T_{ij}$ of $\sim_q$. \end{prop} \pf First we show that the mapping $\psi(T_{ij}):=\gamma T_{ij}$ is a well defined map on the set of equivalence classes. For arbitrary $i,j\in\{0,1,\dots,q-1\}$ we have $\gamma\frac{i+j\alpha}{q}\subset\frac1{q}\Z[\alpha]$ and therefore there exist $l,m\in\{0,1,\dots,q-1\}$ and a $z\in\Z[\alpha]$ such that $\gamma\frac{i+j\alpha}{q}=\frac{l+m\alpha}{q}+z$. For $\psi(T_{ij})$ we have $$ \psi(T_{ij})=\gamma \left(\frac{i+j\alpha}{q}+\Z[\alpha]\right) = \frac{l+m\alpha}{q}+z+\Z[\alpha] = T_{lm}\,. $$ Now let us show that the map $\psi$ is injective. For that it suffices to show \begin{equation}\label{H} \gamma \frac{i_1+j_1\alpha}{q} - \gamma \frac{i_2+j_2\alpha}{q}\in\Z[\alpha] \qquad\iff\qquad (i_1,j_1)=(i_2,j_2)\,, \end{equation} for all $i_1, j_1, i_2, j_2\in\{0,1,\dots,q-1\}$. A simple manipulation of the left hand side of~\eqref{H} leads us to $$ \frac{i_1-i_2+(j_1-j_2)\alpha}{q} \in \frac{1}{\gamma}\Z[\alpha] = \Z[\alpha]\,, $$ which implies that $q$ divides $i_1-i_2$ and $j_1-j_2$. This is possible only if $i_1=i_2$ and $j_1=j_2$. The mapping $\psi$ is therefore injective and hence a permutation on the set of $q^2$ classes $T_{ij}$, $i,j\in\{0,1,\dots,q-1\}$. Necessarily there exists an exponent $k$ so that $\psi^k$ is the identity, i.e. $\psi^k(T_{ij}) = \gamma^kT_{ij} = T_{ij}$, which completes the proof. \pfk For $\beta$ of the form $\beta=\frac{a+b\alpha}{q}$ the numbers $\beta$ and $\beta-1+\alpha$ belong to the same equivalence class $T$. Thus according to Remark~\ref{r:mocnina} and Proposition~\ref{p:tridy} we may consider without loss of generality the quadratic unit $\lambda$ such that $\lambda'T=T$, and study the fixed points of the function $g_\lambda$ on its invariant subset $(\beta-1,\beta]\cap T$. In fact, in the proof of the main result, we need only the class $T$ which contains $\beta$ and $\beta-1+\alpha$ (cf. proof of Corollary~\ref{c}). However, we prove the following statements for arbitrary class $T_{ij}$. Let us study the image of the set $(\beta-1,\beta]\cap T_{ij}$ under the Galois automorphism. Then $$ \begin{aligned} \Bigl((\beta-1,\beta]\cap T_{ij}\Bigr)' &= \Bigl\{y' \Bigm|\, y\in T_{ij}\cap(\beta-1,\beta]\Bigr\} =\\[2mm] &=\left\{\frac{i+j\alpha'}{q}+z' \biggm| z\in \Z[\alpha]\cap \Bigl(\beta-1-\frac{i+j\alpha}{q},\beta-\frac{i+j\alpha}{q}\Bigr]\right\} =\\[2mm] &=\ \frac{i+j\alpha'}{q} \ + \ \Sigma_\alpha\left(\Bigl(\beta-1-\frac{i+j\alpha}{q},\beta-\frac{i+j\alpha}{q}\Bigr]\right)\,. \end{aligned} $$ This means that $\bigl((\beta-1,\beta]\cap T_{ij}\bigr)'$ is the geometric representation of the Sturmian word of slope $\alpha$, intercept $\beta-\frac1{q}(i+j\alpha)$, translated by $\frac{1}{q}(i+j\alpha')$. Therefore the set $\bigl((\beta-1,\beta]\cap T_{ij}\bigr)'$ is a discrete set where the distances of adjacent elements take values $-\alpha'$, $1-\alpha'$. Then there exists a strictly increasing sequence $(s_n)_{n\in\Z}$ such that $$ \bigl((\beta-1,\beta]\cap T_{ij}\bigr)' = \{s_n\mid n\in\Z\}\qquad\hbox{ and }\qquad f(s'_n)=s'_{n+1} \quad\hbox{ for every } n\in\Z\,. $$ Thus the sequence $(s'_n)_{n\in\Z}$ is an orbit under the function $f$ of a point in the interval $(\beta-1,\beta]$. If $T_{ij}=T_{00}=\Z[\alpha]$, then $\{s'_n\mid n\in\Z\}= \{t'_n\mid n\in\Z\}$ is the orbit of 0. The sequence $(s_n)_{n\in\Z}$ for a class $T_{ij}\neq \Z[\alpha]$ is illustrated on Figure~\ref{f:s}. \begin{figure}[hbt]\begin{center} \setlength{\unitlength}{0.5mm} \begin{picture}(270,67) \put(-3,20){\line(1,0){270}} \put(91,8){\line(0,1){45}} \put(89,0){0} \put(21,34){$\overbrace{\hspace*{4.05cm}}$} \put(161,34){$\overbrace{\hspace*{4.05cm}}$} \put(120,34){$\overbrace{\hspace*{1.2cm}}$} \qbezier(201.5,39)(172,81)(105,31) \qbezier(132,39)(110,80)(96,32) \put(116,60){$g_{{}_\lambda}$} \put(173,60){$g_{{}_\lambda}$} \put(72.5,59){$g_{{}_\lambda}$} \qbezier(61.5,39)(70,80)(79,32) %\put(76.5,71){\begin{turn}{20}\mbox{\tiny $\blacktriangleleft$}\end{turn}} %\put(93.5,71){\begin{turn}{20}\mbox{\tiny $\blacktriangleright$}\end{turn}} \drawline(105,31)(106.5,33.5) \drawline(105,31)(107.7,31.7) \drawline(77.7,33.7)(79.2,31.3) \drawline(80.0,34.0)(79.2,31.3) \drawline(95.8,34.1)(96,31.3) \drawline(98,33.5)(96,31.3) %\linethickness{0.7pt} \put(4,18){\line(0,1){4}} \put(0,26){\small $s_{\!{}_{-\!3}}$} \put(21,20){\circle*{3}} \put(17,26){\small $s_{\!{}_{-\!2}}$} \put(17,10){\small $\lambda s_{{}_{2}}$} \put(38,18){\line(0,1){4}} \put(34,26){\small $s_{\!{}_{-\!1}}$} \put(45,18){\line(0,1){4}} \put(43,26){\small $s_{{}_{0}}$} \put(62,18){\line(0,1){4}} \put(60,26){\small $s_{{}_{1}}$} \put(79,18){\line(0,1){4}} \put(77,26){\small $s_{{}_{2}}$} \put(96,18){\line(0,1){4}} \put(93,26){\small $s_{{}_{3}}$} \put(103,18){\line(0,1){4}} \put(101,26){\small $s_{{}_{4}}$} \put(120,20){\circle*{3}} \put(118,26){\small $s_{{}_{5}}$} \put(118,10){\small $\lambda s_{{}_{3}}$} \put(137,18){\line(0,1){4}} \put(134,26){\small $s_{{}_{6}}$} \put(144,18){\line(0,1){4}} \put(142,26){\small $s_{{}_{7}}$} \put(161,20){\circle*{3}} \put(159,26){\small $s_{{}_{8}}$} \put(159,10){\small $\lambda s_{{}_{4}}$} \put(178,18){\line(0,1){4}} \put(175,26){\small $s_{{}_{9}}$} \put(185,18){\line(0,1){4}} \put(182,26){\small $s_{{}_{10}}$} \put(202,18){\line(0,1){4}} \put(199,26){\small $s_{{}_{11}}$} \put(219,18){\line(0,1){4}} \put(216,26){\small $s_{{}_{12}}$} \put(236,18){\line(0,1){4}} \put(231,26){\small $s_{{}_{13}}$} \put(243,18){\line(0,1){4}} \put(241,26){\small $s_{{}_{14}}$} \put(260,20){\circle*{3}} \put(257,26){\small $s_{{}_{15}}$} \put(257,10){\small $\lambda s_{{}_{5}}$} \end{picture} \caption{Action of the mappings ${\rm ind}(x):(\beta-1,\beta]\to\N_0$ and $g_\lambda:(\beta-1,\beta]\to(\beta-1,\beta]$ on the Galois image of points of $(\beta-1,\beta]\cap T_{ij}$.} \label{f:s} \end{center}\end{figure} Bold points represent elements of the set $\lambda\{s_n\mid n\in\Z\}\subset\{s_n\mid n\in\Z\}$. They are important for determination of the value ${\rm ind}(s'_{m})$ for $m\in\Z$. In fact, ${\rm ind}(s'_{m})$ is the number of steps to the first left neighbour of $s_m$ which belongs to the set $\lambda\{s_n\mid n\in\Z\}$. For example, $$ {\rm ind}(s'_3)=5\,,\qquad {\rm ind}(s'_7)=2\,,\qquad {\rm ind}(s'_8)=0\,. $$ If we divide the first left neighbour of $s_m$ in $\lambda\{s_n\mid n\in\Z\}$ by the factor $\lambda$, we obtain the Galois conjugate of the value $g_\lambda(s'_m)$. Clearly, several points may have the same image under the mapping $g_\lambda$. Such points are marked on Figure~\ref{f:s} by braces. For example, we have $$ \begin{array}{ll} &g_\lambda(s'_{-2})=g_\lambda(s'_{-1})=g_\lambda(s'_{0})=g_\lambda(s'_{1}) =g_\lambda(s'_{2})=g_\lambda(s'_{3})=g_\lambda(s'_{4})=s'_2\,,\\ &g_\lambda(s'_5)=g_\lambda(s'_6)=g_\lambda(s'_7)=s'_3\,,\\ &g_\lambda(s'_8)=g_\lambda(s'_9)=g_\lambda(s'_{10})=g_\lambda(s'_{11}) =g_\lambda(s'_{12})=g_\lambda(s'_{13})=g_\lambda(s'_{14})=s'_4\,. \end{array} $$ With this in mind it is simple to describe all fixed points of the function $g_\lambda$. \begin{prop}\label{p:pevnebody} Let $\alpha,\beta$ satisfy~\eqref{ZP}, $\beta\in\frac1{q}\Z[\alpha]$, and let $\lambda>1$ be a quadratic unit with conjugate $\lambda'\in(0,1)$ such that all equivalences classes of $\sim_q$ are closed under multiplication by $\lambda'$. Let $(s_n)_{n\in\Z}$ be the strictly increasing sequence such that $\bigl((\beta-1,\beta]\cap T\bigr)' = \{s_n\mid n\in\Z\}$ for an equivalence class $T$. Then $s'_n$ is a fixed point of $g_\lambda$ if and only if $s_n\leq 0$ and $s_{n+1}\geq 0$. \end{prop} \pf Note that $$ g_\lambda(s'_n) = \frac1{\lambda'}f^{-{\rm ind}(s'_n)}(s'_n) = s'_n \qquad\iff\qquad f^{-{\rm ind}(s'_n)}(s'_n) = \lambda's'_n\,. $$ This means that $s'_n$ being a fixed point of $g_\lambda$ is equivalent to the fact that among the left neighbours of $s_n$, the point $\lambda s_n$ is the nearest one which has its Galois image in $\lambda'(\beta-1,\beta]\cap T$. This is characterized by the two inequalities \begin{eqnarray} \lambda s_n &\leq &s_n \label{hv}\\ s_n &< &\lambda s_{n+1}. \label{hvhv} \end{eqnarray} Since $\lambda>1$, the inequality~\eqref{hv} is equivalent with $s_n\leq 0$. Since $s_{n+1}$ is the nearest right neighbour of $s_n$, inequality~\eqref{hvhv} can be equivalently written as $s_{n+1}\leq\lambda s_{n+1}$, which implies $s_{n+1}\geq 0$. \pfk \begin{pozn}\label{pozn:heavy} Note that in Proposition~\ref{p:pevnebody}, the necessary and sufficient condition for $s_n$ to be a fixed point of the mapping $g_\lambda$ does not depend on $\lambda$. Therefore $s_n$ is either a fixed point of $g_\lambda$ for all $\lambda$ satisfying the assumptions of the proposition, or is not a fixed point of $g_\lambda$ for any $\lambda$. \end{pozn} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section*{\normalsize 7. Substitution invariant Sturmian words} \addtocounter{section}{+1} \addtocounter{lem}{-4} In this section we show that the necessary and sufficient condition of Theorem~\ref{t} is equivalent to the inequalities given in Theorem~\ref{t1}. At the end we explain how to construct a non-trivial substitution $\varphi$ under which a given Sturmian word satisfying the conditions of Theorem~\ref{t1} is invariant. A part of the construction requires to find for a given quadratic $\alpha$ a quadratic unit $\lambda$ such that $\lambda\Z[\alpha']=\Z[\alpha']$. Obviously, if $\Z[\alpha]$ is the ring of integers in $\Q(\alpha)$, then such $\lambda$ trivially exists. However, in general $\alpha$ is even not an algebraic integer and thus $\Z[\alpha]$ is not closed under multiplication. For completeness we prove the existence of the factor $\lambda$ in the following simple lemma. \begin{lem}\label{l} For every quadratic irrational $\alpha$ there exists a quadratic unit $\lambda>1$ such that $\lambda'\in(0,1)$ and $\lambda\Z[\alpha']=\Z[\alpha']$. \end{lem} \pf Let $\alpha$ satisfy the equation $A\alpha^2+B\alpha+C=0$, where $A,B,C\in\Z$, $D=B^2\!-4AC>0$ and $\sqrt{D}$ is irrational. For $\alpha$ and its conjugate $\alpha'$ we have $\alpha+\alpha'=-\frac{B}{A}$, $\alpha\alpha'=\frac{C}{A}$. First we find an algebraic unit $\gamma$ such that $\gamma\Z[\alpha]=\Z[\alpha]$. Let $x,y\in\Z$ be a non-trivial solution of the Pell equation $x^2-Dy^2=1$. Set $\gamma:=x+By+2Ay\alpha$. We have $$ \begin{array}{ccl} \gamma+\gamma'&=&2x+2By+2Ay(\alpha+\alpha') \ = \ 2x \ \in \ \Z\,,\\[2mm] \gamma\gamma'&=&(x+By)^2 + 2Ay(x+By)(\alpha+\alpha') + 4A^2y^2\alpha\alpha' = x^2-Dy^2 \ = \ 1\,, \end{array} $$ therefore $\gamma$ is an algebraic unit. Since $\gamma\in\Z[\alpha]$, for verifying the relation $\gamma\Z[\alpha]=\Z[\alpha]$ it suffices that $\gamma\alpha\in\Z[\alpha]$ and $\frac1{\gamma}\alpha\in\Z[\alpha]$. We have $$ \begin{array}{ccl} \gamma\alpha&=& (x+By)\alpha + 2Ay\alpha^2 = (x+By)\alpha +2Ay\left(-\frac{B}{A}\alpha - \frac{C}{A} \right) \ \in \ \Z[\alpha]\,,\\[2mm] \frac1\gamma\alpha&=&\gamma'\alpha= (x+By+2Ay\alpha')\alpha = (x+By)\alpha + 2Ay\frac{C}{A} \ \in\ \Z[\alpha]\,. \end{array} $$ The relation $\gamma\Z[\alpha]=\Z[\alpha]$, which we have just proven, is equivalent to $\gamma'\Z[\alpha']=\Z[\alpha']$. Since $\gamma$ is a unit, we have also $\gamma\Z[\alpha']=\Z[\alpha']$. Now at least one of the numbers $\gamma$, $\gamma'$, $-\gamma$, $-\gamma'$ is greater than $1$. We choose it for the desired quadratic unit $\lambda$. Clearly, since $\gamma$ was found so that $\gamma\gamma'=1$, we have $\lambda'\in(0,1)$. \pfk \begin{coro}\label{c} Let $(u_n)_{n\in\Z}$, $\alpha,\beta$ satisfy conditions~\eqref{ZP}, and let $0\neq\beta\in\Q(\alpha)$. Then $(u_n)_{n\in\Z}$ is invariant under a non-trivial substitution if and only if \begin{equation}\label{*} \alpha'\leq\beta'\leq 1-\alpha'\,. \end{equation} \end{coro} \pf Let $\beta\in\frac1{q}\Z[\alpha]$. Due to Lemma~\ref{l} and Proposition~\ref{p:tridy} there exists a quadratic unit $\lambda$ with conjugate $\lambda'\in(0,1)$ such that $\lambda' T_{ij}=T_{ij}$ for every equivalence class of $\sim_q$. (Note that the class of $\frac1{q}\Z[\alpha]$ which contains $0$ is $\Z[\alpha]$, therefore the latter condition implies $\lambda'\Z[\alpha]=\Z[\alpha]$.) According to Theorem~\ref{t} and to Remarks~\ref{pozn:achichouvej} and~\ref{pozn:heavy}, for invariance under substitution we have to show that inequality~\eqref{*} is equivalent to the fact that $\beta$ or $\beta-1+\alpha$ is a fixed point of the function $g_\lambda$. Let us denote by $T$ the equivalence class containing $\beta$ and $\beta-1+\alpha$, and by $(s_n)_{n\in\Z}$ the strictly increasing sequence such that $\bigl(T\cap(\beta-1,\beta]\bigr)'=\{s_n\mid n\in\Z\}$. Since $f(\beta-1+\alpha)=\beta$, there exists an index $n_0\in\Z$ such that $\beta'-1+\alpha'=s_{n_0}$ and $\beta'=s_{n_0+1}$. According to Proposition~\ref{p:pevnebody} at least one of the points $s'_{n_0}$ or $s'_{n_0+1}$ is a fixed point of $g_\lambda$ if and only if \begin{equation}\label{**} s_{n_0}\leq 0 \qquad\hbox{ and }\qquad 0\leq s_{n_0+2} \,. \end{equation} We can substitute $s'_{n_0}=\beta-1+\alpha$ and $s'_{n_0+2}=f(s'_{n_0+1})=f(\beta)=\beta-\alpha$ into~\eqref{**} to obtain that $\beta$ or $\beta-1+\alpha$ is a fixed point of $g_\lambda$ if and only if $\beta'-1+\alpha'\leq 0$ and $\beta'-\alpha'\geq 0$, which completes the proof. \pfk \pf[Proof of Theorem~\ref{t1}] Necessity of condition~(i) ($\alpha$ being a Sturm number) has been derived in Proposition~\ref{brumbrum}. Corollary~\ref{c:1} says that (ii) ($\beta\in\Q(\alpha)$) is also a necessary condition. Therefore it suffices to show that for Sturmian words with irrational slope $\alpha\in(0,1)$ and intercept $\beta\in[0,1)$ satisfying (i) and (ii), invariance under a non-trivial substitution is equivalent to the condition (iii). Recall that Sturmian words $\underline{s}_{\alpha,\beta}$, $\underline{s}_{1-\alpha,\beta}$ and $\overline{s}_{\alpha,1-\beta}$ are either all substitution invariant, or none of them. Also condition (iii) is satisfied either for all pairs of parameters $(\alpha,\beta)$, $(\alpha,1-\beta)$ and $(1-\alpha,\beta)$, or for none of them. Therefore it suffices to consider the Sturmian word $(u_n)_{n\in\Z} = \bigl(\underline{s}_{\alpha,\beta}(n)\bigr)_{n\in\Z}$ with $\alpha'<0$. For such a slope $\alpha$ the condition (iii) has the form $$ \alpha'\leq \beta'\leq 1-\alpha'\,. $$ For $\beta=0$ the latter is satisfied automatically. As a consequence of Corollary~\ref{c}, for $\beta\neq 0$, the above inequality is equivalent with $(u_n)_{n\in\Z}$ being substitution invariant. \pfk %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section*{\normalsize 8. Construction of the substitution} The proof given in this paper is constructive. For a given Sturmian word $(u_n)_{n\in\Z}$ with slope $\alpha$ and intercept $\beta= \frac1q(a+b\alpha)$ that satisfies conditions (i)--(iii) of Theorem~\ref{t1} one can determine a non-trivial substitution $\varphi$ under which $(u_n)_{n\in\Z}$ is invariant. If a Sturmian word is invariant under a non-trivial substitution, then it is invariant under many substitutions with different factors. All substitution factors $\lambda$ are quadratic units with conjugate $\lambda'\in(-1,1)$ and satisfy $\lambda'\Z[\alpha]=\Z[\alpha]$. It is convenient to choose the substitution with the smallest substitution factor $\lambda_0$, because then the substitution words $\varphi(0)$, $\varphi(1)$ are short. From the proof presented in the paper it follows that the smallest quadratic unit $\lambda>1$ with conjugate $\lambda'\in(0,1)$, satisfying $\lambda'\Z[\alpha]=\Z[\alpha]$ and $\lambda'T=T$ for $T=\beta+\Z[\alpha']$, is either $\lambda=\lambda_0$ or $\lambda=\lambda_0^2$. Let us describe explicitly the algorithm for determining a substitution to a given Sturmian word. This algorithm is a consequence of the proof of Proposition~\ref{p:suf}. First we find, according to the construction in proof of Lemma~\ref{l}, a quadratic unit $\lambda>1$ with conjugate $\lambda'\in(0,1)$ which satisfies $\lambda'\Z[\alpha]=\Z[\alpha]$. Every power of $\lambda$ satisfies these conditions, therefore we can assume that the chosen factor $\lambda$ is such that $\lambda' T=T$ for the equivalence class $T$ of $\sim_q$, that contains $\beta$. If $\lambda$ satisfies all of the above conditions, then we define the substitution $\varphi:\{0,1\}\to\{0,1\}^*$ in the following way. Put $\varphi(0)=v_0\cdots v_{j_S-1}$, where $j_S={\rm rt}(\lambda'\beta)$ is the smallest positive index such that $f^{j_S}(\lambda'\beta)\in\lambda'(\beta-1,\beta]$, and let $\varphi(1)=w_0\cdots w_{j_L-1}$ where $j_L={\rm rt}\bigl(\lambda'(\beta-1+\alpha)\bigr)$ is the smallest positive index such that $f^{j_L}\bigl(\lambda'(\beta-1+\alpha)\bigr)\in\lambda'(\beta-1,\beta]$. Then we let $$ \begin{array}{lll} v_i:= &\left\{\begin{array}{ll} 0 &\qquad\hbox{ if } f^{i}\bigl(\lambda'\beta\bigr) \in\Omega_S\,, \\[1mm] 1 &\qquad\hbox{ if } f^{i}\bigl(\lambda'\beta\bigr) \in\Omega_L\,, \end{array}\right. &\hbox{ for } i\in\{0,1,\dots,j_S-1\}\,,\\[8mm] w_i:= &\left\{\begin{array}{ll} 0 &\hbox{ if } f^{i}\bigl(\lambda'(\beta-1+\alpha)\bigr) \in\Omega_S\,, \\[1mm] 1 &\hbox{ if } f^{i}\bigl(\lambda'(\beta-1+\alpha)\bigr) \in\Omega_L\,, \end{array}\right. &\hbox{ for } i\in\{0,1,\dots,j_L-1\}\,. \end{array} $$ Let us illustrate the construction of a substitution to a given Sturmian word on an example. \begin{ex} Let $\alpha=\frac1{\sqrt2}$. Such $\alpha$ is a quadratic number, solution of $2x^2-1=0$. Its algebraic conjugate is $\alpha'=-\frac1{\sqrt2}$. Since $\alpha\in(0,1)$ and $\alpha'<0$, $\alpha$ is a Sturm number. Let us first find a quadratic unit $\lambda>0$ with conjugate $\lambda'\in(0,1)$ such that $\lambda'\Z[\alpha]=\Z[\alpha]$. For that we use the constructive proof of Lemma~\ref{l}. Since the coefficients of the equation $Ax^2+Bx+C=2x^2-1=0$ of $\alpha$ are $A=2$, $B=0$, $C=-1$, we have the discriminant $D=B^2-4AC=8$. For a solution of the Pell equation $x^2-Dy^2=x^2-8y^2=1$ we can choose $x=3$, $y=1$. Then $\gamma=x+By+2Ay\alpha=3+4\alpha$. Since $\gamma>1$, we let $\lambda=\gamma=3+4\alpha$. In order that the Sturmian word $(u_n)_{n\in\Z}$ given by $$ u_n=\lfloor(n+1)\alpha+\beta\rfloor - \lfloor n\alpha+\beta\rfloor $$ be invariant under a substitution, we need to choose the intercept $\beta\in\Q(\sqrt2)$ so that $$ -\frac1{\sqrt{2}}=\alpha'\leq \beta' \leq 1-\alpha'=1+\frac1{\sqrt{2}}\,. $$ For simplicity, we consider the example of $\beta=\frac1q$, for some $q\in\N$, which clearly satisfies the condition. Now we have to take a power $\lambda^s$ of $\lambda$, such that the multiplication by ${\lambda'}^s$ preserves the equivalence classes $T_{ij}$ of $\sim_q$ in $\frac1q\Z[\alpha]$. It is not difficult to calculate that the multiplication of $T_{ij}$ by $\lambda'$ gives $\lambda'T_{ij}=T_{kl}$, where $$ k= 3i-2j \ {\rm mod}\, q\qquad \hbox{ and }\qquad l=-4i+3j \ {\rm mod}\, q\,. $$ Clearly for $q=2$ we have $\lambda'T_{ij}=T_{ij}$, whereas for $q=3$ we have to take the fourth power, i.e. ${\lambda'}^4T_{ij}=T_{ij}$. In order to illustrate the construction of a substitution, we let $\beta=\frac12$. We will use the function $f$ in our case defined as $$ f(x) = \left\{ \begin{array}{cccr} x+1-\alpha & \hbox{ if } & x\in\bigl(-\frac12\,,\,-\frac12+\frac1{\sqrt2}\bigr] &=: \ \Omega_L,\\[2mm] x-\alpha & \hbox{ if } & x\in\bigl(-\frac12+\frac1{\sqrt2}\,,\,\frac12\bigr] &=:\ \Omega_S. \end{array} \right. $$ We have to calculate iterations $f^i(\lambda'\beta)=f^{i}(\lambda'\frac12)$, $f^i\bigl(\lambda'(\beta-1+\alpha)\bigr)=f^i\bigl(\lambda'(-\frac12+\frac{1}{\sqrt2})\bigr)$ until the first return to the interval $\lambda'(\beta-1,\beta]$, $$ \begin{array}{rcccl} f^{0}(\lambda'\frac12)&=&{\frac32-2\alpha}&\in&\Omega_L\,,\\[2mm] f^{1}(\lambda'\frac12)&=&{\frac52-3\alpha}&\in&\Omega_S\,,\\[2mm] f^{2}(\lambda'\frac12)&=&{\frac52-4\alpha}&\in&\Omega_L\,,\\[2mm] f^{3}(\lambda'\frac12)&=&{\frac72-5\alpha}&\in&\lambda'\Omega\,, \end{array} \qquad\hbox{ thus } \ j_S=3 \ \hbox{ and }\ \varphi(0)=101\,. $$ Similarly, we have $$ \begin{array}{rclcl} f^{0}\bigl(\lambda'(-\frac12+\frac{1}{\sqrt2})\bigr)&=&-\frac72+5\alpha&\in&\Omega_L\,,\\[2mm] f^{1}\bigl(\lambda'(-\frac12+\frac{1}{\sqrt2})\bigr)&=&-\frac52+4\alpha&\in&\Omega_S\,,\\[2mm] f^{2}\bigl(\lambda'(-\frac12+\frac{1}{\sqrt2})\bigr)&=&-\frac52+3\alpha&\in&\Omega_L\,,\\[2mm] f^{3}\bigl(\lambda'(-\frac12+\frac{1}{\sqrt2})\bigr)&=&-\frac32+2\alpha&\in&\Omega_L\,,\\[2mm] f^{4}\bigl(\lambda'(-\frac12+\frac{1}{\sqrt2})\bigr)&=&-\frac12+\alpha&\in&\Omega_L\,,\\[2mm] f^{5}\bigl(\lambda'(-\frac12+\frac{1}{\sqrt2})\bigr)&=&\ \ \frac12&\in&\Omega_S\,,\\[2mm] f^{6}\bigl(\lambda'(-\frac12+\frac{1}{\sqrt2})\bigr)&=&\ \ \frac12-\alpha&\in&\Omega_L\,,\\[2mm] f^{7}\bigl(\lambda'(-\frac12+\frac{1}{\sqrt2})\bigr)&=&\ \ \frac32-2\alpha&\in&\lambda'\Omega\,, \end{array} \qquad\hbox{ thus } \ j_L=7 \ \hbox{ and }\ \varphi(1)=1011101\,. $$ The infinite word $(u_n)_{n\in\Z}$ is a fixed point of the substitution $$ \varphi(0)=101\,,\qquad\varphi(1)=1011101\,. $$ Therefore $(u_n)_{n\in\Z}$ can be generated from the initial pair of letters $1|1$ by repeated application of $\varphi$, i.e. $$ \cdots u_{-2}u_{-1}|u_0u_{1}u_2\cdots \ =\ \lim_{n\to\infty}\varphi^n(1)|\varphi^n(1)\,. $$ The Sturmian word $(u_n)_{n\in\Z}$ is geometrically represented by the set $$ \Sigma_{\alpha,\beta}=\bigl\{x\in\Z[\alpha'] \,\bigm|\, x'\in(-\tfrac12,\tfrac12]\,\bigr\}\,. $$ Since the boundary point $\frac12$ of the interval is not an element of $\Z[\alpha]$, the set $\Sigma_{\alpha,\beta}$ is symmetric with respect to the origin. This corresponds to the fact that the substitution words $\varphi(0)$ and $\varphi(1)$ are palindromes. \end{ex} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section*{Acknowledgements} We acknowledge financial support of Czech Science Foundation GA \v CR 201/05/0169. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{thebibliography}{9} \footnotesize \bibitem{adam} B. Adamczewski, {\it Codages de rotations et ph\'enom\`enes d'autosimilarit\'e,} J. Th\'eor. Nombres Bordeaux {\bf 14} (2002), 351--386. \bibitem{allauzen} C. Allauzen, {\it Simple characterization of Sturm numbers}, J. Th\'eor. Nombres Bordeaux {\bf 10} (1998), 237--241. \bibitem{seebold} J. Berstel, P. S\'e\'ebold, {\it Morphismes de Sturm,} Bull. Belg. Math. Soc. {\bf 1} (1994), 175--189. \bibitem{berstel2} J. Berstel, {\it Recent results on extensions of Sturmian words,} Internat. J. Algebra Comput. {\bf 12} (2002), 371--385. \bibitem{berthe} V. Berth\'e, H. Ei, S. Ito, H. Rao, {\it Invertible substitutions and Sturmian words: An application of Rauzy fractals,} preprint (2003) \bibitem{berthe2} V. Berth\'e, C. Holton, L. Q. Zamboni, {\it Initial powers of Sturmian sequences,} preprint (2003) \bibitem{brown} T. C. Brown, {\it A characterization of the quadratic irrationals,} Canad. Math. Bull. {\bf 34} (1991), 36--41. \bibitem{crisp} D. Crisp, W. Moran, A. Pollington, P. Shiue, {\it Substitution invariant cutting sequences,} J. Th\'eor. Nombres Bordeaux {\bf 5} (1993), 123-137. \bibitem{coven} E.M. Coven, G.A. Hedlund, {\it Sequences with minimal block growth,} Math. Systems Theory {\bf 7} (1973), 138--153. \bibitem{palin} X. Droubay, G. Pirillo, {\it Palindromes and Sturmian words,} Theoret. Comput. Sci. {\bf 223} (1999), 73--85. \bibitem{kombi} L.S. Guimond, Z. Mas\'akov\'a, E. Pelantov\'a, {\it Combinatorial properties of infinite words associated with cut-and-project sequences,} J. Th\'eor. Nombres Bordeaux {\bf 15} (2003), pp. 697-725. \bibitem{ito} S. Ito, S. Yasutomi, {\it On continued fractions, substitutions and characteristic sequences $[nx+y]-[(n-1)x+y]$,} Japan. J. Math. New Ser. {\bf 16} (1990), 287--306. \bibitem{komatsu} T. Komatsu, A. J. van der Poorten, {\it Substitution invariant Beatty sequences,} Japan. J. Math. New Ser. {\bf 22} (1996), 349--354 \bibitem{lothaire} M. Lothaire, {\it Algebraic combinatorics on words}, Cambridge University Press (2002). %\bibitem{lunpl} W.~F.~Lunnon, P.~A.~B.~Pleasants, {\it %Characterization of two-distance sequences,} J. Austral. Math. Soc. (Series A) {\bf 53} %(1992), 198--218. \bibitem{meyer} Y. Meyer, {\it Quasicrystals, Diophantine approximation and algebraic numbers,} Beyond quasicrystals (Les Houches, 1994), 3--16, Springer, Berlin, 1995. \bibitem{hedlund} M. Morse, G. A. Hedlund, {\it Symbolic dynamics II. Sturmian trajectories,} Amer. J. Math. {\bf 62} (1940) 1--42. \bibitem{parvaix} B. Parvaix, {\it Propri\'et\'es d'invariance des mots sturmiens,} J. Th\'eor. Nombres Bordeaux {\bf 9} (1997), 351--369. \bibitem{parvaix2} B. Parvaix, {\it Substitution invariant Sturmian bisequences,} J. Th\'eor. Nombres Bordeaux {\bf 11} (1999), 201--210. \bibitem{rauzy} G. Rauzy, {\it \'Echanges d'intervalles et transformations induites,} Acta Arith. {\bf 34} (1979), 315--328. \bibitem{vuil} L. Vuillon, {\it A characterization of Sturmian words by return words,} European J. Combin. {\bf 22} (2001), 263--275. \bibitem{yasutomi} S. Yasutomi, {\it On Sturmian sequences which are invariant under some substitutions,} Number theory and its applications (Kyoto, 1997), 347--373, Dev. Math. {\bf 2}, Kluwer Acad. Publ., Dordrecht, 1999. \end{thebibliography} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{document} Let $(u_n)_{n\in\Z}$, $\alpha,\beta$ satisfy~\eqref{ZP}, and moreover $0\neq\beta\in\frac1{q}\Z[\alpha]$. The following three statements are equivalent: \begin{itemize} \item The sequence $(u_n)_{n\in\Z}$ is invariant under a non-trivial substitution. \item There exists a quadratic unit $\lambda>1$, with conjugate $\lambda'\in(0,1)$ such that all classes of equivalence $\sim_q$ are closed under multiplication by $\lambda'$, and such that the sequence $(u_n)_{n\in\Z}$ is invariant under a non-trivial substitution whose incidence matrix has $\lambda$ as its dominant eigenvalue. \item For every quadratic unit $\lambda>1$, with conjugate $\lambda'\in(0,1)$ such that all classes of equivalence $\sim_q$ are closed under multiplication by $\lambda'$, there exists a non-trivial substitution whose incidence matrix has $\lambda$ as its dominant eigenvalue, such that the sequence $(u_n)_{n\in\Z}$ is its fixed point. \end{itemize}