<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\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}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

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

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

\newcommand{\BbR}{\mathbb{R}}
\newcommand{\BbC}{\mathbb{C}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\cA}{\mathcal{A}}
\newcommand{\N}{\mathcal{N}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\W}{\mathcal{W}}
\newcommand{\Wa}{\tta\mathcal{W}}
\newcommand{\Wb}{\ttb\mathcal{W}}
\newcommand{\cM}{\mathcal{M}}

\newcommand{\B}{\mathbb}
\newcommand{\C}{\mathcal}
\newcommand{\F}{\mathfrak}

\newcommand{\ga}{\alpha}
\newcommand{\gb}{\beta}
\newcommand{\gd}{\delta}
\newcommand{\eps}{\varepsilon}
\newcommand{\gf}{\varphi}
\newcommand{\gi}{\iota}
\newcommand{\gk}{\kappa}
\newcommand{\gl}{\lambda}
\newcommand{\go}{\omega}
\newcommand{\gq}{\vartheta}
\newcommand{\gr}{\mu}
\newcommand{\gs}{\sigma}
\newcommand{\gu}{\upsilon}
\newcommand{\gv}{\vartheta}
\newcommand{\gz}{\zeta}
\newcommand{\ueps}{\underline{\eps}}
\newcommand{\tta}{{\tt a}}
\newcommand{\ttb}{{\tt b}}
\newcommand{\ttA}{{\tt A}}
\newcommand{\ttB}{{\tt B}}
\newcommand{\ttw}{{\tt w}}
\newcommand{\tts}{{\tt s}}
\newcommand{\ttf}{{\tt f}}
\newcommand{\ttl}{{\tt l}}
\newcommand{\per}{\mbox{Per}}
\newcommand{\lcm}{\mbox{lcm}}

\newcommand{\gD}{\Delta}
\newcommand{\gF}{\Phi}
\newcommand{\gG}{\Gamma}
\newcommand{\gL}{\Lambda}
\newcommand{\gO}{\Omega}
\newcommand{\gQ}{\Theta}
\newcommand{\gS}{\Sigma}
\newcommand{\gU}{\Upsilon}

\newcommand{\tbf}{\textbf}
\newcommand{\tit}{\textit}
\newcommand{\tsc}{\textsc}

\newcommand{\bigast}{\DOTSB\bigop{\ast}}
\DeclareMathOperator{\adj}{adj}
\DeclareMathOperator{\spn}{span}
\DeclareMathOperator{\tr}{Tr}
\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\E}{End}
\DeclareMathOperator{\dens}{\mbox{dens}}
\DeclareMathOperator{\freq}{\mbox{freq}}
\newcommand{\trdeg}{\mathrm{trdeg}}
\newcommand{\todo}[1]{\begin{sc} #1 \end{sc}}

\newcommand{\m}[1]{\left(\begin{matrix} #1 \end{matrix}\right)}             
\newcommand{\s}[1]{\left(\begin{smallmatrix} #1 \end{smallmatrix}\right)}   
\newcommand{\exend}{\hfill $\Diamond$}

\makeatletter
  \def\vhrulefill#1{\leavevmode\leaders\hrule\@height#1\hfill \kern\z@}
\makeatother

\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 Relative Position in Binary Substitutions
}
\vskip 1cm
Michael Coons\\
Department of Mathematics and Statistics\\
California State University, Chico\\
Chico, CA 95926\\ 
USA \\
\href{mailto:mjcoons@csuchico.edu}{\tt mjcoons@csuchico.edu}\\
\ \\
Christopher Ramsey\\
Department of Mathematics and Statistics\\
MacEwan University\\
Edmonton, AB T5J 4S2\\ 
Canada\\
\href{mailto:ramseyc5@macewan.ca}{\tt ramseyc5@macewan.ca}\\
\ \\
Nicolae Strungaru\\
Department of Mathematics and Statistics\\
MacEwan University\\
Edmonton, AB T5J 4S2\\ 
Canada\\
Institute of Mathematics ``Simon Stoilow''\\
Bucharest 010702\\ 
Romania\\
\href{mailto:strungarun@macewan.ca}{\tt strungarun@macewan.ca}

\end{center}

\vskip .2 in
\begin{abstract}
Given an infinite word on a finite alphabet, an immediate question arises:\ can we understand the frequency of letters in that word? For words that are the fixed points of substitutions, the answer to this question is often `yes'---the details and methods of these answers have been well-documented. In this paper, toward a better understanding of the fixed points of binary substitutions, we delve deeper by investigating, in fine detail, the position of letters by defining various position functions and proving results about their behavior. Our analysis reveals new information about the Fibonacci substitution and the extended Pisa family of substitutions, as well as a new characterization of the Thue-Morse sequence.
\end{abstract}


\section{Introduction}


Sequences over finite alphabets are pervasive in mathematics. Questions surrounding them have inspired the development of whole areas of mathematics---combinatorics on words, analytic number theory, and symbolic dynamics, to name a few. For specific examples one need look no further than the prime number theorem and the Riemann hypothesis; both can be stated in terms of the Liouville $\lambda$-function---a binary sequence over the alphabet $\{-1,1\}$, which indicates the parity of the number of prime divisors of an integer. Such questions often concern the frequency of the values (e.g., prime number theorem) or the variance from that frequency (e.g., Riemann hypothesis). In this paper, our primary objects of concern are substitution sequences, and, in particular, those acting on binary (two-letter) alphabets. By \emph{binary substitution}, we mean a map $\mu$ from binary words to binary words that is a homomorphism---the natural operation on words being concatenation. Being a homomorphism, a substitution is defined by how it acts on the binary alphabet. A ubiquitous example \cite{AS1999} is the Thue-Morse substitution $\mu_{\rm TM}$, which is defined by
\begin{displaymath}
\mu_{\rm TM}:
\begin{cases}
    \tta \to \tta\ttb \\
    \ttb \to \ttb\tta\,.
\end{cases}
\end{displaymath} The one-sided infinite word that is the unique fixed point of this substitution that starts with the seed $\tta$,
\[
{\bf t}=\lim_{n\to\infty}\mu_{\rm TM}^n(\tta)=\tta\ttb\ttb\tta\ttb\tta\tta\ttb\ttb\tta\tta\ttb\tta\ttb\ttb\tta\ttb\tta\tta\ttb\tta\ttb\ttb\tta\tta\ttb\ttb\tta\ttb\tta\tta\ttb\cdots,
\]
is often viewed as an infinite sequence (the so-called \emph{Thue-Morse sequence} or \emph{Prouhet-Thue-Morse sequence}), and is a paradigmatic example in several areas---most notably, number theory, dynamical systems, and theoretical computer science, where it is a canonical example of a sequence that is output by a deterministic finite automaton; see Allouche and Shallit~\cite{ASbook}.

A binary substitution is a robust object. Along with it, comes an incidence matrix, which is nonnegative, and from that, one can often obtain information about the frequency of the letters in a fixed point, hence the questions of the frequency of values can often be easily answered \cite{M1975,M1976}. Also, the questions concerning more nuanced behavior (speed of convergence) of the frequency are known for large classes of substitution sequences, in particular, for those of constant length; see, e.g., Delange \cite{D1975} and Dumas \cite{D2013}. There is a plethora of literature in the area, and we would be remiss if we did not mention some of the more important results in the area including Cobham's result~\cite{Cobham} that if the frequency of a letter in a constant-length substitution sequence exists that value is rational, Peter's necessary and sufficient criterion \cite{Peter} for the existence of such a frequency, Saari's generalization \cite{Saari} of Peter's result to more general substitutions, and Bell's further generalization \cite{B2008} that ensures the logarithmic frequency of words in general substitutions exists. One of our personal favorites is an under-appreciated result of Allouche, Mend\`es~France, and Peyri\`ere \cite{AMP} on Dirichlet series associated with constant-length substitutions, which can be applied to give a wealth of information. 

The position of letters in constant-length substitutions was studied by Cobham \cite{Cobham} and Minsky and Papert \cite{MP1966}, who gave results concerning asymptotics of gaps. Here, toward a better understanding of the fixed points of binary substitutions, we investigate, in fine detail, the position of letters by defining various position functions and proving results about their behavior.  

We accomplish this as follows. In Section \ref{sec:prelim}, we define the (relative) position functions and focus on preliminary results concerning these functions and their interaction with various operators on words. The two main results of Section \ref{sec:prelim} are that a relative position function uniquely determines an infinite binary word (Lemma \ref{lemma2}) and that any increasing function is the relative position function of some infinite binary word (Lemma \ref{lem:2.7}). In Section \ref{sec:meanv}, we study the relationship between our position functions and the standard letter frequency. Section \ref{sect:fib} contains an extended study of the Fibonacci substitution and the extended Pisa family of substitutions; in particular, our main result in this section is a characterization of the Fibonacci word in terms of its position functions (Theorems \ref{thm-fib} and ~\ref{fib-uni}). In Section \ref{sec:linear}, we characterize words that give rise to exact and asymptotically linear relative position functions. We conclude this paper in Section \ref{sec:TM}, where we obtain a new characterization of the Thue-Morse sequence---it is the only sequence on $\{\pm1\}$ that is equal to its own relative position sequence.

\section{Preliminaries}\label{sec:prelim}

In this paper, we look (usually) at infinite one-sided binary words, whose elements we call \emph{letters} or \emph{bits}. That is, considering the alphabet $\Sigma=\{\tta,\ttb\}$ having bits $\tta$ and $\ttb$, we look at words
\[
\ttw=\ell_0 \ell_1 \ell_2 \cdots \ell_n \cdots
\]
where $\ell_n\in\Sigma$. We let $\Sigma^*$ denote the set of finite words over $\Sigma$, and let $\Sigma^{\omega}$ denote the set of infinite words over $\Sigma$. Further, set $\Sigma^{\infty}=\Sigma^*\cup\Sigma^\omega$. Here, for any finite word $w\in\Sigma^*$, $w\Sigma^\omega$ denotes the set of subwords of $\Sigma^{\omega}$ beginning with the word $w$, that is, having $w$ as a \emph{prefix}. For example, $\Sigma^\omega=\tta\Sigma^\omega\cup\ttb\Sigma^\omega$. Concatenation of words is written in the usual power notation; for example, $\tta^3=\tta\tta\tta$ and $(\tta\ttb)^2=\tta\ttb\tta\ttb$. We write $(\ell_0\ell_1\cdots\ell_n)^\omega$ to denote the infinite periodic word with periodic part $\ell_0\ell_1\cdots\ell_n$. The length of a word $\ttw$ is denoted by $|\ttw|$, and the number of $\tta$'s and $\ttb$'s occurring in $\ttw$ are denoted by $|\ttw|_\tta$ and $|\ttw|_\ttb$, respectively. So, $|\ttw|=|\ttw|_a+|\ttw|_\ttb$.

Throughout this paper, we assume that both letters $\tta$ and $\ttb$ appear infinitely many times in any infinite binary word ${\tt w}$, or equivalently that $\ttw$ is not eventually $1$-periodic. We separate out this special subset $\W\subset\Sigma^\omega$ with the notation
\[
\W :=\{ \ttw\in\Sigma^\omega : |\ttw|_\tta=\infty\ \mbox{and}\ |\ttw|_\ttb=\infty \} \,.
\]
We also use the analogous notation to the above to indicate words starting with a given prefix for this special subset; for example, $\W=\tta\W\cup\ttb\W$, where, for a finite word $w$, we write $w\W$ to indicate the subset of words of $\W$ having prefix $w$.

While the words we study, in general, are binary words, most of the examples we focus on are coming from substitutions---for this reason we prefer to use $\{\tta,\ttb\}$ as the alphabet instead of $\{0,1\}$. Here, we define a \emph{substitution} $\mu$ as a morphism on the set $\Sigma^{\infty}$; that is, given a (finite or infinite) word $\ttw=\ell_0 \ell_1 \ell_2 \cdots \ell_n \cdots$, we have $\mu(\ttw)=\mu(\ell_0)\mu( \ell_1)\mu( \ell_2) \cdots \mu(\ell_n) \cdots$. For each substitution, we define the \emph{incidence matrix} $M:=M_\mu$ to be the matrix whose $ij$-th entry is the number of letters $a_i$ in $\mu(a_j)$, where, in our binary case, we take $a_1=\tta$ and $a_2=\ttb$. We call a substitution $\mu$ \emph{primitive} provided $M_\mu$ is a primitive matrix.

This choice allows us to use the standard notation for level-$n$ super-tiles; that is, if $\sigma$ is a substitution on $\Sigma$, we set $\ttA_n:=\sigma^n(\tta)$ and $\ttB_n:=\sigma^n(\ttb)$.

Let us now recall the notions of codings and isomorphic words. Let $\ttw=w_0w_1\cdots$ and $\ttl=\ell_0\ell_1\cdots$ be words on alphabets $\Sigma$ and $\Sigma'$, and assume that the alphabets are \textit{reduced}, meaning
\[
\Sigma=\{ w_n : n \in \ZZ_{\geq 0} \} \quad\mbox{and}\quad \Sigma'=\{ \ell_n : n \in \ZZ_{\geq 0} \} \,.
\]
We say that $\ttl$ is a \textit{coding} of $\ttw$ if there exists a map, also called a \emph{coding}, $\sigma:\Sigma \to \Sigma'$ such that, for all $n \in \ZZ_{\geq 0}$ we have $\ell_n=\sigma(w_n)$. Here, since we are using binary alphabets, we use the shorthand $(\tta,\ttb)=(k,l)$ to denote the coding on the alphabet $\{\tta,\ttb\}$ with $k=\sigma(\tta)$ and $l=\sigma(\ttb)$. We say that $\ttw$ and $\ttl$ are \emph{isomorphic} if there exists such a mapping $\sigma$ that is a bijection.
It is easy to see that $\ttw$ and $\ttl$ are isomorphic if and only if each is a coding of the other.

Finally, given a sequence $(x_n)_{n \in \NN}$ that only takes finitely many values, we often abuse notation and think about it as being the word $
\ttw = x_1x_2\cdots x_n \cdots$. Note here that this introduces a shift in position, as $x_1$ is in position $0$.

With the above `stringology' firmly noted, we move on to the definition of functions that play important roles in what follows. Here, and below, $\NN$ denotes the set of positive integers, and $\ZZ_{\geq 0}$ denotes the set of non-negative integers, and $\CC$ denotes the set of complex numbers.

\begin{definition} Let $\ttw \in \W$. We define the \emph{position functions} $p_{\tta, \ttw}(n)$ and $p_{\ttb,\ttw}(n)$ as the position of the $n$-th occurrence of $\tta$ and $n$-th occurrence of $\ttb$ in $\ttw$, respectively.
Provided the context is clear, we use $p_\tta$ and $p_\ttb$ in place of $p_{\tta, \ttw}$ and $p_{\ttb,\ttw}$, respectively.
\end{definition}

In the context of constant-length substitutions, each of these position functions has been studied separately. In particular, Cobham \cite{Cobham} considered the difference $p_\tta(n+1)-p_\tta(n)$ and Mirsky and Papert \cite{MP1966} considered the ratio $p_\tta(n+1)/p_\tta(n)$. See also Allouche and Shallit \cite[Section 8.6]{ASbook}. Here, we consider a relationship between the position functions of different letters.

\begin{definition} Let $\ttw \in \W$. We define the \emph{relative position function} $r_\ttw(n)$ as
\[
r_\ttw(n):=p_{\ttb,\ttw}(n)-p_{\tta,\ttw}(n) \,.
\]
Provided the context is clear, we use $r$ in place of $r_\ttw$.
\end{definition}

\begin{definition}
For a sequence $s : \NN \to \CC$ , the \emph{difference sequence} $\Delta s:\NN \to \CC$ of $s$ is defined by
\[
\Delta s (n) := s(n+1)-s(n) \,.
\]
\end{definition}

Let $\ttw \in \W$. Note the following immediate consequences of the above definitions. Firstly, we have $r(n) \neq 0$ for each $n$. Secondly, the functions $p_\tta$ and $p_\ttb$ are strictly increasing. In particular, $\Delta p_\tta$ and $\Delta p_\ttb$ are positive sequences. Thirdly, the difference sequence $\Delta p_\tta(n)$ equals one plus the number of $\ttb$'s between the $n$-th and $(n+1)$-th $\tta$. This is sometimes called the \emph{sequence of $\ttb$-runs}. Similarly, the difference sequence $\Delta p_\ttb(n)$ equals one plus the number of $\tta$'s between the $n$-th and $(n+1)$-th $\ttb$. Finally, since both $\tta$ and $\ttb$ appear infinitely many times in $\ttw$, the sets
\[
  A =\{ p_\tta(n): n \in \NN \} \quad \mbox{and}\quad
  B =\{ p_\ttb(n): n \in \NN \} \,,
\]
partition $\ZZ_{\geq 0}$ into two infinite sets. Moreover, each such partition corresponds uniquely to the images of the position functions for a word $\ttw\in\W$. In particular, $\ttw$ can be recovered from $A$ or $B$.

With the above properties in hand, we now discuss which functions can be position functions or relative position functions. The following lemma is an immediate consequence of the definitions---since the proof is straightforward, we omit it.

\begin{lemma} Let $p :\NN \to \ZZ_{\geq 0}$. The following hold.
\begin{itemize}
  \item[(a)] There exists some $\ttw \in \Wa$ such that $p_\tta=p$ if and only if $p$ is strictly increasing, $p(1)=0$, and $\Delta p &gt;1$ infinitely often.
  \item[(b)] There exists some $\ttw \in \Wa$ such that $p_\ttb=p$ if and only if $p$ is strictly increasing, $p(1)&gt;0$, and $\Delta p &gt;1$ infinitely often. 
\end{itemize}
\end{lemma}

The question of which $r: \NN \to \ZZ$ can occur as a relative position function is a bit trickier. As noted above, there are some restrictions on relative position functions, which eliminate many possibilities. Here, we arrive at the first of the two main results of this section---a relative position function $r$ uniquely identifies $\ttw$.

\begin{lemma}\label{lemma2} Let $\ttw,\ttw' \in \W$ with relative position functions $r_\ttw$ and $r_{\ttw'}$, respectively. Then $\ttw=\ttw'$ if and only if $r_\ttw=r_{\ttw'}$.
\end{lemma}

\begin{proof} Necessity is clear, so we need only prove sufficiency. Toward this, suppose that $r_\ttw=r_{\ttw'}$. We show by induction that $p_{\tta,\ttw}(n)=p_{\tta,\ttw'}(n)$, from which the result follows.

We know that $r_{\ttw}(1) = r_{\ttw'}(1)$. If this value is positive, then the first $\tta$ must appear before the first $\ttb$, hence
\[
p_{\tta,\ttw}(1)=0=p_{\tta,\ttw'}(1) \,.
\]
On another hand, if $r_{\ttw}(1) = r_{\ttw'}(1) &lt;0$ then
\begin{align*}
 p_{\ttb,\ttw}(1)&amp;=0=p_{\ttb,\ttw'}(1)    \\
 p_{\tta,\ttw}(1)&amp;=0-r_{\ttw}(1)=0-r_{\ttw'}(1)=p_{\tta,\ttw'}(1)  \,.
\end{align*}
This shows the claim for $n=1$.

Now suppose that $p_{\tta,\ttw}(k)=p_{\tta,\ttw'}(k)$ for all positive integers $k\leq n$. Then, by the definition of $p_{\tta,\ttw}$,  $p_{\tta,\ttw'}$, $r_\ttw$, and $r_{\ttw'}$, the first $n$  $\tta$'s in $\ttw$ appear at the positions
\[
A_n:= \{p_{\tta,\ttw}(1), p_{\tta,\ttw}(2), \ldots, p_{\tta,\ttw}(n) \},
\]
and that the first $n$ $\ttb$'s in $\ttw$ appear at the positions
\[
B_n:= \{  p_{\tta,\ttw}(1)+r_\ttw(1), p_{\tta,\ttw}(2)+r_\ttw(2), \ldots, p_{\tta,\ttw}(n)+r_\ttw(n) \} \,.
\]
Since $r_\ttw=r_{\ttw'}$, and $p_{\tta,\ttw}(k)=p_{\tta,\ttw'}(k)$ for $1 \leq k \leq n$, we get that the first $n$  $\tta$'s in $\ttw'$ appear at the positions $A_n$ and that the first $n$ $\ttb$'s in $\ttw'$ appear at the positions $B_n$. Set
\[
M:= \min \big(\NN \backslash (A_n \cup B_n)\big) \,.
\]
We consider the two possible cases.

Suppose $r_\ttw(n+1)&gt;0$. Then, in $\ttw$, the $(n+1)$-th $\tta$ appears before the $(n+1)$-th $\ttb$. So, for $k \geq n+1$ the $k$-th $\ttb$ appears after the $(n+1)$-th $\tta$. Also, for $k \geq n+2$ the $k$-th $\tta$ appears after the $(n+1)$-th $\tta$. Since the $M$-th position contains either an $\tta$ or a $\ttb$, which is neither among the first $n$ $\tta$'s nor the first $n$ $\ttb$'s, it must contain the $(n+1)$-th $\tta$. Thus $p_{\tta,\ttw}(n+1)=M$. Repeating the argument for $\ttw'$ instead of $\ttw$, we get $p_{\tta,\ttw'}(n+1)=M$, and so $p_{\tta,\ttw}(n+1)=M=p_{\tta,\ttw'}(n+1)$.

If instead, $r_\ttw(n+1)&lt;0$, a similar argument shows that $p_{\ttb,\ttw}(n+1)=M=p_{\ttb,\ttw'}(n+1)$. Since $r_\ttw(n+1)=r_{\ttw'}(n+1)$, this gives $p_{\tta,\ttw}(n+1)=p_{\tta,\ttw'}(n+1)$.
\end{proof}

The proof of Lemma \ref{lemma2} gives the following algorithm for reconstructing $\ttw$ from $r_\ttw$.

\begin{lemma}[Reconstruction algorithm] Let $r : \NN \to \ZZ$ be the relative position function of some word $\ttw \in \W$. Then, we can recover the word $\ttw$ from $r$ by the following simple algorithm.

\textbf{Step 1.} If $r(1) &gt;0$, set $p_\tta(1)=0, p_\ttb(1)=r(1)$, otherwise set $p_\tta(1)=-r(1), p_\ttb(1)=0$.

\textbf{Step 2.} For each $n \geq 2$, define
\begin{align*}
A_n&amp;:= \{ p_\tta(1), p_\tta(2), \ldots, p_\tta(n) \}=A_{n-1} \cup \{ p_{\tta}(n) \} \\
B_n&amp;:= \{  p_\ttb(1), p_\ttb(2), \ldots, p_\ttb(n) \} =B_{n-1} \cup \{ p_{\ttb}(n) \}.
\end{align*}

\textbf{Step 3.} Set $k_{n+1}:= \min \big(\NN \backslash (A_n \cup B_n)\big)$. Then,
\begin{itemize}
  \item[(i)] if $r(n+1)&gt;0$, set $p_\tta(n+1)=k_{n+1}$ and\, $p_{\ttb}(n+1)=k_{n+1}+r(n+1)$,
  \item[(ii)] if $r(n+1)&lt;0$, set $p_\tta(n+1)=k_{n+1}-r(n+1)$ and\, $p_{\ttb}(n+1)=k_{n+1}$.
\end{itemize}

\textbf{Step 4.} Increase $n$ by $1$ and go back to Step 2.
\end{lemma}

\begin{remark} Given a relative position function $r$, in Step 3, one of the following two situations must occur.
\begin{itemize}
\item[($\alpha$)] If $r(n+1)&gt;0$, then we must have $k_{n+1} &gt; p_{\tta}(n)$, $k_{n+1}+r(n+1)&gt; p_{\ttb}(n)$, and $k_{n+1}+r(n+1) \notin A_n \cup B_n$.
\item[($\beta$)]  If $r(n+1)&lt;0$, then we must have $k_{n+1} &gt; p_{\ttb}(n)$, $k_{n+1}-r(n+1)&gt; p_{\tta}(n)$, and $k_{n+1}-r(n+1) \notin A_n \cup B_n$.
\end{itemize}

Moreover, given any function $r: \NN \to \ZZ \backslash \{0 \}$ with $r(1)&gt;0$, $r$ is the relative position function of some $\ttw$ if and only if
in the above algorithm the conditions $(\alpha)$ and $(\beta)$ always hold.\exend
\end{remark}

We now give the second main result of this section---each increasing function $r$ with $r(1)&gt;0$ is a relative position function---and we discuss the relation between monotonicity and the $\ttb$-runs. 

\begin{lemma}\label{lem:2.7}
For each increasing function $r: \NN \to \NN$, there exists some word $\ttw \in \Wa$ with $r=r_\ttw$.
\end{lemma}

\begin{proof} The idea of the proof is the same as the reconstruction algorithm---the key is that $r(n)&gt;0$ for each $n$. We determine the word $\ttw$ by the position of its letters. To this end, we start by defining $p_\tta(1)=0$ and $p_\ttb(1)=r(1)$, and proceed by induction.

For each $n \geq 1$, set
\begin{align*}
A_n&amp;:= \{ p_\tta(1), p_\tta(2), \ldots, p_\tta(n) \}=A_{n-1} \cup \{ p_{\tta}(n) \} \\
B_n&amp;:= \{  p_\ttb(1), p_\ttb(2), \ldots, p_\ttb(n) \} =B_{n-1} \cup \{ p_{\ttb}(n) \} \\
p_{\tta}(n+1)&amp;:= \min \NN \backslash (A_n \cup B_n) \\
p_{\ttb}(n+1)&amp;:=p_{\tta}(n+1)+r(n+1) \,.
\end{align*}
Since $(A_{n-1} \cup B_{n-1}) \subseteq (A_n \cup B_n)$, we immediately get that $p_{\tta}(n+1) &gt; p_{\tta}(n)$. Next,
\[
p_{\ttb}(n+1)=p_{\tta}(n+1)+r(n+1) &gt; p_{\tta}(n)+r(n) = p_{\ttb}(n) \,.
\]
Moreover, by definition $p_{\tta}(n+1) \notin A_n \cup B_n$, which, with $p_{\ttb}(n+1)&gt;p_\tta(n)$ and $p_{\ttb}(n+1)&gt;p_\ttb(n)$, imply that $p_{\ttb}(n+1) \notin A_n \cup B_n$. This immediately implies that for all $n$ we have $A_n \cap B_n =\varnothing$. Since $A_1 \subsetneq A_2  \subsetneq \cdots $ and $B_1 \subsetneq  B_2  \subsetneq \cdots $ are nested, we get that the unions
\[
A := \bigcup_n A_n \qquad\mbox{and}\qquad B := \bigcup_n B_n
\]
are disjoint infinite sets.

Finally, $p_\tta(1)=0$ and $p_\tta(n+1) &gt; p_{\tta}(n)$ immediately imply that $p_\tta(n) \geq n-1$. Therefore.
\[
\min \NN \backslash (A_n \cup B_n)= p_\tta(n+1)\geq n,
\]
hence
\[
\{1,2,3, \ldots, n \} \subseteq (A_{n+1} \cup B_{n+1})  \subseteq (A \cup B) \,.
\]
It follows that $\NN = A\cup B$. Now, defining
\begin{displaymath}
\ttw := \ell_0 \ell_1 \cdots \qquad\mbox{where}\qquad
\ell_k=
\begin{cases}
\tta, &amp; \text{if $k \in A$;} \\
\ttb, &amp;\text{if $k \in B$;} 
\end{cases}
\end{displaymath}
since $A\cap B=\varnothing$, we have that $r_\ttw=r$, which is the desired result.
\end{proof}

By applying an analogous argument, we get the following immediate corollary.

\begin{corollary} For each decreasing function $r : \NN \to \ZZ$ with $r(1)&lt;0$, there exists some $\ttw \in \Wb$ with $r=r_\ttw$.
\end{corollary}

\begin{definition} The \emph{reflection operator}, $\bar{\cdot}$, on  $\Sigma^\infty$, is the substitution $\overline{\tta}\mapsto\ttb$ and $\overline{\ttb}\mapsto\tta$.
\end{definition}

The following result is clear, so we omit the proof.

\begin{proposition}\label{prop12} The refection operator satisfies the following properties.
\begin{itemize}
    \item[(a)] $\overline{\Wa} = \Wb$ and $\overline{\Wb}=\Wa$.
    \item[(b)] Let $\ttw,\ttw'\in\W$. Then $\overline{\ttw}=\ttw'$ if and only if $r_{\ttw}=-r_{\ttw'}$\,.
\end{itemize}
\end{proposition}

This proposition allows us to restrict our attention to $r_\ttw$ for $\ttw \in \Wa$ as needed. Note that the condition $\ttw \in \Wa$ is equivalent to $r(1)&gt;0$, which is equivalent to $p_\tta(1)=0$. Also, $r(1)=k&gt;1$ if and only if $\ttw \in\tta^{k-1}\ttb\W$. And, if $r(1)=k&gt;1$, then $r(2),\ldots, r(k-1)\geq k$.

The reflection operator induces an involution, $\tilde{\cdot}$, on the class of binary substitutions.

\begin{definition} Let $\sigma :\Sigma\to \Sigma^*$ be a binary substitution. Define $\tilde{\sigma}:\Sigma\to \Sigma^*$ by
\[
\tilde{\sigma} (\alpha)= \overline{ \sigma(\overline{\alpha})} \qquad \forall \alpha \in \Sigma = \{ \tta, \ttb \} \,.
\]
\end{definition}
A fast calculation shows that $\tilde{\sigma} (\tts) =  \overline{ \sigma(\overline{\tts})}$ for all $\tts \in \Sigma^*$, hence $\tilde{\sigma} (\ttw) =  \overline{ \sigma(\overline{\ttw})}$ for $\ttw \in \W$.

The following characterization of the $\tta$ and $\ttb$ runs is clear.

\begin{lemma} \label{lem:1} Let $\ttw \in \Wa$ and $k \geq 1$.
\begin{itemize}
\item[(a)] The following are equivalent.
\begin{itemize}
\item[(i)]$\ttb^k$ is a subword of $\ttw$.
\item[(ii)] $\sup \{ \Delta p_\tta(n) \} &gt; k$.
\item[(iii)] $\Delta p_\ttb$ takes the value one at least $k-1$ times in a row.
\end{itemize}
\item[(b)]  The following are equivalent.
\begin{itemize}
\item[(i)]$\tta^k$ is a subword of $\ttw$.
\item[(ii)] $\Delta p_\tta$ takes the value one at least $k-1$ times in a row.
\end{itemize}
\end{itemize}
\end{lemma}

Note that Lemma~\ref{lem:1} implies that $\sup \{ \Delta p_\tta(n) \} - 1$ is the length of the longest run of $\ttb$'s in $\ttw$ and that
$\sup \{ \Delta p_\ttb(n) \} - 1$ is the length of the longest run of $\tta$'s appearing in $\ttw$. Combining this with the fact that $\Delta p_\tta \geq 1$, we have the following result.

\begin{lemma} \label{lemma1} Let $\ttw \in \Wa$.
\begin{itemize}
\item[(a)] If the function $r$ is strictly increasing, then ${\tt bb}$ is not a subword of ${\tt w}$.
\item[(b)] If\, ${\tt bb}$ is not a subword of ${\tt w}$, then $r$ is increasing.
\item[(c)] If\, $\ttb^k$ is a subword of $w$, there is an $n$ so that $\Delta r(n+j) \leq 0$ for all $j\in\{1,\ldots,k-1\}$.
\item[(d)] If $\tta^k$ is a subword of $w$, there is an $n$ so that $\Delta r(n+j) \geq 0$ for all $j\in\{1,\ldots,k-1\}$.
\end{itemize}
\end{lemma}
\begin{proof}
\textbf{(a)} Toward a contradiction, assume that $\ttb \ttb$ is a subword of $\ttw$. By Lemma~\ref{lem:1}(a), there exists some $n$ such that $\Delta p_\ttb(n)=1$. Since $\Delta p_{\tta}(n) \geq 1$, we get that $\Delta r(n) \leq 0$, which contradicts the fact that $r$ is strictly increasing.

\textbf{(b)} Since $\ttb \ttb$ is not a subword of $\ttw$, by Lemma~\ref{lem:1}(a), we have $\Delta p_\tta(n) \leq 2$ for all $n$ and that $\Delta p_\ttb$ never takes the value $1$, meaning that $\Delta p_\ttb(n) \geq 2$ for all $n$. It follows immediately that $\Delta r \geq 0$ so that $r$ is increasing.

The proofs of \textbf{(c)} and \textbf{(d)} follow \emph{mutatis mutandis} the proof of part \textbf{(a)} above.
\end{proof}

In Lemma~\ref{lemma1}(a), we cannot assume that $r$ is increasing, and, in Lemma~\ref{lemma1}(b), we cannot show that $r$ is strictly increasing. Indeed, here are two witnessing examples.
\begin{itemize}
  \item The word
\[
\ttw =\tta\ttb\tta\tta\ttb\ttb\tta\tta\tta\ttb \ttb\ttb\tta\tta\tta\tta\ttb\ttb\ttb\ttb\cdots =\tta \ttb \tta^2 \ttb^2 \tta^3 \ttb^3 \tta^4 \ttb^4 \cdots
\]
has the sequence $1,2,2,3,3,3,4,4,4,4,\ldots$, as its relative position function. Here, $r$ is increasing, but $\ttw$ contains $\ttb \ttb$ as a subword.

Later, we cover a more interesting example---the word obtained by adding the prefix $\tta \tta \ttb \ttb$ to the Fibonacci substitution $\sigma_2$ contains $\ttb \ttb$, and its relative position function $r$ satisfies $r(1)=r(2)=r(3)=2$ and is strictly increasing starting at $n=3$.
  \item The periodic word $\ttw = (\tta \ttb)^\omega$ does not contain $\ttb \ttb$ and has $r(n)=1$ for all $n$.
\end{itemize}

Before moving on to periodic sequences, we note that Lemma~\ref{lem:1} gives the following results on the possible boundedness of $\Delta r$.

\begin{lemma} Let $\ttw \in \Wa$. If $\ttb^k$ does not appear in $\ttw$, then 
\[
\left| \Delta r -\Delta p_\ttb \right| \leq k \,.
\]
In particular, $\Delta r$ is bounded if and only if $\Delta p_\ttb$ is bounded.
\end{lemma}

\begin{proof} This follows noting that $\Delta r =\Delta p_\ttb -\Delta p_\tta$, and by Lemma~\ref{lem:1}, $\Delta p_\tta &lt;k+1$.
\end{proof}

For a periodic word $\ttw$, all of the relative position functions are also periodic, as we shall prove here. But this relationship cannot be inverted---later, we will see some examples where $\Delta r_\ttw$ is periodic for an aperiodic word $\ttw$.

\begin{lemma}\label{lem:per-seq} Let $\ttw \in \Wa$. Then, the following are equivalent.
\begin{itemize}
  \item[(i)] $\ttw$ is periodic.
  \item[(ii)] $\Delta p_{\tta}$ is periodic.
  \item[(iii)] $\Delta p_{\tta}$ and $\Delta p_{\ttb}$ are periodic.
\end{itemize}
Moreover, if $\ttw =  (w)^\omega$ and $w$ contains $k\ \tta$'s and $j\ \ttb$'s, then $\Delta p_{\tta}$ is $k$-periodic and $\Delta p_{\ttb}$ is $j$-periodic.
\end{lemma}

\begin{proof}
(i)$\Rightarrow$(iii).
Let $\ttw = (w_0w_1\cdots w_{k+j-1})^\omega$, and let $w$ contain $k\ \tta$'s and $j\ \ttb$'s. Let $0 = l_0 &lt; l_1 &lt;l_2&lt;\cdots &lt; l_{k-1} \leq k+j-1$ be all the positions of $\tta$ in the word $w_0w_1\cdots w_{k+j-1}$. Then, the values of $p_a(1), p_a(2), p_a(3),\ldots$ are precisely
\[
l_0, l_1, l_2, \ldots, l_{j-1}, l_0+k+j, l_1+k+j, \ldots, l_{j-1}+k+j, l_0+2(k+j), l_1+2(k+j), \ldots\,.
\]
Explicitly, if $n=qk+r$ where $1 \leq r \leq k$ when divided by $k$, then
\[
p_a(n)=q(k+j)+l_{r-1} \,.
\]
In particular, $\Delta p_a$ is the $k$-periodic sequence obtained by repeating
\[
l_1 -l_0, l_2-l_1, \ldots, l_{k-1}-l_{k-2}, l_0-l_{k-1}+k+j \,.
\]
The proof for $\Delta p_b$ is identical.

The claim that (iii)$\Rightarrow$(ii) is clear.

(ii)$\Rightarrow$(i).
Assume that $\Delta p_{\tta}$ is periodic with period $k$. Note that $0 = p_\tta(1) &lt;  p_\tta(2) &lt; \cdots &lt; p_\tta(k)$. Set $m=p_\tta(k+1)-p_\tta(1)$. Then, for all $n=kq+t$ with $1 \leq t \leq k$, we have
\[
p_{\tta}(n)=mq+p_{\tta}(t) \,.
\]
This shows that the set of positions of $\tta$ in $\ttw$ is the finite union of the infinite arithmetic progressions
\[
p_\tta(1)+m \NN, p_\tta(2)+m \NN, \ldots, p_\tta(k)+m \NN \,,
\]
which is certainly periodic. The claim follows immediately.
\end{proof}

\begin{corollary} If $\ttw$ is periodic, so is $\Delta r(n)$. Moreover, if $\ttw=(w)^\omega$ and $w$ contains $k$ $\tt a$'s and $j$ $\ttb$'s, then ${\rm lcm}(k,j)$ is a period of $\Delta r$.
\end{corollary}

To illustrate the above properties of periodic words $\ttw$, we summarize some specific examples having small period in Table \ref{TT1}.

\begin{table}[htp]
\begin{center}
\begin{tabular}{c|c|c|c}
$\ttw$ &amp; $\Delta p_a$ &amp; $\Delta p_b$ &amp; $\Delta r$ \\ \hline
$(\tta\ttb)^\omega$ &amp; $2,2,2,2,2,2,\ldots$ &amp; $2,2,2,2,2,2,\ldots$ &amp; $0,0,0,0,0,0,\ldots$\\
$(\tta\tta\ttb)^\omega$ &amp; $1,2,1,2,1,2,\ldots$ &amp; $3,3,3,3,3,3,\ldots$ &amp; $2,1,2,1,2,1,\ldots$ \\
$(\tta\ttb\ttb\tta)^\omega$ &amp; $3,1,3,1,3,1,\ldots$ &amp; $1,3,1,3,1,3,\ldots$ &amp; $-2,2,-2,2,-2,2,\ldots$ \\
$(\tta\tta\ttb\ttb)^\omega$ &amp; $1,3,1,3,1,3,\ldots$ &amp; $1,3,1,3,1,3,\ldots$ &amp; $0,0,0,0,0,0,\ldots$
\end{tabular}
\caption{Relative position sequences for some periodic words having small period.}
\end{center}
\label{TT1}
\end{table}

We note that the example $\ttw=(\tta\tta\ttb\ttb)^\omega$ shows that the period of $\Delta r$ can be strictly smaller than the periods of $\Delta p_a$ and $\Delta p_b$.

In the remainder of this section, we discuss three more operators on the set of words $\W$---the deletion operator, the prefix operator, and the cloning operator.

\begin{definition} Let $D_\tta: \W \to \W$ and $D_\ttb : \W \to \W$ be the operators that delete the first $\tta$ and first $\ttb$, respectively, in a word. The \emph{deletion operator} $D :\W \to \W$ is defined by
\[
D:= D_\tta \circ D_\ttb \,.
\]
\end{definition}

It is quite clear that $D_\ttb$ and $D_\tta$ commute with each other, so also, $D=D_\ttb \circ D_\tta$. Also, the reflection operator, $\bar{\cdot}$, satisfies the equalities $D_\tta\circ\bar{\cdot}=\bar{\cdot}\circ D_\ttb$ and $D_\ttb\circ\bar{\cdot}=\bar{\cdot}\circ D_\tta$, so that $D$ and $\bar{\cdot}$ commute, that is, $D\circ\bar{\cdot}=\bar{\cdot}\circ D$.

With the language of the deletion operator in hand, we turn back to periodic sequences.

\begin{lemma} Let $\ttw \in \W$. Then, $\Delta p_{\ttb}$ is periodic if and only if $D_{\tta}^{p_{\ttb}(1)}(\ttw)$ is periodic.
\end{lemma}

\begin{proof}
Since $\ttw' = D_{\tta}^{p_{\ttb}(1)}(\ttw)$ is just $\ttw$ with its initial run of $\tta$'s deleted, if there are any, then $\Delta p_{\ttb,\ttw} = \Delta p_{\ttb, \ttw'}$. Hence, because $\ttw' \in \mathcal W_\ttb$, the conclusion follows from Lemma \ref{lem:per-seq}.
\end{proof}


\begin{definition} The \emph{prefix operator}, ${\rm Pre}_{u}: \W \rightarrow u\W$ is the operator that adds the finite word $u$ to the start of any word. That is, ${\rm Pre}_{u}(\ttw) = u\ttw$.
\end{definition}

The identity ${\rm Pre}_{u}\circ \bar{\cdot} =\bar{\cdot} \circ {\rm Pre}_{\bar{u}}$ is immediate from the definitions. 

The deletion and prefix operators allow one to classify binary words having the same number of $\tta$'s and $\ttb$'s. Here, we call a finite word $u$ \emph{equilibrious} provided it contains an equal number of $\tta$'s and $\ttb$'s.

\begin{lemma} Let $u\in\Sigma^*$ be a word of length $2k$. Then, $u$ is equilibrious if and only if $D^{k} \circ {\rm Pre}_u = \mbox{Id}$.
\end{lemma}

\begin{proof}
Let $u\in\Sigma^*$ be a word of length $2k$. Note that for each $\ttw \in \W$,
\[
D^{k} \circ {\rm Pre}_u(\ttw)= D^{k} (u \ttw )
\]
deletes the first $k$ $\tta$'s and the first $k$ $\ttb$'s in $u \ttw$.

Assume that $u$ is equilibrious. Since $u$ contains $k$ $\tta$'s and $k$ $\ttb$, $D^{k} (u \ttw )$ deletes the first $2k$ letters, which is the prefix $u$. That is, $D^{k} (u \ttw)=\ttw$.

Now suppose that $D^{k} \circ {\rm Pre}_u = \mbox{Id}$, and, toward a contradiction, let us further assume that $u$ is not equilibrious. Then, $u$ either contains at least $k+1$ $\tta$'s or it contains at least $k+1$ $\ttb$'s. Without loss of generality, suppose that $u$ contains at least $k+1$ $\tta$'s. Let $\ttw \in \W$ be arbitrary and consider
\[
D^{k} \circ {\rm Pre}_u (\ttw)= D^{k} (u \ttw) \,.
\]
Here, $u$ contains at most $k-1$ $\ttb$'s. Therefore, $D^k$ deletes all the $\ttb$'s in $u$, and deletes only $k$ of the at least $k+1$ $\tta$'s in $u$. This immediately implies that $D^{k} (u \ttw)$ starts with an $\tta$. Thus, we have $D^{k} \circ {\rm Pre}_u( \W) \subseteq \tta\W\subsetneq\W$, a contradiction that proves the result.
\end{proof}

We finish our focus on the prefix operator by showing that the addition of equilibrious words eventually shifts the (relative) position function(s).

\begin{lemma} Let $u\in\Sigma^*$ be an equilibrious word of length $2k$ and $\ttw \in \W$. Then, $p_{\tta,{\rm Pre}_{u}(\ttw)}(n+k) = p_{\tta,\ttw}(n)+2k$ and $p_{\ttb,{\rm Pre}_{u}(\ttw)}(n+k) = p_{\ttb,\ttw}(n)+2k$. In particular, $r_{{\rm Pre}_{u}(\ttw)}(n+k) = r_{\ttw}(n)$.
\end{lemma}

\begin{proof}
Each $\tta$ and $\ttb$ in $\ttw$ shifts to the right by $2k$ spots in ${\rm Pre}_{u}(\ttw)=u \ttw$, and has their position (in order) increased by $k$, since there are $k$ bits of same type introduced before it. The claim follows.
\end{proof}

In the last part of this section, we discuss how the (relative) position functions behave on words under a binary substitution. Here, since we are interested in the set $\W$ of words that have infinitely many occurrences of $\tta$ and $\ttb$, we restrict ourselves to the consideration of binary substitutions $\mu$ such that both $\tta$ and $\ttb$ appear in $\mu(\tta\ttb)$.

In addition to the reflection operator, a particularly well-behaved family is the cloning substitutions.

\begin{definition} Let $k &gt;1$ be a positive integer. The \emph{cloning substitution} $\phi_k: \Sigma \to \Sigma^*$ is defined by
\[
\phi_k:\begin{cases} \tta\rightarrow \tta^k \\
\ttb\rightarrow \ttb^k \,.\end{cases}
\]
\end{definition}

Before proceeding, let us note in passing that for all $k \geq 2$ we have $\phi_k(\Wa) \subsetneq \Wa$ and $\phi_k(\Wb) \subsetneq \Wb$. The proof of the following lemma is clear, so we omit it.

\begin{lemma}\label{lem23} Let $\ttw \in \W$ and $k \geq 2$.  Then, for all $m \in \ZZ_{\geq 0}$ and all $1 \leq j \leq k$, we have
    \begin{align*}
    p_{\tta,\phi_k(\ttw)}(mk+j)&amp;=k\, p_{\tta,\ttw}(m+1)+j-1 \\
    p_{\ttb, \phi_k(\ttw)}(mk+j)&amp;=k\, p_{\ttb,\ttw}(m+1)+j-1 \\
    r_{\phi_k(\ttw)}(mk+j) &amp;= k\, r_{\ttw}(m+1) \,.
    \end{align*}
\end{lemma}

The formulas in Lemma~\ref{lem23} can be alternatively written in the form
    \begin{align*}
    p_{\tta,{\phi_k}(\ttw)}(n)&amp;=k\, p_{\tta,\ttw}\left(\left\lfloor \frac{n}{k} \right\rfloor+1\right)+n-k\left\lfloor \frac{n}{k} \right\rfloor-1 \\
    p_{\ttb,{\phi_k}(\ttw)}(n)&amp;=k\, p_{\ttb,\ttw}\left(\left\lfloor \frac{n}{k} \right\rfloor+1\right)+n-k\left\lfloor \frac{n}{k} \right\rfloor-1 \\
    r_{{\phi_k}(\ttw)}(n) &amp;= k\, r_{\ttw}\left(\left\lfloor \frac{n}{k} \right\rfloor+1\right) \, ,
    \end{align*}
where $\lfloor \cdot \rfloor$ is the standard floor function. In particular, we have that the ratios ${p_{\tta,{\phi_k}(\ttw)}(n)}/{n}$, ${p_{\ttb,{\phi_k}(\ttw)}(n)}/{n}$ and ${r_{{\phi_k}(\ttw)}(n)}/{n}$ have the same limits of indetermination as the ratios ${p_{\tta,\ttw}(n)}/{n}$, ${p_{\ttb,\ttw}(n)}/{n}$ and ${r_{\ttw}(n)}/{n}$, respectively, as $n\to\infty$.

\section{Mean values of (relative) position functions}\label{sec:meanv}

A nice consequence of Lemma~\ref{lem:1} is that for binary words where the number of consecutive identical letters is bounded, the relative position function is bounded, above and below, by linear functions.

\begin{lemma}\label{r-bounded-by-linear} Let $\ttw \in \Wa$. Denote the longest run of a single letter in ${\tt w}$ by $c$. If
\begin{align}
c:&amp;= \sup\{ k :\ell_{n}=\ell_{n+1}=\cdots = \ell_{n+k-1},n \in \ZZ_{\geq 0} \} \nonumber\\
&amp;= \sup \{ \Delta p_a(n) - 1, \Delta p_b(n) - 1 : n \in \ZZ_{\geq 0}\} \cup \{ p_b(1)\}&lt;\infty \label{rel-den}\, ,
\end{align}
then,
\begin{align}
 p_\tta(n) &amp; \leq (c+1)(n-1)  \label{eq1}\\
 p_\ttb(n) &amp; \leq (c+1)n-1  \label{eq2}\,.
\end{align}
In particular, $(1-c)n+1 \leq r(n) \leq cn$.
\end{lemma}

\begin{proof} Since $\tta^{c+1}$ and $\ttb^{c+1}$ are not subwords of $\ttw$, Lemma~\ref{lem:1} gives both $\Delta p_\tta(n) \leq c+1$ and $\Delta p_\ttb(n) \leq c+1$. Since $p_\tta(1)=0$ and $p_\ttb(1)\leq c$, an easy induction yields
\eqref{eq1} and \eqref{eq2}.

Noting that $p_\tta(1)=0$, both $p_\tta(n) \geq n-1$ and $p_\ttb(n)\geq n$, thus combinations of the upper bounds from the previous paragraph give $c(1-n)+1 \leq r(n) \leq cn$, which finishes the proof.
\end{proof}

\begin{remark} The condition \eqref{rel-den} is equivalent to the sets of positions of $\tta$ and $\ttb$, respectively, being relatively dense in $\ZZ_{\geq 0}$. In particular, this
always holds for infinite words that are fixed points of primitive substitutions. For the definitions and examples related to relatively dense sets and substitutions, see Baake and Grimm \cite{TAO}.\exend
\end{remark}

In general, the upper bounds in \eqref{eq1} and \eqref{eq2} cannot be improved. To see this, note that for the periodic word $\ttw = (\tta \ttb^{c})^\omega$ we get equality in \eqref{eq1}, and for the periodic word $\ttw = (\tta^{c} \ttb)^\omega$ we get equality in \eqref{eq2}.

\begin{corollary} Let $\ttw \in \W$ whose longest letter run $c&lt;\infty$. Then,
\[
 p_\tta(n)  \leq (c+1)n-1  \quad\mbox{and}\quad
 p_\ttb(n)  \leq (c+1)n-1 .
\] In particular, $-cn \leq r(n) \leq cn $.
\end{corollary}

\begin{proof} By applying the reflection operator and Lemma~\ref{r-bounded-by-linear}, we have, for $\ttw \in \Wb$, that $p_\tta(n) \leq (c+1)n-1$,  $p_\ttb(n) \leq (c+1)(n-1)$, and $-cn \leq r(n) \leq c(n-1)-1$. 
\end{proof}

For a word $\ttw$ and a letter $\alpha\in\Sigma$, let $\#_\alpha(n)=\#_{\alpha,\ttw}(n)$ denote the counting function of the occurrences of $\alpha$ in the first $n$ bits of $\ttw$. Note that $\#_\alpha$ is an increasing function. For $\alpha \in \{ a, b \}$, it is immediate that $\#_\alpha(p_{\alpha}(n))=n$, and $\#_{\alpha}(m)=n$ if and only if $p_\alpha(n) \leq m &lt; p_{\alpha}(n+1)$ for all $n\geq 1$. In particular, $\#_\alpha \circ p_\alpha = \mbox{Id}$,
$p_\alpha \circ \#_\alpha \leq \mbox{Id}$, and $p_\alpha \circ (\#_\alpha+1) &gt; \mbox{Id}$. Here, one has to be mindful of indices as $p_\alpha$ has domain $\ZZ_{\geq 0}$. The following lemma and corollary are direct consequences of the relationships between $\#_\alpha(m)$ and $p_\alpha(n)$,

\begin{lemma}\label{dens} Let $\ttw \in \W$ and $\alpha\in\Sigma$. Then,
\begin{itemize}
\item[(a)] $\displaystyle{\lim_{m\to\infty} \frac{\#_\alpha(m)}{m} = d \in (0,1]}$ if and only if\, $\displaystyle{\lim_{n\to\infty}\frac{p_\alpha(n)}{n} = \frac{1}{d}}$,
\item[(b)] $\displaystyle{\lim_{m\to\infty} \frac{\#_\alpha(m)}{m} = 0}$
if and only if\, $\displaystyle{\lim_{n\to\infty}\frac{p_\alpha(n)}{n} = \infty}$.
\end{itemize}
\end{lemma}

\begin{corollary}\label{cor:liminfsup}  Let $\ttw \in \W$ and $\alpha\in\Sigma$. Then
\begin{equation*}
\limsup_{m\to\infty} \frac{\#_\alpha(m)}{m} =\limsup_{n\to\infty} \frac{n}{p_\alpha(n)} \qquad\mbox{and}\qquad\liminf_{m\to\infty} \frac{\#_\alpha(m)}{m} =\liminf_{n\to\infty} \frac{n}{p_\alpha(n)} \,. 
\end{equation*}
\end{corollary}

For the remainder of this section, we focus on results concerning the \emph{frequency} of the letters in a binary word $\ttw$. That is, for $\alpha\in\Sigma$, the limit 
\[
{\rm Freq}(\alpha)={\rm Freq}_\alpha(\ttw) := \lim_{m\to\infty} \frac{\#_\alpha(m)}{m}.
\] Our discussion involves possible existence as well as consequences if the frequency exists. Note that frequency is often called \emph{natural density}, especially in number theory. The following result, follows from Lemma \ref{dens}, and is also well-known---it is essentially folklore.

\begin{theorem}\label{t1} Let $\ttw \in \W$ and $d\in(0,1)$. The following are equivalent.
\begin{itemize}
  \item[(i)] ${\rm Freq}(\ttb)$ exists and is $d$.
  \item[(ii)] ${\rm Freq}(\tta)$ exists and is $1-d$.
  \item[(iii)] $\lim_{n\to\infty} {p_\ttb(n)}/{n}=\frac{1}{d}$.
  \item[(iv)] $\lim_{n\to\infty} {p_\tta(n)}/{n}=\frac{1}{1-d}$.
\end{itemize}
\end{theorem}

\begin{corollary}\label{cor:asymp} Let $\ttw$ be a word such that ${\rm Freq}(\ttb)=d \in (0,1)$. Then,
\begin{equation*}
\lim_{n\to\infty} \frac{r(n)}{n}=\frac{1}{d}-\frac{1}{1-d}=\frac{1-2d}{d(1-d)} \,.
\end{equation*}
\end{corollary}

In particular, recalling that in a binary substitution the frequencies of the letters exist and are proportional to the right Perron-Frobenius eigenvector, the following result holds.

\begin{lemma}\label{sub:asympt} Let $\mu : \Sigma \to \Sigma^*$ be a primitive substitution and $[u\ 1]^T$
be a right Perron--Frobenius eigenvector for the incidence matrix $M_\mu$. Let $\ttw \in \W$ be a fixed point of $\mu$; that is, $\mu(\ttw)=\ttw$. Then, the following limits exist
\begin{align}
  {\rm Freq}(\tta) =\frac{u}{u+1},\quad {\rm Freq}(\ttb) =\frac{1}{u+1}, \label{eqx}\quad 
  \lim_{n\to\infty} \frac{p_\tta(n)}{n}= 1+\frac{1}{u},\\
  \lim_{n\to\infty} \frac{p_\ttb(n)}{n}=u+1,\ \ \mbox{and}\ \
  \lim_{n\to\infty} \frac{r(n)}{n}=u-\frac{1}{u}=\frac{u^2-1}{u}. \nonumber
\end{align}
Moreover, all the above limits belong to $\QQ(\lambda_{PF})$, where $\lambda_{PF}$ is the Perron--Frobenius eigenvalue of $M_\mu$.
\end{lemma}

\begin{proof}
The equations in \eqref{eqx} follow from the fact that the frequencies exist and are proportional to $[u\ 1]^T$. The existence and values of the remaining limits follow immediately from the previous results.

Let $M_\mu \in \mathcal{M}_2(\ZZ)$ be the incidence matrix, $\lambda_{PF}$ its Perron--Frobenius eigenvalue. Then $0 \neq u \in \QQ(\lambda_{PF})$.
\end{proof}

\begin{proposition}
Let $\ttw \in \mathcal W$, and suppose that $\lim_{n\to\infty} {r(n)}/{n} =: r \in [-\infty, \infty]$; that is, $r$ takes a value in the extended real numbers. Then
\begin{displaymath}
{\rm Freq}(\ttb) = \begin{cases}
0, &amp; \text{if $r = \infty$;} \\
1, &amp; \text{if $r = -\infty$;} \\
\frac{1}{2}, &amp; \text{if $r = 0$;} \\
\frac{2+r - \sqrt{4+r^2}}{2r}, &amp; \text{if $r\in (-\infty,0)\cup (0,\infty)$.}
\end{cases}
\end{displaymath}
\end{proposition}

\begin{proof}
First, suppose $r=\infty$. Since ${r(n)}/{n} = {p_{\ttb}(n)}/{n} - {p_{\tta}(n)}/{n}$ is the difference of two positive sequences then we must have $\lim_{n\to\infty} \frac{p_{\ttb}(n)}{n} = \infty$. Thus, by Theorem \ref{t1}, ${\rm Freq}(\ttb) = 0$. 

If $r= -\infty$, then, as above, we must have $\lim_{n\to\infty} \frac{p_a(n)}{n}=\infty$. Thus, by Lemma \ref{dens}, we have ${\rm Freq}(a)=0$, so ${\rm Freq}(b)=1$.

Now suppose that $r\in (-\infty,\infty)$. Due to the existence of $\lim_{n\to\infty} {r(n)}/{n}$ and that $r(n)=p_\ttb(n)-p_\tta(n)$, a classical limit equality gives that 
\[
\limsup_{n\to\infty}\frac{p_\ttb(n)}{n}=\limsup_{n\to\infty}\frac{r(n)+p_\tta(n)}{n}=\lim_{n\to\infty}\frac{r(n)}{n}+\limsup_{n\to\infty}\frac{p_\tta(n)}{n}.
\]
Then, using Corollary \ref{cor:liminfsup},
\begin{align*}
r = \lim_n \frac{r(n)}{n}  &amp;= \limsup_{n\to\infty} \frac{p_{\ttb}(n)}{n} - \limsup_{n\to\infty} \frac{p_{\tta}(n)}{n}\\ 
&amp;= \frac{1}{\displaystyle{\liminf_{m\to\infty} \frac{\#_{\ttb}(m)}{m}}} - \frac{1}{\displaystyle{\liminf_{m\to\infty} \frac{\#_{\tta}(m)}{m}}}
\\  
&amp;= \frac{1}{\displaystyle{\liminf_{m\to\infty} \frac{\#_{\ttb}(m)}{m}}} - \frac{1}{\displaystyle{1 - \liminf_{m\to\infty} \frac{\#_{\ttb}(m)}{m}}}\\ 
&amp;= \frac{\displaystyle{1 - 2\liminf_{m\to\infty} \frac{\#_{\ttb}(m)}{m}}}{\displaystyle{\liminf_{m\to\infty} \frac{\#_{\ttb}(m)}{m}\left(1 - \liminf_{m\to\infty} \frac{\#_{\ttb}(m)}{m}\right)}}\,.
\end{align*}
Set $d_- := \liminf_m \frac{\#_{\ttb}(m)}{m}\in (0,1)$ to make the analysis cleaner. Hence,
\[
r=\frac{1-2d_-}{d_-(1-d_-)} \,.
\]
When $r=0$, we thus have $d_-=\frac{1}{2}$, while when $r \neq 0$, we obtain $rd_-^2-(2+r)d_-+1=0$ so that
\[
d_- =\frac{2+r \pm \sqrt{(2+r)^2-4r}}{2r}= \frac{2+r \pm \sqrt{4+r^2}}{2r} \,.
\]
Note that when $r \neq 0$, the quadratic polynomial $f(x)=rx^2-(2+r)x+1$ satisfies $f(0)=1&gt;0$ and $f(1)=-1&lt;0$, and therefore, has exactly one zero $d_- \in (0,1)$, which uniquely identifies $d_-$.

Repeating the same argument with $d_+ := \limsup_{m\to\infty} \frac{\#_{\ttb}(m)}{m} \in (0,1)$ yields
\[
r = \liminf_n \frac{r(n)}{n} = \frac{1-2d_+}{d_+(1-d_+)}\,.
\]
By uniqueness, $d_- = d_+$, so $d = {\rm Freq}(\ttb)$ exists. As noted above, if $r=0$, then $d=\frac{1}{2}$, and when $r\neq 0$, $d$ is equal to the single value satisfying
\[
d = \frac{2+r \pm \sqrt{4+r^2}}{2r}\in(0,1).
\]
If $r&gt;0$, $\sqrt{4 + r^2} &gt;r$ so that $\frac{2+r +\sqrt{4+r^2}}{2r}&gt;1$, and $d=\frac{2+r -\sqrt{4+r^2}}{2r}$. On the other hand, if $r&lt;0$, then $-r = |r| &lt; 2 + \sqrt{4 + r^2}$, and
\[
\frac{2+r + \sqrt{4+r^2}}{2r} &lt; 0
\]
Thus, again, $d=\frac{2+r -\sqrt{4+r^2}}{2r}$.
\end{proof}

\begin{theorem} If one of the limits
\[
r:= \lim_n \frac{r(n)}{n},\quad
p:= \lim_n \frac{p_\ttb(n)}{n},\quad\mbox{or}\quad
q:=\lim_n \frac{p_\tta(n)}{n},
\]
exist, then they all exist and $\frac{1}{p}+\frac{1}{q}=1$.
Moreover, on the extended reals,
\[
p= \frac{2+r + \sqrt{4+r^2}}{2} \quad \textrm{and} \quad q = \frac{2-r + \sqrt{4+r^2}}{2}.
\]
\end{theorem}
\begin{proof}
The previous proposition proves the simultaneous existence of these limits.
Hence, we have $r=p-q$ and $\frac{1}{p}+\frac{1}{q}={\rm Freq}(\ttb) + {\rm Freq}(\tta)=1$. Thus, $r=p-\frac{p}{p-1}$, so that  $p^2-(2+r)p+r =0$, from which we obtain
\[
p= \frac{2+r \pm \sqrt{4+r^2}}{2}\,.
\]
By the previous proposition, when $r\in (-\infty,0)\cup(0,\infty)$,
\[
p = \frac{1}{d} = \frac{2r}{2+r - \sqrt{4+r^2}} = \frac{2r(2+r + \sqrt{4+r^2})}{(2+r)^2 - (4+r^2)} = \frac{2+r + \sqrt{4+r^2}}{2}\,.
\]
Observe that this formula also holds true for $r\in\{0,\pm \infty\}$, and $q = p-r = \frac{2-r + \sqrt{4+r^2}}{2}$.
\end{proof}

We finish this section by considering what happens to the asymptotics of the (relative) position functions under a binary substitution. This is addressed by the following result on the frequency of letters of a fixed point of a binary substitution---this result is folklore, so we omit its proof.

\begin{theorem}
Let $\mu : \Sigma \rightarrow \Sigma^*$ be a substitution with incidence matrix $M_\mu\in M_2(\mathbb Z)$ such that $\tta$ and $\ttb$ appear in $\mu(\tta\ttb)$. If $\ttw \in \mathcal W$ is any word such that ${\rm Freq}_\tta(\ttw)$ exists, then
\[
\begin{bmatrix}
{\rm Freq}_\tta(\mu(\ttw)) \\ {\rm Freq}_\ttb(\mu(\ttw))
\end{bmatrix}
\ = \ \frac{1}{|\mu(\tta)|\cdot{\rm Freq}_\tta(\ttw) + |\mu(\ttb)|\cdot{\rm Freq}_\ttb(\ttw)}\cdot M_\mu\cdot\begin{bmatrix}
{\rm Freq}_\tta( \ttw) \\ {\rm Freq}_\ttb( \ttw)
\end{bmatrix}\,.
\]
\end{theorem}

Of course, once you have the letter frequencies, you have the relative position asymptotics.

\begin{example} Let $\ttw \in \W$, $k \geq 2$, and let ${\phi_k}$ be the $k$-cloning substitution. The incidence matrix of $\phi_k$ is $kI_2$.
Using the above theorem, or Lemma \ref{lem23}, 
if one of the limits below exist, then all exist, and ${\rm Freq}_\alpha(\ttw) =     {\rm Freq}_\alpha(\phi_k(\ttw)) $  for $\alpha\in\Sigma$,
\begin{align*}
\lim_{n\to\infty} \frac{r_{\ttw}(n)}{n} = &amp;\lim_{n\to\infty} \frac{r_{\phi_k(\ttw)}(n)}{n},\quad
  \lim_{n\to\infty} \frac{p_{\tta,\ttw}(n)}{n}= \lim_{n\to\infty} \frac{p_{\tta,\phi_k(\ttw)}(n)}{n}\, ,\\
  &amp;\mbox{and}\quad
    \lim_{n\to\infty} \frac{p_{\ttb,\ttw}(n)}{n}= \lim_{n\to\infty} \frac{p_{\ttb,\phi_k(\ttw)}(n)}{n}\, .
\end{align*}
\end{example}

\section{The Fibonacci and extended Pisa substitution family}\label{sect:fib}

In this section, we look at the extended Pisa family of substitutions, whose  canonical example is the Fibonacci substitution. To introduce this family, we start this section by focusing on the Fibonacci substitution and emphasize some features that are exclusive to this example.

\begin{definition} We call the substitution,
\[
\mu_F:\begin{cases}
\tta&amp;\to \tta \ttb \\
\ttb&amp;\to\tta \,,
\end{cases}
\]
the \emph{Fibonacci substitution}, and the resulting one-sided infinite fixed point,
\[
\ttf := \tta \ttb \tta \tta \ttb \tta \ttb \tta \cdots  = \lim_{n\to\infty} \mu_F^n(\tta)\, ,
\]
the \emph{Fibonacci word}.
\end{definition}

We start with the first of two main results of this section.

\begin{theorem}\label{thm-fib}The Fibonacci word $\ttf$ has the following properties.
\begin{itemize}
  \item[(a)] $\Delta p_\tta$ is the sequence obtained from the Fibonacci word under the coding $(\tta,\ttb)=(1,2)$.
  \item[(b)] $\Delta p_\ttb$ is the sequence obtained from the Fibonacci word under the coding $(\tta,\ttb)=(2,3)$.
  \item[(c)] $r(n)=n$ and $\Delta r=1$. In particular, $\Delta r$ is periodic.
\end{itemize}
\end{theorem}

\begin{proof}
\textbf{(a)} Consider the level-$1$ supertiles $\ttA_1:=\mu_F(\tta)=\tta \ttb$ and $\ttB_1 :=\mu_F(\ttb)=\tta$. Each such supertile contains exactly one $\tta$, at the beginning. This means that, for all $n \geq 1$ the $n$-th $\tta$ is the first letter of the $n$-th level-$1$ supertile.

Now, if the $n$-th letter in the Fibonacci word is $\tta$, then the $n$-th supertile is $\ttA_1=\tta \ttb$. This means that the $n$-th $\tta$ is followed by $\ttb$, and then, since there are no two $\ttb$'s in a row, that $\ttb$ is followed by $\tta$. This implies that the distance between the $n$-th and $(n+1)$-th $\tta$ is $2$ whenever the $n$-th letter in the Fibonacci word is $\tta$.

Next, if the $n$-th letter in the Fibonacci word is $\ttb$, then the $n$-th supertile is $\ttB_1=\tta$. Since $\ttB_1\ttB_1$ never appears, this $\ttB_1$ is followed by $\ttA_1=\tta \ttb$. This implies that the distance between the $n$-th and $(n+1)$-th $\tta$ is $1$ when the $n$-th letter in the Fibonacci word is $\ttb$. Therefore
\begin{displaymath}
\Delta p_\tta(n) =
\begin{cases}
  2, &amp; \text{if the $n$th letter in $\ttf$ is $\tta$;} \\
  1, &amp; \text{if the $n$th letter in $\ttf$ is $\ttb$.}
\end{cases}
\end{displaymath}

\textbf{(b)} Consider the level-$2$ supertiles $\ttA_2 :=\mu_F^2(\tta)=\tta \ttb \tta$ and $\ttB_2 :=\mu_F^2(\ttb)=\tta \ttb$. Each such supertile contains exactly one $\ttb$, in the second position. This means that, for all $n \geq 1$ the $n$-th $\ttb$ is the second letter of the $n$-th level-$2$ supertile.

Now, if the $n$-th letter in the Fibonacci word is $\tta$, then the $n$-th level two supertile is $\ttA_2=\tta \ttb \tta$. The next supertile starts with $\tta \ttb$ since $\ttA_2=\tta \ttb \tta$ and $\ttB_2=\tta \ttb$. This implies that the distance between the $n$-th and $(n+1)$-th $\ttb$ is $3$ whenever the $n$-th letter in the Fibonacci word is $\tta$.

Next, if the $n$-th letter in the Fibonacci word is $\ttb$, then the $n$-th level-$2$ supertile is $\ttB_2=\tta \ttb$. The next level-$2$ supertile starts with $\tta \ttb$, again since both $\ttA_2$ and $\ttB_2$ start with $\tta \ttb$. This implies that the distance between the $n$-th and $(n+1)$-th $\ttb$ is $2$ whenever the $n$-th letter in the Fibonacci word is $\ttb$. Therefore
\begin{displaymath}
\Delta p_\ttb(n) =
\begin{cases}
  3, &amp; \text{if the $n$th letter in $\ttf$ is $\tta$;} \\
  2, &amp; \text{if the $n$th letter in $\ttf$ is $\ttb$.}
\end{cases}
\end{displaymath}

\textbf{(c)}
By (a) and (b) we have $\Delta r(n)=1$ for all $n$. By looking at the first $2$ letters in the Fibonacci word $\ttf$, we get that $r(1)=1$. 
\end{proof}

Theorem \ref{thm-fib} implies that the Fibonacci word is the only word such that $r(n)=n$. Theorem~\ref{thm:6} below gives a different proof of the fact that $r_{\ttf}(n)=n$. We prove below, in Theorem~\ref{fib-uni}, that the Fibonacci word is the unique non-periodic word that satisfies properties (a) and (b) in Theorem~\ref{thm-fib}, with $(1,2)$ and $(2,3)$ replaced by any two tuples.

Let $\tau= \frac{1+\sqrt{5}}{2}$ be the golden ratio. By Lemma \ref{sub:asympt}, the Fibonacci $\ttf$ word satisfies
\[
{\rm Freq}_\ttf(\tta)=\frac{\tau}{\tau+1},\ \ {\rm Freq}_\ttf(\ttb)=\frac{1}{\tau+1} \,,\quad\mbox{and}\quad\lim_{n\to\infty} \frac{r_\ttf(n)}{n}= \tau+1- \frac{\tau+1}{\tau}= \frac{\tau^2-1}{\tau}=1 \,.
\]
Of course this holds by the previous theorem, but it is important to realize that the substitution itself was telling us that $r_{\ttf}(n)$ had to at least be asymptotically $n$.

We can characterize all substitutions such that $\lim_{n\to\infty} {r(n)}/{n}=1$. We require the following preliminary result.

\begin{lemma}\label{lem2} Let $M \in M_2(\ZZ)$. Then,  $[\tau\ 1]^T$ is a right eigenvector for $M$ if and only if there exists $m, n \in \ZZ$ such that
\[
M= \begin{bmatrix} m+n &amp; m \\ m &amp; n\end{bmatrix} = m\begin{bmatrix}
 1 &amp; 1 \\
 1 &amp; 0
\end{bmatrix} + n \begin{bmatrix}
    1 &amp; 0 \\
    0&amp; 1
\end{bmatrix}.
\]
Moreover, in this case, the eigenvalues of $M$ are $n+m \tau$ and $n+m \tau'$, where $\tau'=(1-\sqrt{5})/2$ is the algebraic conjugate of $\tau$.
\end{lemma}

\begin{proof}
($\Leftarrow$). This direction follows easily from
\[
\begin{bmatrix}m+n &amp; m \\ m &amp; n \end{bmatrix}\begin{bmatrix} \tau  \\ 1 \end{bmatrix}= \begin{bmatrix} m \tau + n \tau +m \\  m \tau + n \end{bmatrix} = (m \tau + n) \begin{bmatrix}
\tau  \\ 1\end{bmatrix}.
\]

($\Rightarrow$). Define $M$ by
\[
M =\begin{bmatrix} k &amp; l \\  m &amp; n \end{bmatrix} \in M_2(\ZZ).
\]
The eigenvalue-eigenvector equation $ M\,[\tau\ 1]^T=\lambda\,[\tau\ 1]^T$ is equivalent to the linear system
\begin{align*}
  k \tau + l &amp;= \tau \lambda \\
  m\tau + n &amp;= \lambda \,.
\end{align*}
Therefore, $\lambda=\lambda_1 = m \tau +n = k-l \tau' \in \ZZ[\tau]$. Since $M$ has integer entries, the second eigenvalue is the algebraic conjugate $\lambda_2 = m \tau'+n = k-l\tau$. Then,
\[
k+n= \tr(M)= \lambda_1+\lambda_2= (m \tau +n)+(m \tau'+n)=(k-l \tau')+(k-l \tau) \,.
\]
It follows that $k+n=2n+m=2k-l$, hence $k=n+l$ and $l=m$. Therefore,
\[
M= \begin{bmatrix} m+n &amp; m \\ m &amp; n\end{bmatrix},
\]
which is the desired result.
\end{proof}

\begin{example} When $m=f_k, n=f_{k-1}$ are consecutive Fibonacci numbers, we have
\[
M=\begin{bmatrix} m+n &amp; m \\ m &amp; n\end{bmatrix}= \begin{bmatrix} f_{k+1} &amp; f_k \\ f_k &amp; f_{k-1}\end{bmatrix}= \begin{bmatrix}
1 &amp; 1 \\
1 &amp; 0
\end{bmatrix}^k \,.
\]
The ring $\ZZ[\tau]$ is a free $\ZZ$-module with basis $\{ \tau, 1\}$. Now, each element $m\tau+n$ induces a $\ZZ$-linear homomorphism $T_{m\tau+n}: \ZZ[\tau]\to \ZZ[\tau]$. The matrix $M$ is exactly the matrix of the linear mapping $T_{m\tau+n}$ with respect to the canonical basis $\{ \tau, 1 \}$. The product of the matrices $M$ and 
\[
M'= \begin{bmatrix} m'+n' &amp; m' \\ m' &amp; n'\end{bmatrix}
\] 
has $[\tau\ 1]^T$ as a right eigenvector, hence $MM'$ must also be of this form. \exend
\end{example}

\begin{lemma}\label{lem2a1} Let $\mu : \Sigma \to \Sigma^*$ be any primitive substitution, $\ttw \in \W$ such that $\mu(\ttw)=\ttw$, and $M_\mu$ be the incidence matrix of $\mu$. The following are equivalent.
\begin{itemize}
\item[(i)] $\lim_{n\to\infty} {r(n)}/{n}=1$.
\item[(ii)]  $[\tau\ 1]^T$ is a right Perron--Frobenius eigenvector for $M_\mu$.
\end{itemize}
\end{lemma}

\begin{proof}
Let $[u\ 1]^T$ be a right Perron--Frobenius eigenvector of $M_\mu$. By Lemma~\ref{sub:asympt}, we have
\[
\lim_{n\to\infty} \frac{r(n)}{n}=\frac{u^2-1}{u}.
\]

Now, (i) holds if and only if $\frac{u^2-1}{u} =1$, so $u \in \{ \tau, \tau' \}$. Since the right Perron--Frobenius eigenvector is positive, (i) holds if and only if $u=\tau$. This shows (i)$\Leftrightarrow$(ii).
\end{proof}

\begin{example}For each $m \in \NN$ and $n \in \ZZ_{\geq 0}$, the substitution
\[
\mu:\begin{cases}
  \tta \to\tta^{m+n}\ttb^m \\
  \ttb \to \tta^m\ttb^n
\end{cases}
\]
is a primitive substitution with incidence matrix
\[
M_\mu= \begin{bmatrix} m+n &amp; m \\ m &amp; n \end{bmatrix} \,.
\]
This family of substitutions, and all their permutations such that $\mu(\tta)$ starts with $\tta$, give all the substitutions with fixed words $\ttw \in \Wa$ satisfying
\begin{equation}\label{eq-r1}
\lim_{n\to\infty} \frac{r(n)}{n} =1 \,,
\end{equation}
while all the permutations of these $\mu(\tta)$ and $\mu(\ttb)$ with the property that $\mu(\ttb)$ starts with $\ttb$ yield all the substitutions with fixed words $\ttw \in \Wb$ satisfying \eqref{eq-r1}.\exend
\end{example}

Now, we discuss the binary words satisfying $r(n)=n+1$, and then the generalization $r(n)=n+j$ for any $j$. Since $r(n)$ does not vanish, we must have $j \geq0$. On the other hand, for $j \geq 0$, the sequence $r(n)=n+j$ is a strictly increasing sequence of positive integers, hence there exists a unique $\ttw$ such that $r(n)=n+j$.

We start this discussion with the following corollaries of Theorem \ref{thm-fib}.

\begin{theorem}\label{thm:fibplusone}
Let $\tt f$ be the Fibonacci word and $\ttw = D (\tt f)$ be the Fibonacci word with the initial $\tta\ttb$ deleted. Then, $r_\ttw(n)=n+1$ for all $n$.
\end{theorem}

\begin{theorem}\label{thm:fibk} Let $\ttw_k = D^k(\ttf)$, the word obtained from the Fibonacci by deleting the first $k$ $\tta$'s and the first $k$ $\ttb$'s. Then, there exists some $N=N(k)$ such that, for all $n&gt;N$, $r_{\ttw_k}(n)=n+k$.
\end{theorem}

Now, the word $D^2(\ttf)$ has $r(n)=n+2$ for all $n \geq 2$ and $r(1)=2$. Moreover, we show below that $D^k(\ttf)$ is not a fixed point of a primitive substitution for any $k\geq 1$.

We now show that $\ttw= D(\ttf)$  can be obtained from Fibonacci via a different process. In particular, we get that two completely unrelated processes applied to the Fibonacci word lead to the same result.

\begin{theorem}[The Fibonacci switch]
Let $\mu: \Sigma \to \Sigma^{*}$ be defined by $\mu(\tta)=\tta\tta\ttb$ and $\mu(\ttb)=\tta\ttb$.
Next, split the Fibonacci word $\ttf$ into level-$2$ supertiles, replace each level-$2$ supertile $\ttA_2=\tta\ttb\tta$ by $\mu(\tta)=\tta\tta\ttb$, and keep each level-$2$ supertile $\ttB_2=\tta\ttb= \mu(\ttb)$ unchanged. Let
\[
\ttw=\underbrace{\tta\tta\ttb}_{\mu(\tta)}\underbrace{\tta\ttb}_{\mu(\ttb)}\underbrace{\tta\tta\ttb}_{\mu(\tta)} \underbrace{\tta\tta\ttb}_{\mu(\tta)}\underbrace{\tta\ttb}_{\mu(\ttb)}\underbrace{\tta\tta\ttb}_{\mu(\tta)}\underbrace{\tta\ttb}_{\mu(\ttb)}\underbrace{\tta\tta\ttb}_{\mu(\tta)}  \cdots
\]
be the word obtained via this Fibonacci switch. Then $\ttw = \mu(\ttf) = D(\ttf)$.
\end{theorem}

\begin{proof}
Consider the $n$-th letter in the Fibonacci word $\ttf$. Let us compare the switches in
\begin{align*}
\ttw&amp;=\underbrace{\tta\tta\ttb}_{\mu(\tta)}\underbrace{\tta\ttb}_{\mu(\ttb)}\underbrace{\tta\tta\ttb}_{\mu(\tta)} \underbrace{\tta\tta\ttb}_{\mu(\tta)}\underbrace{\tta\ttb}_{\mu(\ttb)}\underbrace{\tta\tta\ttb}_{\mu(\tta)}\underbrace{\tta\ttb}_{\mu(\ttb)}\underbrace{\tta\tta\ttb}_{\mu(\tta)}  \cdots \\
\ttf&amp;= \underbrace{\tta\ttb\tta}_{\ttA_2}\underbrace{\tta\ttb}_{\ttB_2}\underbrace{\tta\ttb\tta}_{\ttA_2} \underbrace{\tta\ttb\tta}_{\ttA_2}\underbrace{\tta\ttb}_{\ttB_2}\underbrace{\tta\ttb\tta}_{\ttA_2}\underbrace{\tta\ttb}_{\ttB_2}\underbrace{\tta\ttb\tta}_{\ttA_2}  \cdots
\end{align*}
Here, the supertiles we are comparing are
\[
\ttA_2=\tta\ttb\tta \leftrightarrow \mu(\tta) = \tta\tta\ttb \qquad\mbox{and}\qquad
\ttB_2= \tta \ttb  \leftrightarrow \mu(\ttb) = \tta\ttb.
\]
Each of these four supertiles contains exactly one $\ttb$, and the order of $\ttA_2$ and $\ttB_2$ ($\mu(\tta)$ and $\mu(\ttb)$) is the same as the order of letters in the Fibonacci word. Whenever an $\ttA_2$ supertile appears, then the position of the corresponding $\ttb$ in $\mu(\tta)$ increases by 1. Whenever a $\ttB_2$ supertile appears, then the position of the corresponding $\ttb$ in $\mu(\ttb)$ stays the same. It follows that
\begin{displaymath}
p_{\ttb,\ttw}(n) =
\begin{cases}
p_{\ttb, \ttf}(n)+1,    &amp;\text{if the $n$th letter in $\ttf$ is $\tta$;}    \\
p_{\ttb, \ttf}(n),     &amp;\text{if the $n$th letter in $\ttf$ is $\ttb$.}
\end{cases}
\end{displaymath}
Next, recall that
\[
\ttA_2=\ttA_1\ttB_1=(\tta \ttb) \tta    \leftrightarrow \mu(\tta) = \tta\tta\ttb \qquad\mbox{and}\qquad
\ttB_2=\ttA_1 =\tta \ttb    \leftrightarrow \mu(\ttb) = \tta\ttb.
\]
Looking at the position changes of $\tta$'s, we see immediately that the $\tta$ in $\ttB_1$ moves one position back in $\ttw$, and the $\tta$ in $\ttA_1$ stays in the same position. Thus,
\begin{displaymath}
p_{\tta,\ttw}(n) =
\begin{cases}
p_{\tta, \ttf}(n), &amp;\text{if the $n$th letter in $\ttf$ is $\tta$;} \\
p_{\tta, \ttf}(n) -1, &amp;\text{if the $n$th letter in $\ttf$ is $\ttb$.}
\end{cases}
\end{displaymath}
This implies that $\ttw$ has relative position function $r_{\ttw}(n)=r_{\ttf}(n)+1 =n+1$. Thus, by uniqueness and Theorem \ref{thm:fibplusone}, $\ttw = \mu(\ttf) = D(\ttf)$.
\end{proof}

We now prove our second and final main result of this section---combining the property of aperiodicity/non-triviality with the generalization of the properties in Theorem~\ref{thm-fib}(a) and Theorem~\ref{thm-fib}(b) uniquely identifies the Fibonacci word $\ttf$.

\begin{theorem}\label{fib-uni} Let $\ttw \in \Wa$ be a word. Then, both $\Delta p_\tta$ and $\Delta p_\ttb$ are codings of $\ttw$ if and only if either $\ttw=\ttf$ or $\ttw=(\tta\ttb)^\omega$.

In particular, $\ttf$ is the only aperiodic word in $\Wa$ that is isomorphic to both $\Delta p_\tta$ and $\Delta p_\ttb$.
\end{theorem}

\begin{proof}
Before proceeding, we summarize our strategy. First, we show that any word starting with $\tta \tta$ and satisfying the given conditions must consist of $\tta$'s only. Therefore, we can focus on words starting with $\tta \ttb$. This means that $\Delta p_\tta(1)$ and $\Delta p_\tta(2)$ uniquely identify $k$ and $l$ and $\Delta p_\ttb(1)$ and $\Delta p_\ttb(2)$ uniquely identify $m$ and $n$. To obtain one of these, we need to look at the first few bits of $\ttw$. Finally, knowing one of the pairs $(k,l)$ or $(m,n)$ and that $\ttw \in \tta \ttb \W$, we can reconstruct $\ttw$. Let us proceed along these lines.

Toward a contradiction, assume that $\ttw$ starts with $\tta \tta$. Then, under the coding $\tta \to k$, the sequence $\Delta p_\tta$ starts with $k,k$. Since $\Delta p_\tta(1)=1$, we get that $k=1$, hence $\Delta p_\tta$ starts with $1,1$.
A short induction proves that for each $n$, $\ttw$ starts with $\tta^n$, and so  $\Delta p_\tta(1)$ starts with $n$ repeated $1$s.
Therefore, $\ttw = \tta^\omega \notin \Wa$, a contradiction.

Now, we look at six cases.

\textbf{Case 1.} Suppose $\ttw=\tta \ttb \tta \tta \cdots$. Under the coding $(\tta,\ttb)=(k,l)$, the sequence $\Delta p_\tta$ starts with $k,l,k,k$. Since $\Delta p_\tta(1)=2$ and  $\Delta p_\tta(2)=1$, we get that $(k,l)=(2,1)$. For simplicity, let $\ttw = \ell_0 \ell_1 \ell_2 \cdots$ and $\ttf = f_0 f_1 f_2 \cdots$. We prove by induction that $f_j = \ell_j$ for all $j \in \ZZ_{\geq 0}$. By hypothesis, $f_j = \ell_j$ for $0\leq j\leq 3$. Next, suppose $f_j = \ell_j, 0\leq j\leq r$. Then, $\Delta p_{\tta,\ttw}(j) = \Delta p_{\tta,\ttf}(j)$, for $0\leq j\leq r$. As $p_{\tta, \ttw}(1)=0=p_{\tta, \ttf}(1)$, it follows that the positions of the first $r+1$ $\tta$'s in $\ttw$ and $\ttf$ agree. Hence, the bits of $\ttw$ and $\ttf$ are the same up to position $p_{\tta,\ttw}(r+1)=p_{\tta,\ttf}(r+1)$. Now, since $p_{\tta,\ttf}(2)=2$, we trivially get that $p_{\tta, \ttf}(r+1)=p_{\tta,\ttw}(r+1)\geq r+1$. Therefore $\ell_{r+1}=f_{r+1}$.

\textbf{Case 2.} Suppose that $\ttw=\tta \ttb \tta \ttb \tta\cdots$. Then, the sequence $\Delta p_\tta$ starts with $k,l,k,l,k$, hence $k=l=2$. This shows that $\Delta p_\tta(j)=2$ for all $j\geq1$. Thus $\ttw = (\tta \ttb)^\omega$.

\textbf{Case 3.} Suppose $\ttw=\tta \ttb \tta \ttb \ttb\cdots$.  Then, the sequence $\Delta p_\ttb$ starts with $m,n,m,n,n$, which gives $(m,n)=(2,1)$, hence $\Delta p_\ttb$ starts with $2,1,2,1,1$. Since $p_\ttb(1)=1$, the first six positions of $\ttb$ in $\ttw$ are $1,3,4,6,7,8$, so $\ttw = \tta \ttb \tta \ttb \ttb \tta \ttb \ttb \ttb \cdots$, which implies that $\Delta p_\tta$ starts with $2,3,m$ with $m\geq 4$, a contradiction to the hypothesis that $\Delta p_\tta$ is obtained from $\ttw$ by under a coding $(\tta,\ttb)=(k,l)$.

\textbf{Case 4.} Suppose $\ttw=\tta \ttb \ttb \tta \tta\cdots$. Here, $\Delta p_\tta(1)=3$ and $\Delta p_\tta(2)=1$, which gives that $(k,l)=(3,1)$, hence $\Delta p_\tta$ starts with $3,1,1,3,3$. Since $p_\tta(1)=0$, the first six positions of $\tta$ in $\ttw$ are $0,3,4,5,8, 11$, so $\ttw = \tta \ttb \ttb \tta \tta \tta \ttb \ttb \tta \ttb \ttb \tta \cdots$. This immediately implies that $\Delta p_\ttb$ starts with $1, 4 , 1, 2$, which contradicts the fact that $\Delta p_\ttb$ is obtained from $\ttw$ by under a coding $(\tta,\ttb)=(m,n)$.

\textbf{Case 5.} Suppose $\ttw=\tta \ttb \ttb \tta \ttb\cdots$. In this case, $\Delta p_\ttb(1)=1$ and $\Delta p_\ttb(2)=2$, which implies that $(m,n)=(1,2)$, hence $\Delta p_\ttb$ starts with $1,2,2,1,2$. Since $p_\ttb(1)=1$, the first six positions of $\ttb$ in $\ttw$ are $1,2,4,6,7,9$, so $\ttw = \tta \ttb \ttb \tta \ttb \tta \ttb \ttb \tta \ttb \cdots$. This immediately implies that $\Delta p_\tta$ starts with $3, 2, 3$, which contradicts the fact that $\Delta p_\tta$ is obtained from $\ttw$ by under a coding $(\tta,\ttb)=(k,l)$.

\textbf{Case 6.} Finally, suppose $\ttw=\tta \ttb\ttb\ttb\cdots$. This implies that $\Delta p_\ttb$ starts with $1,1$. Therefore, $\Delta p_\ttb$ is obtained from $\ttw$ under the coding $(\tta,\ttb)=(1,1)$, which implies that $\Delta p_\ttb(n)=1$ for all $n$. In particular, $\tta$ appears in $\ttw$ only on the first position, which contradicts $\ttw \in \Wa$.

This completes the proof.
\end{proof}

\begin{remark} For each pair $(k,l)\in \NN \times \NN$ with $k\neq 1$, there exists a unique word $\ttw_{k,l} \in \tta\mathcal{W}$ with the property that $\Delta p_\tta$ is obtained from $\ttw_{k,l}$  under the coding $(\tta,\ttb)=(k,l)$.\exend
\end{remark}

Combining Theorem~\ref{fib-uni} with the reflection operator, we obtain

\begin{corollary} Let $\ttw \in \Wb$ be a word. Then, both $\Delta p_\tta$ and $\Delta p_\ttb$ are codings of $\ttw$ if and only if either $\ttw=\bar{\ttf}$ or $\ttw=(\ttb\tta)^\omega$.

In particular, $\bar{\ttf}$ is the only aperiodic word in $\Wb$ that is isomorphic to both $\Delta p_\tta$ and $\Delta p_\ttb$.
\end{corollary}

Since the Fibonacci word $\ttf$ is isomorphic via reflection to $\bar{\ttf}$, we have the following.

\begin{corollary} The Fibonacci word $\ttf$ is, up to isomorphism, the only aperiodic binary word that is isomorphic to the difference sequence of the position function of each letter.
\end{corollary}

Now, we consider a variant of the Fibonacci substitution.

\begin{definition} We call the substitution,
\[
\mu_F':\begin{cases}
\tta\to \ttb\tta \\
\ttb\to\tta \,,
\end{cases}
\]
the \emph{backwards Fibonacci substitution}, or the \emph{iccanobiF substitution}.
\end{definition}

The substitution $\mu_F'$ does not have a fixed point, but $(\mu_F')^2$ has two fixed points, one starting with $\tta$, and one starting with $\ttb$. We look at the fixed points of $(\mu_F')^2$ and their relative position functions. To explicitly calculate these fixed points, we relate $\mu_F'$ to the Fibonacci substitution $\mu_F$.

The substitutions $\mu_F$ and $\mu_F'$ are conjugate \cite[Remark~4.6]{TAO}. More precisely, for all words $\ttw\in\Sigma^*$, we have $\mu_F(\ttw) \tta = \tta \mu_F'(\ttw)$. Our immediate goal is to show that we can relate $\mu_F^n$ and $(\mu_F')^n$ via conjugation relations. Noting that for $n\geq 1$, we have $\mu_F^n(\ttb)= \mu_F^{n-1}(\tta)$ and $(\mu_F')^n(\ttb)= (\mu_F')^{n-1}(\tta)$, it suffices to relate $\mu_F^n(\tta)$ to $(\mu_F')^n(\tta)$. We achieve this in the following result.

\begin{proposition}\label{prop:rev-fib} For all $n \geq 1$, we have both
\begin{enumerate}
\item[(a)] $\tta \ttb \mu_F^{2n}(\tta)=(\mu_F')^{2n}(\tta) \ttb \tta$, and
\item[(b)] $\ttb \tta \mu_F^{2n-1}(\tta)=(\mu_F')^{2n-1}(\tta) \tta \ttb$.
\end{enumerate}
\end{proposition}

\begin{proof}
We prove both by induction.

{\bf (a)} For $n=1$, we have $\tta \ttb \mu_F^{2}(\tta)=\tta \ttb \tta \ttb \tta = \left(\mu_F'\right)^{2}(\tta) \ttb \tta$. Now suppose the result holds for some $n\geq 1$. Then
\begin{align*}
\tta \ttb \mu_F^{2n+2}(\tta)&amp;=\tta \ttb \mu_F^{2n}(\tta \ttb \tta ) =  \tta \ttb \mu_F^{2n}(\tta) \mu_F^{2n-1}(\tta) \mu_F^{2n}(\tta) \\
&amp;= (\mu_F')^{2n}(\tta) \ttb \tta  \mu_F^{2n-1}(\tta) \mu_F^{2n}(\tta) = (\mu_F')^{2n}(\tta)  (\mu_F')^{2n-1}(\tta) \tta \ttb  \mu_F^{2n}(\tta) \\
&amp;= (\mu_F')^{2n}(\tta)  (\mu_F')^{2n-1}(\tta)  (\mu_F')^{2n}(\tta)  \ttb \tta = (\mu_F')^{2n}(\tta \ttb \tta) \ttb \tta = (\mu_F')^{2n+2}(\tta) \ttb \tta \,.
\end{align*}

{\bf (b)} For $n=1$, we have $\ttb \tta \mu_F^{1}(\tta)=\ttb \tta \tta \ttb = \left(\mu_F'\right)^{1}(\tta) \tta \ttb$. Now suppose the result holds for some $n\geq 1$. Then
\begin{align*}
\ttb \tta \mu_F^{2n+1}(\tta)&amp;=\ttb \tta \mu_F^{2n-1}(\tta \ttb \tta ) =  \ttb \tta \mu_F^{2n-1}(\tta) \mu_F^{2n-2}(\tta) \mu_F^{2n-1}(\tta) \\
&amp;= (\mu_F')^{2n-1}(\tta) \tta \ttb  \mu_F^{2n-2}(\tta) \mu_F^{2n-1}(\tta) = (\mu_F')^{2n-1}(\tta)  (\mu_F')^{2n-2}(\tta) \ttb \tta  \mu_F^{2n-1}(\tta) \\
&amp;= (\mu_F')^{2n-1}(\tta)  (\mu_F')^{2n-2}(\tta)  (\mu_F')^{2n-1}(\tta)  \tta \ttb = (\mu_F')^{2n}(\tta \ttb \tta) \ttb \tta = \left(\mu_F'\right)^{2n+2}(\tta) \tta \ttb.\ \qedhere
\end{align*}
\end{proof}

Similarly, we have the following result.

\begin{proposition} For all $n \geq 1$, we have both
\begin{itemize}
\item[(a)] $\tta \ttb \mu_F^{2n+1}(\ttb)=\left(\mu_F'\right)^{2n+1}(\ttb) \ttb \tta$, and
\item[(b)] $\ttb \tta \mu_F^{2n}(\ttb)=\left(\mu_F'\right)^{2n}(\ttb) \tta \ttb$.
\end{itemize}
\end{proposition}

As a consequence, we can understand the fixed points of $(\mu_F')^2$.

\begin{theorem} Let $\mu_F'$ be the iccanobiF substitution and $\ttf$ be the Fibonacci word. Then, the one-sided fixed points of $(\mu_F')^{2}$ (starting with $\tta$ or $\ttb$) exist, and satisfy
\[
\lim_{n\to\infty} (\mu_F')^{2n} (\tta) ={\rm Pre}_{\tta \ttb } (\ttf) \in \Wa\qquad\mbox{and}\qquad
\lim_{n\to\infty} (\mu_F')^{2n} (\ttb) ={\rm Pre}_{\ttb \tta } (\ttf)  \in \Wb\,.
\]
Moreover, we have both
\begin{displaymath}
r_{{\rm Pre}_{\tta \ttb } (\ttf)}(n)= \begin{cases}
    1, &amp; \text{if $n=1$;}  \\
    n-1, &amp; \text{if $n&gt;1$;}
\end{cases}
\qquad
\mbox{and}
\qquad
r_{{\rm Pre}_{\ttb \tta } (\ttf)}(n)=
\begin{cases}
    -1, &amp; \text{if $n=1$;}  \\
    n-1, &amp; \text{if $n&gt;1$.}
\end{cases}
\end{displaymath}
\end{theorem}

\begin{proof}
By Proposition~\ref{prop:rev-fib}, we have $(\mu_F')^{2n}(\tta) \ttb \tta = \tta \ttb \mu_F^{2n}(\tta)$. Letting $n$ tend to infinity, we get $\tta \ttb \ttf = {\rm Pre}_{\tta \ttb}(\ttf)$.
Similarly, $(\mu_F')^{2n-1}(\tta) \tta \ttb = \ttb \tta \mu_F^{2n-1}(\tta)$, which gives $\ttb \tta \ttf = {\rm Pre}_{\ttb \tta}(\ttf)$. The remaining claims follow immediately.
\end{proof}

\begin{remark}\label{remreferee} The Fibonacci word $\ttf$ is the coding of the intercept $1/\tau^2$ under the $2$-interval exchange $I_\tta=[0,1/\tau)$ and $I_\ttb=[1/\tau,1]$. From this point of view, it is clear that ${\rm Pre}_{\tta \ttb}(\ttf)$ and ${\rm Pre}_{\ttb\tta}(\ttf)$ are codings of intercepts $0$ and $1$, respectively, under the same interval exchange. Hence, it is clear that both are fixed by the same substitution; see Dekking \cite{D2018}.\exend
\end{remark}

We now note a result, which shows what one can obtain words $\ttw$ from the Fibonacci words such that eventually $r_\ttw(n)=n+j$ for all values of $j$.

\begin{theorem} Let $w$ be any equilibrious word of length $2j$ and let $\ttw_j = {\rm Pre}_{w} (\ttf)$. Then, for all $n&gt;j$ we have $r_{\ttw_j}(n)=n-j$.

Moreover, if $w=(\tta \ttb)^j$, then $r_{\ttw_j}(1)=r_{\ttw_j}(2)=\cdots =r_{\ttw_j}(j)=1$.
\end{theorem}

We now turn to the one-sided fixed points of the family of substitutions $\mu$ on $\Sigma$ with the property that $\mu(\tta)$ and $\mu(\ttb)$ contain one $\ttb$ in total. We add two further restrictions on this family. First, if the $\ttb$ appears in $\mu(\ttb)$, then $\tta \to \mu(\tta)$ generates the 1-sided word containing only $\tta$, which is not interesting. Therefore, we assume that the single $\ttb$ appears in $\mu(\tta)$. In this case, the only way of getting a fixed point for $\mu$, and not only for one of its larger powers, is if $\mu(\tta)$ starts with $\tta$---this is our second restriction. Therefore, we consider the following family of substitutions.

\begin{definition}The \emph{extended Pisa family of substitutions} is given by $\sigma_{k,l,m}$ with $k, m \geq 1$ and $l \geq 0$, where
\[
\sigma_{k,l,m}:
\begin{cases}\tta\to\tta^k\ttb\tta^l  \\
\ttb\to\tta^m \,.
\end{cases}
\]
\end{definition}

Note that, in the case $l=0$ and $m=1$, the substitutions $\sigma_{k,0,1}$ are called the \emph{noble means substitutions} \cite[Rem.\ 4.7]{TAO} \cite{EMM}, and $\sigma_{1,0,2}$ is the \emph{period-doubling substitution} \cite[Sect.\ 4.5.1]{TAO}.

For general $k$, $l$, and $m$, the incidence matrix is
\[
M=M_{\sigma_{k,0,1}}= \begin{bmatrix}
k+l &amp; 1 \\
m   &amp;0
\end{bmatrix} \,.
\]
Since $M^2&gt;0$, $M$ is a primitive matrix. Its two distinct eigenvalues are
\[
\lambda_{\pm}= \frac{(k+l) \pm  \sqrt{(k+l)^2+4m}}{2} \,,
\]
which only depend on the two parameters $k+l$ and $m$. Since the product of eigenvalues is $\det(M)=-m&lt;2$, we have $\lambda_- &lt;0$. Thus, the substitution is Pisot (see Sing \cite{Sing} for definition and properties) if and only if $m &lt; (k+l)+1$. When $m=(k+l)+1$, the eigenvalues are $\lambda_+=(k+l)+1$ and $\lambda_-=-1$.

We now prove a result, which significantly extends the results on the Fibonacci substitution, $(k,l,m)=(1,0,1)$.

\begin{theorem}\label{thm:6} Let $k, m \geq 1$, $l \geq 0$, and $\ttw$ be the one-sided fixed point of $\sigma_{k,l,m}$. Then,
\[
p_{\ttb}(n)= m\cdot p_\tta(n) + (k+l+1-m)  n + m-l-1\,.
\]
In particular,
\begin{equation}\label{eq-r}
r(n)= (m-1) \cdot p_\tta(n) + (k+l+1-m)  n + m-l-1.
\end{equation}
Moreover, $\ttw$ is the unique word satisfying \eqref{eq-r}.
\end{theorem}

\begin{proof} We split $\ttw$ into level-$1$ supertiles $\ttA=\tta^k\ttb\tta^l$ and $\ttB=\tta^m$, so that
\[
\ttw =\underbrace{\tta \cdots }_{X_0=\ttA} \underbrace{\tta \cdots }_{X_1}  \underbrace{\tta \cdots }_{X_2} \ \cdots,
\]
where $X_i\in\{\ttA,\ttB\}$ for each $i\geq 0$. To calculate the position $p_\ttb(n)$ of the $n$-th $\ttb$, we note that each $\ttA$ contains exactly one $\ttb$ and each $\ttB$ contains no $\ttb$. This means that the $n$-th $\ttb$ appears in the $n$-th $\ttA$ supertile. For simplicity, set $j:=p_\tta(n)$, so that the $n$-th $\ttb$ appears inside $X_j$. Now, there are $j$ supertiles before $X_j$. Since $X_j$ is the $n$-th $\ttA$ supertile, there are exactly $n-1$ supertiles $\ttA$ before $X_j$. The remaining $j-n+1$ supertiles are $\ttB$ supertiles. Since each $\ttA$ supertile contains $k+l+1$ letters and each $\ttB$ supertile contains $m$ letters, there are
\[
(n-1) (k+l+1)+(j-n+1) m
\]
letters before the supertile $X_j$. Further, the single $\ttb$ is in position $k+1$ inside $X_j$. Remembering that our index count starts at $0$, for $\ttw=\ell_0\ell_1 \cdots$, we have
\begin{align*}
p_\ttb(n)&amp;= (n-1) (k+l+1)+(j-n+1) m+ k   \\
&amp;=n (k+l+1)+(p_\tta(n)-n+1) m+ k -(k+l+1)\\
&amp;= m \cdot p_\tta(n) + (k+l+1-m)  n + m-l-1 \,,
\end{align*}
which proves the first claim as well as \eqref{eq-r}.

Lastly, we prove uniqueness of $\ttw$ satisfying \eqref{eq-r}. Note that this is not a trivial fact, since, in general, $r(n)$ uniquely determines $\ttw$ only when it is a specific function of $n$. Suppose $\ttw' \in \mathcal W$ has a relative position function satisfying (\ref{eq-r}) for some $k,m\geq 1$ and $l\geq 0$. Since $p_{\tta,\ttw'}(n) \geq n$,
\begin{align*}
p_{\ttb,\ttw'}(n) &amp;= m \cdot p_{\tta,\ttw'}(n) + (k+l+1-m)  n + m-l-1 \\
&amp;\geq p_{\tta,\ttw'}(n) + (m-1)n + (k+l+1-m)n + m-l-1 \\
&amp; = p_{\tta,\ttw'}(n) + kn + ln + m -l -1 \\
&amp; = p_{\tta,\ttw'}(n) + kn + l(n-1) + (m-1) &gt; p_{\tta,\ttw'}(n)\,.
\end{align*}
This implies that $p_{\tta,\ttw'}(1) = 0$. Now, we reconstruct in the straightforward manner, where the $(n+1)$-th $\tta$ is placed in the first unoccupied spot and the $(n+1)$-th $\ttb$ is placed further along according to the formula. Thus, there is only one word that is constructed from these formulas, which must be the fixed point of $\sigma_{k,l,m}$.
\end{proof}

\begin{corollary} Let $k, m \geq 1$, $l \geq 0$, and $\ttw$ be the one-sided fixed point of $\sigma_{k,l,m}$. Then,
\begin{equation*}
 r(n) = \left(\frac{m-1}{m}\right) p_{\ttb}(n) +\left(\frac{k+l+1-m}{m}\right) n +\frac{ m-l-1}{m} \,.
\end{equation*}
\end{corollary}

Now, we illustrate this result with a few examples.

\begin{example}
Recall from above, the family of noble means substitutions are given by $\sigma_{k,0,1}$. The members of this family behave like the Fibonacci substitution. In particular, for each fixed point, we have $r(n) = kn$. \exend
\end{example}

\begin{example}
The period-doubling substitution $\mu_{\rm pd}$ is given by
\[
\mu_{\rm pd}:=\sigma_{1,0,2}:
\begin{cases}
    \tta \rightarrow \tta \ttb \\
    \ttb \rightarrow \tta \tta\, ,
\end{cases}
\]
which has the unique one-sided fixed point
\[
\ttw = \lim_{n\to\infty}\mu_{\rm pd}^n(\tta)=\lim_{n\to\infty} \sigma_{1,0,2}^n(\tta) = \tta\ttb\tta\tta\tta\ttb\tta\ttb\tta\ttb\tta\tta\cdots.
\]
By Theorem \ref{thm:6}, we have $p_{\ttb}(n) = 2p_{\tta}(n) + 1$, and
\[
r(n) = p_{\tta}(n)+1 = \frac{1}{2}\cdot p_{\ttb}(n) + \frac{1}{2}.
\]
Analogous to the noble means family, the period-doubling substitution and its fixed point is part of a well-behaved family, specifically,
\[
\sigma_{k,0,k+1}: \begin{cases}
\tta \to \tta^{k}\ttb\\
\ttb \to \tta^{k+1}\, ,
\end{cases}
\] where $p_{\ttb}(n) = (k+1)p_{\tta}(n) + 1$ and $r(n) = k\cdot p_{\tta}(n)+1 = \left(\frac{k}{k+1}\right)p_{\ttb}(n) + \frac{k}{k+1}$.\exend
\end{example}

\begin{example}
The ``mixture/addition" of Fibonacci and period-doubling is most interesting. Here, let $\ttw$ be the one-sided fixed point of
\[
\sigma_{2, 0, 2}
:\begin{cases}
\tta\to \tta \tta \ttb \\
\ttb\to\tta \tta.
\end{cases}
\]
Then, by Theorem~\ref{thm:6}, $p_\ttb(n) = 2\cdot p_\tta(n) + n + 1$ and $r(n) = p_{\tta}(n)+ n+ 1$. Further, since each level-$1$ supertile contains exactly two $\tta$'s, which are consecutive, we can relabel this substitution using $(\alpha,\beta):=(\tta\tta,\ttb)$. The relabeled fixed word is the fixed word $\ttw'$ of the substitution $\sigma'$ satisfying
\[
\sigma'(\alpha)= \sigma_{2,0,2}(\tta\tta) = \tta\tta\ttb\tta\tta\ttb =  \alpha \beta \alpha \beta \quad\mbox{and}\quad
\sigma'(\beta)= \sigma_{2,0,2}(\ttb) = \tta\tta = \alpha\,.
\]
Moreover, the relation $p_{\ttb, \ttw}(n)=2\cdot p_{\tta, \ttw}(n) + n+1$ implies that
\[
p_{\beta,\ttw'}(n)=p_{\tta, \ttw}(n)+n+1 \,,
\]
so that
\[
r_{\ttw}(n)=p_{\ttb, \ttw}(n)-p_{\tta,\ttw}(n)=p_{\beta, \ttw'} (n),
\]
which, we find, is an interesting relationship between these infinite words.\exend
\end{example}

To finish this section, we obtain the letter frequencies and the mean values of the the (relative) position functions for the entire extended Pisa family, which come as a generalization of the Fibonacci example. First, note that the Perron--Frobenius eigenvalue of $M_{\sigma_{k,l,m}}$, as mentioned above, is $\tau_{k+l,m}$ where
\[
\tau_{j,m}:=\frac{j + \sqrt{j^2+4m}}{2},
\]
and the right Perron--Frobenius eigenvector is $[\tau_{k+l,m} \
1]^T$. The characteristic polynomial of $M_{\sigma_{k,l,m}}$ is $X^2-(k+l)X-m$, so
\[
\tau_{k+l,m}^2=(k+l)\tau_{k+l,m}+m \,.
\]
In particular,
\[
\frac{1}{\tau_{k+l,m}}= \frac{\tau_{k+l,m}-(k+l)}{m} \,.
\]
A direct application of Lemma~\ref{sub:asympt} and \eqref{eq-r} gives
\[
  {\rm Freq}(\tta) =\frac{\tau_{k+l,m}}{\tau_{k+l,m}+1}=\frac{\tau_{j,m}-m}{k+l+1-m}, \qquad
  {\rm Freq}(\ttb) =\frac{1}{\tau_{k+l,m}+1}=\frac{k+l+1-\tau_{k+l,m}}{k+l+1-m} \,,
\]
\[
\lim_{n\to\infty} \frac{p_\tta(n)}{n}=1+\frac{\tau_{k+l,m}-(k+l)}{m}, \qquad
  \lim_{n\to\infty} \frac{p_\ttb(n)}{n}=\tau_{k+l,m}\,,
  \] and
  \[
  \lim_{n\to\infty} \frac{r(n)}{n}=\frac{(m-1)\tau_{k+l,m}+k+l}{m}= (m-1)\cdot \lim_{n\to\infty} \frac{p_\tta(n)}{n} + (k+l+1-m) \,.
\]

Analogous to the proofs of Theorem~\ref{thm-2} and Lemma~\ref{lem2a1}, we establish the following.

\begin{proposition} Let $j$ and $m$ be two positive integers and let $\mu$ be a primitive binary substitution with incidence matrix $M_\mu$. Let $\ttw$ be a fixed point of the substitution. Then, the following are equivalent.
\begin{itemize}
  \item[(i)]  ${\rm Freq}(\tta) =\frac{\tau_{j,m}-m}{j+1-m} $.
  \item[(ii)] ${\rm Freq}(\ttb) =\frac{j+1-\tau_{j,m}}{j+1-m}$.
  \item[(iii)]$\displaystyle{\lim_{n\to\infty} \frac{p_\tta(n)}{n}= 1+\frac{\tau_{j,m}-j}{m}}$.
  \item[(iv)] $\displaystyle{\lim_{n\to\infty} \frac{p_\ttb(n)}{n}=\tau_{j,m}+1}$.
  \item[(v)]  $\displaystyle{\lim_{n\to\infty} \frac{r(n)}{n}=\frac{(m-1)\tau_{j,m}+j}{m}} $.
  \item[(vi)] $\displaystyle{\lim_{n\to\infty} \frac{r(n)}{n}= (m-1) \lim_{n\to\infty} \frac{p_\tta(n)}{n} + (j+1-m)}$.
  \item[(vii)] $[\tau_{j,m} \ 1]^T$ is a right eigenvector for $M_\mu$.
  \end{itemize}
\end{proposition}

\begin{proof}
Let $[u \ 1]^T$ be the right Perron--Frobenius eigenvector for $M_\mu$. Then, $u&gt;0$. The discussion above shows that $u= \tau_{j,m}$ is the unique solution to each of the linear equations
\[
\frac{u}{u+1} =\frac{\tau_{j,m}}{\tau_{j,m}+1}=\frac{\tau_{j,m}-m}{j+1-m},\qquad
  \frac{1}{u+1}=\frac{1}{\tau_{j,m}+1}=\frac{j+1-\tau_{j,m}}{j+1-m},
  \]
  \[
  1+\frac{1}{u}=1+\frac{\tau_{j,m}-j}{m},\quad\mbox{and}\quad
  u+1=\tau_{j,m}+1.
\]
Applying Lemma~\ref{sub:asympt} proves the equivalence of (i), (ii), (iii), (iv) and (vii).

Next, the quadratic equation
\[
\frac{u^2-1}{u}= \frac{(m-1)\tau_{j,m}+j}{m} \\
\]
has $u= \tau_{j,m}$ as one of the solutions. Since the product of the solutions is $-1$, it follows that $u= \tau_{j,m}$ is the only positive solution. So, Lemma~\ref{sub:asympt} gives the equivalence of (v) and (vii).

Also by Lemma~\ref{sub:asympt}, we have
\[
\lim_{n\to\infty} \frac{r(n)}{n}= (m-1) \lim_{n\to\infty} \frac{p_\tta(n)}{n} + (j+1-m),
\] if and only if
\[
\frac{u^2-1}{u}=(m-1)(1+\frac{1}{u})+ (j+1-m),
\] if and only if
\[
\frac{u^2-1}{u}=\frac{m-1}{u}+j,
\] if and only if $u^2-ju-m=0$, which, again, has the unique positive solution $u= \tau_{j,m}$. This finishes the proof.
\end{proof}

Finally, we have the following result.

\begin{theorem}\label{thm:Mform} Let $j$ and $m$ be two positive integers and let $M \in M_2(\ZZ)$.
\begin{itemize}
  \item[(a)] If $j^2+4m$ is not a perfect square, then $[\tau_{j,m} \
1]^T$ is a right eigenvector for $M$ if and only if there exist integers $s$ and $t$ such that
\[
M= \begin{bmatrix}
t+sj  &amp;ms  \\
s&amp;  t
\end{bmatrix}.
\]
  \item[(b)] If $j^2+4m=r^2$ for some $r \in \ZZ$, then $[\tau_{j,m} \
1]^T$ is a right eigenvector for $M$ if and only if there exist integers $s$, $t$, $u$, and $v$ such that $u(j+r)^2+2(v-s)(j+r)-4t=0$ and
\[
  M =\begin{bmatrix} s &amp; t \\  
  u &amp; v \end{bmatrix}.
\]
\end{itemize}
\end{theorem}

\begin{proof}
\textbf{(a)} ($\Leftarrow$). A short calculation yields
\begin{align*}
\begin{bmatrix}
t+sj  &amp;ms  \\
s&amp;  t
\end{bmatrix}
\begin{bmatrix}
\tau_{j,m} \\ 1
\end{bmatrix}&amp;=\begin{bmatrix}
(t+sj)\tau_{j,m} +sm   \\s\tau_{j,m}+t
\end{bmatrix}=\begin{bmatrix}
(s(j\tau_{j,m}+m )+t\tau_{j,m})   \\
s\tau_{j,m}+t
\end{bmatrix}\\
&amp;=\begin{bmatrix}
 (s\tau_{j,m}^2+t\tau_{j,m})   \\s\tau_{j,m}+t
\end{bmatrix}=\begin{bmatrix}
\tau_{j,m}(s\tau_{j,m}+t) \\ s\tau_{j,m}+t
\end{bmatrix}=( s\tau_{j,m}+t) \begin{bmatrix}
\tau_{j,m} \\ 1
\end{bmatrix},
\end{align*}
so $[\tau_{j,m} \ 1]^T$ is a right eigenvector for $M$.

($\Rightarrow$). Since $\tau_{j,m} \notin \QQ$, $\QQ(\tau_{j,m})$ is a degree two extension of $\QQ$, both (distinct) eigenvalues lie in this field, and $[\tau_{j,m}' \ 1]^T$ is another (linearly independent) eigenvector of $M$. Thus, for some integers $s$ and $t$, we have
\begin{align*}
M&amp;= \begin{bmatrix}
    \tau_{j,m} &amp; \tau_{j,m}' \\
    1 &amp; 1
\end{bmatrix} \begin{bmatrix}
    t+s\tau_{j,m} &amp; 0 \\
    0 &amp; t+s \tau_{j,m}'
\end{bmatrix}\begin{bmatrix}
    \tau_{j,m} &amp; \tau_{j,m}' \\
    1 &amp; 1
\end{bmatrix}^{-1} \\
&amp;=\frac{1}{(\tau_{j,m}-\tau_{j,m}')}\begin{bmatrix}
    (t+s\tau_{j,m} )\tau_{j,m} &amp; (t+s \tau_{j,m}')\tau_{j,m}' \\
t+s\tau_{j,m}  &amp; t+s \tau_{j,m}'
\end{bmatrix}  \begin{bmatrix}
    1 &amp; -\tau_{j,m}' \\
    -1 &amp; \tau_{j,m}
\end{bmatrix} \\
&amp;=  \frac{1}{\tau_{j,m}-\tau_{j,m}'}
\begin{bmatrix}
    (t+s\tau_{j,m} )\tau_{j,m} -(t+s \tau_{j,m}')\tau_{j,m}'  &amp; m(t+s\tau_{j,m}) - m(t+s \tau_{j,m}') \\
\left(( t+s\tau_{j,m})-(t+s \tau_{j,m}')\right)&amp;  -(t+s\tau_{j,m}) \tau_{j,m}'   +(t+s \tau_{j,m}') \tau_{j,m}
\end{bmatrix} \\
&amp;=\frac{1}{\tau_{j,m}-\tau_{j,m}'}
\begin{bmatrix}
( t+sj) (\tau_{j,m}  -\tau_{j,m}')  &amp;ms (\tau_{j,m} - \tau_{j,m}') \\
s(\tau_{j,m}- \tau_{j,m}')&amp;  t(\tau_{j,m}- \tau_{j,m}')
\end{bmatrix}=
\begin{bmatrix}
t+sj  &amp;ms  \\
s&amp;  t
\end{bmatrix}\,,
\end{align*}
which finishes the proof of (a).

\textbf{(b)}
We have $\tau_{j,m} ={(j + r)}/{2}$. A straightforward calculation shows that $[(j+r)/2, \ 1]^T$ is a right eigenvector for
\[
M= \begin{bmatrix}
s &amp; t \\
u &amp; v
\end{bmatrix}\] if and only if $u(j+r)^2+2(v-s)(j+r)-4t=0$, which is the desired result.
\end{proof}

\section{Substitutions with exactly, or asymptotically,\\ linear relative position function}\label{sec:linear}

In this section, we first consider words $\ttw$ such that $r(n)$ is a linear function, then consider the asymptotically linear case. We start with the following result, which follows immediately from results of the previous sections.

\begin{theorem} The following hold.
\begin{itemize}
    \item[(a)] For all $j \geq 1$, the periodic word $\ttw =(\tta^j\ttb^j)^\omega$ satisfies $r(n)= j$.
\item[(b)] Let $k$ and $j$ be integers satisfying $0 \leq j \leq k-1$, and let $\ttw$ be the one-sided fixed point of the Pisa substitution $\sigma_{k-j, j, 1}$. Then $r(n)=k  n - j$.
\item[(c)] Let $k\geq 0$ be an integer, and let $\ttw$ be the one-sided fixed point of the Pisa substitution $\sigma_{1, k-1, 1}$. Then, $
r_{D(\ttw)}(n)=k  n +1$.
\end{itemize}
\end{theorem}

The above result covers all the arithmetic progressions $kn+j$ for $-1\leq j \leq k-1$. Note that $kn+j$ cannot occur for $j=-k$, since this arithmetic progression contains the value $0$. In this case, the best we can hope is for $r(n)$ to eventually equal $kn+j$. This can always be achieved.

\begin{proposition}
Let $k\geq 0$ and $j$ be integers. Let $j=qk-r$ with $0 \leq r \leq k-1$, and let $\ttw$ be the one-sided fixed point of the Pisa substitution $\sigma_{1, k-1, 1}$.
\begin{itemize}
    \item[(a)]  If $q\geq 0$, then $r_{D^q(\ttw)}(n)= kn+j$ for all large enough $n$.
      \item[(b)]  If $q&lt; 0$, then for each equilibrious word $s$ of length $-2q$, we have $r_{{\rm Pre}_{s}(\ttw)}(n)= kn+j$ for all large enough $n$. In particular, this holds when $s = (\tta \ttb)^{-q}$.
\end{itemize}
\end{proposition}

We now turn to binary substitutions such that the relative position is asymptotically linear. In particular, analogous to the calculations in Section~\ref{sect:fib}, we can find all binary substitutions whose one-sided fixed points satisfy
\[
\lim_{n\to\infty} \frac{r(n)}{n}= k \in \ZZ \,.
\]
As in the previous section, for each $k \in \NN$, set $\tau_{k}:=\frac{k+ \sqrt{k^2+4}}{2}$. These numbers arise naturally as the eigenvalues of the substitution matrices of the Pisa substitutions $\sigma_{k-j,j,1}$. Of course, $\tau_1=\tau$ is the golden mean.
Recall that $\tau_k$ is a root of $X^2-kX-1=0$ and so, $\tau_k^2=k \tau_k+1$.

We obtain the following, more general, version of Lemma~\ref{lem2}.

\begin{lemma}\label{lem2a} Let $k \in \NN$ and $M \in {M}_2(\ZZ)$. Then,  $[\tau_k\ 1]^T$ is a right eigenvector for $M$ if and only if there exist $m, n \in \ZZ$ such that
\[
M= \begin{bmatrix}
km+n &amp; m \\
m &amp; n
\end{bmatrix}\,.
\]
Here, the eigenvalues are $n+m \tau_k$ and $n+m \tau'_k$, where $\tau_k'$ is the algebraic conjugate of $\tau_k$.
\end{lemma}
\begin{proof} ($\Leftarrow$). Note that
\[
\begin{bmatrix}
km+n &amp; m \\
m &amp; n
\end{bmatrix}\begin{bmatrix}
\tau_k  \\ 1
\end{bmatrix}=
\begin{bmatrix}
km\tau_k+n\tau_k+m \\
m \tau_k + n
\end{bmatrix}=\begin{bmatrix}
m \tau_k^2 + n\tau_k  \\ m \tau_k + n
\end{bmatrix}= \\
 (m \tau_k + n) \begin{bmatrix}
\tau_k  \\ 1
\end{bmatrix},
\] so $[\tau_k\ 1]^T$ is a right eigenvector for $M$.

($\Rightarrow$).
Since $k&gt;0$, the polynomial $X^2-kX-1$ is irreducible over $\QQ$ by the rational root test. In particular, $\QQ(\tau_k)$ is a degree-two extension of $\QQ$. We now mimic the proof of Theorem~\ref{thm:Mform}(a) to get
\begin{align*}
M&amp;= \begin{bmatrix}
    \tau_k &amp; \tau_k' \\
    1 &amp; 1
\end{bmatrix} \begin{bmatrix}
    n+m\tau_k &amp; 0 \\
    0 &amp; n+m \tau_k'
\end{bmatrix}\begin{bmatrix}
    \tau_k &amp; \tau_k' \\
    1 &amp; 1
\end{bmatrix}^{-1} \\
&amp;=\frac{1}{\tau_k-\tau_k'}\begin{bmatrix}
    (n+m\tau_k )\tau_k &amp; (n+m \tau_k')\tau_k' \\
 n+m\tau_k  &amp; n+m \tau_k'
\end{bmatrix}  \begin{bmatrix}
    1 &amp; -\tau_k' \\
    -1 &amp; \tau_k
\end{bmatrix} \\
&amp;=\frac{1}{\tau_k-\tau_k'}
\begin{bmatrix}
(n+km )   (\tau_k-\tau_k') &amp; m(\tau_k - \tau_k') \\
m(\tau_k - \tau_k')&amp; n (\tau_k-\tau_k')
\end{bmatrix}
=\begin{bmatrix}
km+n &amp; m \\
m &amp; n
\end{bmatrix}\,,
\end{align*} which proves the result.
\end{proof}

We finish this section with the classification of all asymptotically linear relative position functions arising from primitive binary substitutions.

\begin{theorem}\label{thm-2} Let $\mu$ be a primitive binary substitution with incidence matrix $M_\mu$ and having one-sided fixed point $\ttw \in \W$. Let $k\in\NN$.
\begin{itemize}
  \item[(a)] The following are equivalent.
\begin{itemize}
\item[(i)] ${\lim_{n\to\infty} {r(n)}/{n}=k}$.
\item[(ii)]  $[\tau_k\ 1]^T$ is a right Perron--Frobenius eigenvector for $M_\mu$.
\item[(iii)] There exist $m \in \NN$ and $n \in \ZZ_{\geq 0}$ such that
$
M_\mu= \begin{bmatrix}
km+n &amp; m \\
m &amp; n
\end{bmatrix}$.
\end{itemize}
\item[(b)] The following are equivalent.
\begin{itemize}
\item[(i)] ${\lim_{n\to\infty} {r(n)}/{n}=-k}$.
\item[(ii)]  $[1\ \tau_k]^T$ is a right Perron--Frobenius eigenvector for $M_\mu$.
\item[(iii)] There exist $m \in \NN$ and $n \in \ZZ_{\geq 0}$ such that
$
M_\mu= \begin{bmatrix}
                         n &amp; m \\
                         m &amp;km+n
                       \end{bmatrix}$.
\end{itemize}
\item[(c)] The following are equivalent.
\begin{itemize}
  \item[(i)] ${\lim_{n\to\infty} {r(n)}/{n}=0}$.
  \item[(ii)] $[1\ 1]^T$ is a right Perron--Frobenius eigenvector for $M_\mu$.
  \item[(iii)] There exist $a,b,c,d \in \ZZ_{\geq 0}$ with $a+b=c+d$ such that
$
M_\mu=\begin{bmatrix}
a &amp; b \\
c &amp; d
\end{bmatrix}$.
\end{itemize}
\end{itemize}
\end{theorem}

\begin{proof} The proof of \textbf{(a)} is analogous to that of Lemma~\ref{lem2a1}, so we omit it.

\textbf{(b)} We have $\lim_{n\to\infty} {r_\ttw(n)}/{n}=-k$ if and only if $\lim_{n\to\infty} {r_{\overline{\ttw}}(n)}/{n}=k$. Now, $\overline{\ttw}$ is the one-sided fixed point of the substitution $\overline{\mu}$. Let ${M}_{\overline{\mu}}$ be the incidence matrix of $\overline{\mu}$. Then,
\[
M_\mu=\begin{bmatrix}
    a &amp; b \\
    c &amp; d
  \end{bmatrix}\quad\mbox{if and only if}\quad {M}_{\overline{\mu}}= \begin{bmatrix}
    d &amp; c \\
    b &amp; a
  \end{bmatrix} \,.
\]
Part (b) now follows now from part (a) applied to the situation of $\overline{\ttw}$.


\textbf{(c)} Let $[u\ 1]$ be the left Perron--Frobenius eigenvector of $M_\mu$.
Then, by Corollary~\ref{cor:asymp}, $\lim_{n\to\infty} \frac{r(n)}{n}=\frac{u^2-1}{u}$. The equivalence between (i) and (ii) is now clear, and (ii) $\Leftrightarrow$ (iii) is a trivial exercise.
\end{proof}

\section{The Thue-Morse substitution and related words}\label{sec:TM}

We now arrive at our final curiosity of the relative position function---the Thue-Morse word ${\bf t}$ is the only word $\ttw\in\Wa$ on the letters $\tta =1$ and $\ttb =-1$ with the property that the word
\[
r(1)r(2) \cdots r(n) \cdots
\]
is, again, equal to $\ttw$.

To this end, recall that the Thue-Morse substitution $\mu_{\rm TM}$ is defined by
\[
\mu_{\rm TM}:
\begin{cases}
    \tta \to \tta\ttb \\
    \ttb \to \ttb\tta\, ,
\end{cases}
\]
which has one-sided fixed point ${\bf t}$ satisfying ${\rm Freq}(\tta) = {\rm Freq}(\ttb) = \frac{1}{2}$ and $\displaystyle\lim_{n\to\infty} {r(n)}/{n} = 0$.

\begin{definition} Let $\ttw = \ell_0 \ell_1 \cdots \ell_n \cdots\in\W$. We define the \emph{dimers}
\[
X_n:=\ell_{2n}\ell_{2n+1} \,.
\]
Note that $\ttw = X_0X_1 \cdots X_n \cdots$, where $X_n \in \{ \tta \tta , \tta \ttb, \ttb \tta , \ttb \ttb \}$.
\end{definition}

In the particular case where each dimer contains distinct letters, we can give an explicit formula for $r(n)$ in terms of the dimers $X_n$. Taking into account that the first dimer has index $0$ while $r$ starts at $r(1)$, the following result follows from an easy induction on $n$.

\begin{proposition} Let $\ttw \in \W$ be some word. If all the dimers $X_n$ satisfy $X_n \in \{ \tta \ttb, \ttb \tta \}$, then
\begin{displaymath}
r(n)=
\begin{cases}
1, &amp;\text{if $X_{n-1} = \tta \ttb$;} \\
-1, &amp;\text{if $X_{n-1} = \ttb \tta$.} 
\end{cases}
\end{displaymath}
\end{proposition}

In the case of the Thue-Morse word, the dimers are exactly the level-$1$ supertiles $\ttA=\tta \ttb$ and $\ttB=\ttb \tta$ of the substitution $\mu_{\rm TM}$. This immediately gives the following result.

\begin{theorem} The Thue-Morse word ${\bf t}$ is the only binary word on $\tta=1$ and $\ttb=-1$ starting with $\tta=1$, having the property that ${\ttw}=r(1)r(2)\cdots r(n)\cdots$.
\end{theorem}

\begin{proof}
If ${\bf t}$ is the Thue-Morse word, then by the above,  $r_{{\bf t}}(n+1)=1$ if and only if $X_n=\ttA$ if and only if $\ell_{2n}=\tta = 1$. This shows that Thue-Morse word satisfies this property.

Next, let $\ttw$ be any word on $\tta=1$ and $\ttb=-1$ starting with $\tta=1$ with this property. Since $r_{\ttw}(n) \in \{1,-1\}$ for all $n$, a simple induction shows the dimers satisfy
\begin{displaymath}
X_n'=\begin{cases}
\tta \ttb,  &amp;\text{if $r_{\ttw}(n+1) = 1$;} \\
\ttb \tta, &amp;\text{if $r_{\ttw}(n+1) = -1$.}
\end{cases}
\end{displaymath}
Now, let $\ttw =\ell_0'\ell_1' \cdots \ell_n' \cdots$ and let ${\bf t}=\ell_0\ell_1 \cdots \ell_n \cdots$. We know that $\ell_0=1=\ell'_0$. Now, for each $n \geq 0$, we have that $\ell_n = \ell'_n$ implies that $r_{{\bf t}}(n+1)=r_{\ttw}(n+1)$, which implies that $X_n=X_n'$, so that $\ell_{2n} = \ell'_{2n}$ and $\ell_{2n+1} = \ell'_{2n+1}$. This proves the claim.
\end{proof}

Let us note next that for a word $\ttw \in \W$, the equalities $r_\ttw(1)=1$ and $r_\ttw(2)=-1$ are equivalent to $\ttw \in \tta \ttb \ttb \tta \W$. Therefore, we have
\begin{corollary} The Thue-Morse word ${\bf t}$ is the only binary word in $\tta \ttb \ttb \tta\W$ that is isomorphic to $r(1)r(2)\cdots r(n)\cdots$.
\end{corollary}


In exactly the same way, we can show that the double--double of bits of the Thue-Morse word creates the only word on $\tta =2$ and $\ttb =-2$ with this property. More generally, we have the following result. Since the proof is identical to the one above, we omit it. 

\begin{theorem} Let $k&gt;1$ be a positive integer, let ${\bf t}$ be the Thue-Morse word, and let $\ttw = \phi_k({\bf t})$. Then, $\ttw$ is the only binary word on $\tta=k$ and $\ttb=-k$, starting with $\tta=k$, with the property that ${\ttw}=r(1)r(2)\cdots r(n)\cdots$.
\end{theorem}


\section{Acknowledgments}

We thank the referee for their careful reading and constructive criticisms, as well as for Remark \ref{remreferee}, all of which improved our paper.

This work was partially supported by NSERC via grants 2019-05430 (CR) and 2024-04853 (NS), and by a David W. and Helen E. F. Lantis Endowment (MC). This work was initiated during MC's visit to MacEwan University---MC thanks the MacEwan faculty and staff for their hospitality and support. 

\bibliographystyle{amsplain}
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\href}[2]{#2}
\begin{thebibliography}{99}

\bibitem{AMP}
J.-P.\ Allouche, M.\ Mend{\`e}s~France, and J.\ Peyri{\`e}re, {Automatic {D}irichlet series}, \emph{J.\ Number Theory} \textbf{81} (2000), 359--373.

\bibitem{AS1999}
J.-P.\ Allouche and J.\ Shallit, {The ubiquitous Prouhet-Thue-Morse sequence}, in C.\ Ding, T.\ Helleseth, and H.\ Niederreiter, eds., \emph{Sequences and their Applications}, Springer-Verlag London, 1999, pp.\ 1--16.

\bibitem{ASbook}
J.-P.\ Allouche and J.\ Shallit, \emph{Automatic Sequences}, Cambridge University Press, 2003.

\bibitem{TAO}
M.\ Baake and U.\ Grimm, \emph{Aperiodic Order. {V}ol. 1: A Mathematical Invitation}, Cambridge University Press, 2013.

\bibitem{B2008}
J.\ P.\ Bell,
{Logarithmic frequency in morphic sequences},
\emph{J.\ Th\'eor.\ Nombres Bordeaux} \textbf{20} (2008), 227--241.

\bibitem{Cobham}
A.\ Cobham, Uniform tag sequences, \emph{Math.\ Systems Theory} \textbf{6} (1972), 164--192.

\bibitem{D2018}
M.\ Dekking, Substitution invariant Sturmian words and binary trees, \emph{Integers} \textbf{18A} (2018), Paper A7.

\bibitem{D1975}
H.\ Delange, Sur la fonction sommatoire de la fonction ``somme des chiffres'', \emph{Enseign. Math.} \textbf{21} (1975), 31--47.

\bibitem{D2013}
P.\ Dumas, Joint spectral radius, dilation equations, and asymptotic behavior of radix-rational sequences, \emph{Linear Algebra Appl.} \textbf{438} (2013), 2107--2126.

\bibitem{EMM}
G.\ B.\ Escolano, N.\ Ma\~nibo, and E.\ D.\ Miro, {Mixing properties and entropy bounds of a family of Pisot random substitutions}, \emph{Indagationes Math.}~\textbf{33} (2022), 965--991.

\bibitem{MP1966}
M.\ Marvin and S.\ Papert, Unrecognizable sets of numbers, \emph{J.\ Assoc.\ Comput.\ Mach.} \textbf{13} (1966), 281--286.

\bibitem{M1975}
P.\ Michel, \emph{Sur les Ensembles Minimaux Engendr\'es par les Substitutions de Longueur Non Constante}, PhD thesis, Universit\'e de Rennes, 1975.

\bibitem{M1976}
P.\ Michel, Stricte ergodicit\'e d'ensembles minimaux de substitution, in J.-P.\ Conze and M.\ S.\ Keane, eds., \emph{Th\'eorie Ergodique: Actes des Journ\'ees Ergodiques}, Springer, 1976, pp.\ 189--201.

\bibitem{Peter}
M.\ Peter, The asymptotic distribution of elements in automatic sequences, \emph{Theoret.\ Comput.\ Sci.} \textbf{301} (2003), 285--312.

\bibitem{Que}
M.\ Queff\'{e}lec, \emph{Substitution Dynamical Systems---Spectral Analysis}, Springer, 1987.

\bibitem{Saari}
K.\ Saari, On the frequency of letters in morphic sequences, in D.\ Grigoriev, J.\ Harrison, and E.\ A.\ Hirsch, eds., \emph{Computer Science---Theory and Applications}, Springer, 2006, pp.\ 334--345.

 \bibitem{Sing}
B.\ Sing, \emph{Pisot Substitutions and Beyond}, PhD thesis, Univ.\ Bielefeld, 2006.
\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification}:
Primary 05A05; Secondary 68R15, 11B05.

\noindent \emph{Keywords:} substitution, Thue-Morse sequence, letter frequency.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences \seqnum{A003849} and \seqnum{A010060}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received October 15 2024;
revised versions received  October 16 2024; February 9 2025.
Published in {\it Journal of Integer Sequences}, February 12 2025.

\bigskip
\hrule
\bigskip

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


\end{document}
</pre></body></html>