\documentclass{amsart}
\usepackage{amssymb}
\usepackage{latexsym}
\newcommand{\ZZ}{{\mathbb Z}}
\newcommand{\RR}{{\mathbb R}}
\newcommand{\NN}{{\mathbb N}}
\newcommand{\lp}{{\rm (}}
\newcommand{\rp}{{\rm )\,}}
\newtheorem{theo}{Theorem}[section]
\newtheorem{prop}[theo]{Proposition}
\newtheorem{lemma}[theo]{Lemma}
\newtheorem{coro}[theo]{Corollary}
\newtheorem{defi}[theo]{Definition}
\begin{document}
\title[Palindrome complexity bounds]{Palindrome complexity bounds for primitive substitution sequences}
\author[D.~Damanik and D.~Zare]{David Damanik$\,^{1,2}$ and Douglas Zare$\,^{3}$}
\maketitle
\vspace{0.3cm}
\noindent
$^1$ Department of Mathematics 253-37,
California Institute of Technology,
Pasadena, CA 91125,
U.S.A.\\[0.2cm]
$^2$ Fachbereich Mathematik,
Johann Wolfgang Goethe-Universit\"at,
60054 Frankfurt, Germany\\[0.2cm]
$^3$ Department of Mathematics,
Columbia University,
New York, NY 10027,
U.S.A.\\[0.3cm]
E-mail: damanik@its.caltech.edu, zare@math.columbia.edu\\[0.2cm]
1991 AMS Subject Classification: 68R15, 58F03, 58F11, 81Q10\\
Key words: primitive substitutions, word complexity
\begin{abstract}
We consider one-sided infinite words generated via iteration by primitive
substitutions on finite alphabets and provide bounds on the palindrome
complexity function as well as uniform bounds on the frequencies of
palindromes in such words. As an application of these bounds, we prove
that the strongly palindromic sequences in a primitive substitution
dynamical system form a set of measure zero.
\end{abstract}
\section{Introduction}
In this paper we are concerned with a study of local reflectional
symmetries in general infinite words generated by primitive substitutions.
We shall study combinatorial issues, namely, the palindrome complexity
function associated to such words, as well as dynamical issues, that is,
the frequencies of palindromes occurring in these words. Before we present
the results we shall prove, let us recall some basic notions.
Consider a finite set $\mathcal{A}=\{a_1,\ldots,a_s\}$, called the {\it
alphabet}. The elements of $\mathcal{A}^* = \cup_{n = 0}^\infty \mathcal{A}^n$
are called (finite) {\it words over} $\mathcal{A}$. A word $x$ has {\it
length} $n$ if it belongs to $\mathcal{A}^n$. We shall also consider
one-sided (resp., two-sided) infinite words, that is, elements of $\mathcal{A}^\NN$ (resp., $\mathcal{A}^\ZZ$). The set $\mathcal{A}^*$ naturally carries a
free semigroup structure with respect to concatenation. Given a word $x
\in \mathcal{A}^*$, $y \in \mathcal{A}^*$ is called a {\it factor} of $x$ if
there are words $z_1,z_2$ such that $x=z_1 y z_2$. Similarly, a word $y$
is a factor of an infinite word $u \in \mathcal{A}^\NN$ if there exist $z \in \mathcal{A}^*$ and $v \in \mathcal{A}^\NN$ such that $u=zyv$. Given a word $u$ (finite or infinite), we define $F_u = \{y:y$ is a factor of $u\}$ and, for $n \in \NN$, $F_u(n) = F_u \cap \mathcal{A}^n$. The {\it complexity
function} $f_u:\NN \rightarrow \NN_0$ corresponding to a word $u$ is given
by $f_u(n) = |F_u(n)|$, $|\cdot|$ denoting cardinality. A word $p \in
\mathcal{A}^*$ is called a {\it palindrome} if it is the same when read
backwards. Denote by $PAL_\mathcal{A}$ the set of all palindromes over $\mathcal{A}$ and define for a given word $u$, $P_u = F_u \cap PAL_\mathcal{A}$ and $P_u(n) = P_u \cap \mathcal{A}^n$. Thus, the set $P_u(n)$ consists of all palindromes which are a factor of $u$ and have length $n$. The {\it palindrome complexity function} $p_u:\NN \rightarrow \NN_0$ corresponding to a word $u$ is given by $p_u(n) = |P_u(n)|$. We refer the reader to the introductory articles \cite{ab,am,b2,b3} for more information on issues related to combinatorial complexity.
A mapping $S:\mathcal{A} \rightarrow \mathcal{A}^*$ is called a {\it
substitution}. Such a mapping $S$ can be extended to $\mathcal{A}^*$ by
$S(b_1 \ldots b_k) = S(b_1) \ldots S(b_k)$ and, similarly, to $\mathcal{A}^\NN$ by $S(b_1 b_2\ldots) = S(b_1) S(b_2) \ldots$, $b_i \in \mathcal{A}$.
A substitution $S$ is called {\it primitive} if there is some $k \in \NN$
such that for every $a_i \in \mathcal{A}$, the word $S^k(a_i)$ contains all
the elements of $\mathcal{A}$. Prominent examples of primitive substitutions
are given by
\begin{center}
\begin{tabular}{lll}
$\mathcal{A} = \{a,b\}$, & $a \mapsto ab$, $b \mapsto a$ & Fibonacci
substitution,\\
$\mathcal{A} = \{a,b\}$, & $a \mapsto ab$, $b \mapsto aa$ & Period doubling
substitution,\\
$\mathcal{A} = \{a,b\}$, & $a \mapsto ab$, $b \mapsto aaa$ & Binary non-Pisot
substitution,\\
$\mathcal{A} = \{a,b\}$, & $a \mapsto ab$, $b \mapsto ba$ & Thue-Morse
substitution,\\
$\mathcal{A} = \{a,b,c,d\}$, & $a \mapsto ab$, $b \mapsto ac$, $c \mapsto
db$, $d \mapsto dc$ & Rudin-Shapiro substitution.
\end{tabular}
\end{center}
A fixed point $u \in \mathcal{A}^\NN$ of a substitution $S$ is called a {\it
substitution sequence}. If $S$ is primitive, a substitution sequence $u$
always exists for a suitable power of $S$ and the set of finite factors in
a substitution sequence depends only on $S$, that is, if $u_1,u_2$ are
fixed points of $S$, then $F_{u_1} = F_{u_2}$. Moreover, in the primitive
case the a priori exponential upper bound on $f_u$ can be improved
considerably. In fact, a linear upper bound can be proven \cite{q}. Now,
the palindrome complexity function, which also has an exponential a priori
upper bound, can therefore grow at most linearly since, obviously, $p_u(n)
\le f_u(n)$ for every $n \in \NN$. This can be improved as the
following theorem shows.
\begin{theo}\label{comp}
Let $S$ be a primitive substitution. Then there exists $C < \infty$ such
that for every substitution sequence $u$ associated to $S$, $p_u(n) \le C$
for every $n \in \NN$.
\end{theo}
{\noindent}{\it Remarks.}
{\noindent} 1. The palindrome complexity function has been investigated
for the Fibonacci case \cite{d2,dp}, the period doubling case \cite{d1},
and the Rudin-Shapiro case \cite{a} (see also \cite{b}). These works
provide explicit descriptions of the sets $P_u(n)$, $n \in \NN$, in the
respective cases.\\
2. The palindrome complexity function implicitly plays an
important role in a paper by Hof et al.~\cite{hks}. They study the eigenvalue problem of one-dimensional Schr\"odinger operators with potentials generated by primitive substitutions. Their criterion for absence of eigenvalues is applicable if and only if the palindrome complexity function does not eventually vanish and gives generic absence of eigenvalues.
\medskip
Given a substitution sequence $u$ of a primitive substitution
$S$, we can consider the associated substitution dynamical system
$(\Omega,T)$, where
$$\Omega = \{ \omega \in \mathcal{A}^\ZZ\; :\; F_\omega = F_u\}$$
and
$$T:\Omega \rightarrow \Omega, \: (T\omega)_n = \omega_{n+1}.$$
If $\mathcal{A}$ is equipped with discrete topology and $\mathcal{A}^\ZZ$ is
equipped with product topology, the topological dynamical system
$(\Omega,T)$ is strictly ergodic, that is, the orbit of every $\omega \in
\Omega$ is dense in $\Omega$ and there exists a unique $T$-invariant Borel
measure $\mu$ which is necessarily ergodic \cite{q}. In particular, all
frequencies of factors in $u$ exist uniformly and are strictly positive,
that is, for every $v \in F_u$ there exists $d_u(v) > 0$ such that for
every $k \in \NN$, we have
$$
\frac{\#_v(u_k \ldots u_{k+n-1})}{n} \rightarrow d_u(v)
$$
as $n \rightarrow \infty$, where for $x,y \in \mathcal{A}^*$, $\#_x (y)$ denotes the number of occurrences of $x$ in $y$, and the convergence is uniform in $k$. The measure of a cylinder set is given by the frequency of the defining word, that is, for each $v \in F_u$ and $k \in \NN$, we have
\begin{equation}\label{cylsetmeas}
\mu(\{\omega \in \Omega : \omega_k \ldots \omega_{k + |v| - 1} = v
\}) = d_u(v).
\end{equation}
For palindromes in $u$, the following uniform bounds can be obtained for
their frequencies.
\begin{theo}\label{freq}
Let $S$ be a primitive substitution. Then there exist $0 < D,E < \infty$
such that for every aperiodic substitution sequence $u$ associated to $S$,
for every $n\in \NN$, and for every $p \in P_n(u)$, we have
\begin{equation}\label{uniflin}
\frac{D}{n} \le d_u(p) \le \frac{E}{n}.
\end{equation}
\end{theo}
Given a substitution dynamical system and a function $g: \mathcal{A}
\rightarrow \RR$, one can define an ergodic family of Schr\"odinger
operators $(H_\omega)_{\omega \in \Omega}$ in $l^2(\ZZ)$ by
$$
(H_\omega \phi)(n) = \phi(n+1) + \phi(n-1) + V_\omega(n) \phi(n),
$$
{\noindent}where $V_\omega(n) = g(\omega_n)$. A study of palindromic
structures in
substitution sequences is now connected to the eigenvalue problem for
these operators as follows. Let
$$
\Omega_c = \{ \omega \in \Omega : \sigma_{{\rm pp}} (H_\omega) =
\emptyset\},
$$
{\noindent}that is, the bi-infinite sequences $\omega \in \Omega$ whose associated operators have no eigenvalues.
A two-sided sequence is called {\it strongly palindromic} if it contains
palindromes $p_n$ having length $l_n$ and centers $c_n$ such that $c_n
\rightarrow \infty$ and
$$
\frac{\exp(B c_n)}{l_n} \rightarrow 0
$$
for a certain constant $B \ge 1$ (which is determined by $g$). Define
\begin{center}
$\Omega_{{\rm sp}}$ $=$ $\{ \omega \in \Omega$ : $\omega$ is strongly
palindromic$\}$.
\end{center}
Then, Hof et al.~have shown that
$$
\Omega_{{\rm sp}} \subseteq \Omega_c.
$$
{\noindent}Moreover, if the palindrome complexity function does not
eventually vanish, then $\Omega_{{\rm sp}}$ is not empty and, in fact,
$\Omega_{{\rm sp}}$ is uncountable. Using \cite{s}, it can even be shown that $\Omega_c$ is then a dense $G_\delta$ in $\Omega$.
The set $\Omega_{{\rm sp}}$ is invariant and hence has measure either $0$ or $1$. With the bounds from the above theorems we are able to show that the
measure is always zero.
\begin{theo}\label{ospmz}
Let $S$ be a primitive substitution which admits an aperiodic substitution
sequence and $\Omega$ the induced substitution dynamical system. Then,
$\mu(\Omega_{{\rm sp}})=0$.
\end{theo}
{\noindent}{\it Remark.} This result should be contrasted with the
following. By different methods it has been shown that $\mu(\Omega_c)=1$ for a class of substitutions including period doubling and binary non-Pisot \cite{d4}; see also \cite{k1} (resp., \cite{d3}) for a direct proof in the Fibonacci (resp., period doubling) case. In the Fibonacci case it can even be shown that $\Omega_c = \Omega$ \cite{dl1}.
\medskip
The organization of this article is as follows. In Section 2 we prove a
rather useful tool which concerns the repetitivity of the finite factors
in primitive substitution sequences. We use this lemma in Section 3 to
relate powers and palindromes in such sequences and to prove Theorems
\ref{comp} and \ref{freq}. We show in Section 4 how the bounds from these
two theorems imply Theorem \ref{ospmz}. Finally, Section 5 contains some
concluding remarks.
\section{The window lemma}
This section is concerned with a proof of what could be called the window
lemma, a result saying that given a primitive substitution sequence $u$,
one can find all subwords of a given length $n$ by inspecting an arbitrary
subword of length $Cn$, where the constant $C$ only depends on the
substitution. That is, one may put a window of length $Cn$ on some
arbitrary portion of $u$ and be sure that one ``sees'' all the words from
$F_u(n)$. In fact, this property has been termed {\it linearly repetitive}
by Lagarias and Pleasants in \cite{lp}. They show that strict ergodicity
of the associated dynamical system $(\Omega,T)$ follows from this
property. The result presented in the lemma below seems to be known.
However, since we could not find a suitable reference, we include a proof
for the reader's convenience.
\begin{lemma}\label{windowlemma}
Let $S$ be a primitive substitution. Then there exists $C_S < \infty$
such that for every one-sided infinite fixed point $u$ of $S$ and every
$n \in \NN$, every subword of $u$ of length $n$ is a factor of every
subword of $u$ of length $C_S n$.
\end{lemma}
{\it Remark.} This recovers the linear bound on $f_u(n)$. In
fact, our proof will refine the argument from the proof of this bound
given in \cite{q}.
\medskip
Before giving the proof of Lemma \ref{windowlemma}, let us recall some
standard facts which can all be found in \cite{q}. Given a substitution
$S$ on some alphabet $\mathcal{A}$ having $s$ symbols, we can associate an
$s\times s$-matrix $M=(m_{ij})$, the {\it substitution matrix}, by
$m_{ij}=\,$number of occurrences of $a_i$ in $S(a_j)$. Primitivity of $S$
is then equivalent to primitivity of $M$ (i.e., existence of $k \in \NN$
such that all entries of $M^k$ are strictly positive). In the primitive
case, the Perron-Frobenius theorem ensures the existence of a dominant
eigenvalue $\theta$ of $M$ which can be regarded as a uniform asymptotic
blow-up factor. That is, for each $a \in \mathcal{A}$, there is $c_a \in
(0,\infty)$ such that
$$
\frac{|S^k(a)|}{\theta^k} \rightarrow c_a.
$$
Define
$$
{\rm lmax}(k) = \max_{a \in \mathcal{A}}|S^k(a)|, \; {\rm lmin}(k) = \min_{a
\in \mathcal{A}}|S^k(a)|,
$$
\noindent that is, the maximum and minimum lengths of $k$-fold iterations of
the substitution $S$ upon letters. Then there exist $z_1,z_2 \in
(0,\infty)$ such that for all $k
\in \NN$, we have
$$
z_1 \theta^k \le {\rm lmin}(k) \le {\rm lmax}(k) \le z_2 \theta^k.
$$
Another concept we shall need is the following. The associated
substitutions $S_l$ treat $\mathcal{A}_l=F_u(l)$ as a new alphabet and map
from $\mathcal{A}_l$ to $\mathcal{A}_l^*$. Given some $b_1 \ldots b_l \in \mathcal{A}_l$, $S_l(b_1 \ldots b_l)$ is given by
$$
S_l(b_1 \ldots b_l) = (x_1 \ldots x_l) (x_2 \ldots x_{l+1}) \ldots
(x_{|S(b_1)|} \ldots x_{|S(b_1)|+l-1}),
$$
where the $x_i$ are defined by
$$
S(b_1 \ldots b_l) = x_1 \ldots x_{|S(b_1)|} x_{|S(b_1)|+1} \ldots
x_{|S(b_1 \ldots b_l)|}.
$$
Then, it is easy to check that $|S_l(b_1 \ldots b_l)| = |S(b_1)|$ and that
$S_l$ admits the sequence
$$
U_l = (u_1 \ldots u_l)(u_2 \ldots u_{l+1})(u_3 \ldots u_{l+2}) \ldots
$$
as a fixed point. Moreover, $u$ satisfies the window property with window
length $m$ for words of length $l$ if and only if $U_l$ satisfies the
window property with window length $m-l+1$ for words of length $1$.
\medskip
{\it Proof of Lemma \ref{windowlemma}.} The proof consists of two steps.
One treats the case $n=2$ first and then handles the general case.
Consider the substitution $S_2$. By primitivity of $S_2$, every window of
length $C_1 = 2 {\rm lmax}(k)$ on $U_2$, $k$ being the primitivity
constant of $S_2$, contains all the symbols from $\mathcal{A}_2$ and thus all the words in $F_u(2)$. By the above remarks, every window of length $C_2 = C_1 + 1$ on $u$ contains all the words from $F_u(2)$.
Now let $n \ge 3$ be arbitrary. We claim that with $C_S = \frac{(C_2 + 2)z_2 \theta}{z_1}$, the assertion of the lemma holds. So let $i \in \NN$ be arbitrary and consider the window $w=u_i \ldots u_{i +C_S n -1}$. We have to show that this window contains all the words from $F_u(n)$ as factors. By $S(u) = u$ we have $u_1 u_2 u_3 \ldots = S^p(u_1) S^p(u_2) S^p(u_3) \ldots$ for each $p \ge 1$, and we choose $p$ to be that value for which
\begin{equation}\label{pdef}
{\rm lmin}(p-1) < n \le {\rm lmin}(p).
\end{equation}
Consider now the partition of $u$ into blocks of the type $S^p(b)$, $b \in \mathcal{A}$. Let $S^p(u_r) \ldots S^p(u_{r+j-1})$ be the blocks that are fully contained in this window. We can now infer the following:
\begin{eqnarray*}
j & \ge & \frac{C_S n - 2 {\rm lmax}(p)}{{\rm lmax}(p)}\\
& \ge & \frac{\frac{(C_2 + 2)z_2 \theta}{z_1} n}{z_2\theta^p} -2\\
& \ge & C_2 + 2 -2.
\end{eqnarray*}
Thus, $u_r \ldots u_{r+j-1}$ contains all the words from $F_u(2)$. The
claim now follows from (\ref{pdef}) since any word in $F_u(n)$ is
contained in some $S^p(v)$ with a suitably chosen $v\in
F_u(2)$.\hfill$\Box$
\section{Powers and palindromes}
In this section we use the window lemma to relate powers and palindromes
occurring in substitution sequences and to prove Theorems \ref{comp} and
\ref{freq}. Given a word $u$ (finite or infinite), denote by $\pi(u) \in
\NN \cup \{ \infty \}$ the largest power occurring in $u$, that is,
$$
\pi(u) = \sup \{k \in \NN : v^k \in F_u, v \in \mathcal{A}^*\}.
$$
If $u$ is a substitution sequence associated to a primitive substitution,
then either $\pi(u)$ is bounded by $C_S$ or $u$ is ultimately periodic as
the following lemma shows.
\begin{lemma}\label{powerbound}
Let $S$ be a primitive substitution. Suppose $u$ is an aperiodic
substitution sequence associated to $S$. Then $\pi(u) < C_S$.
\end{lemma}
{\it Proof.} It is well known that if $u$ is aperiodic, then $f_u(n) \ge
n+1$ for every $n \in \NN$; see, for example, \cite{q}. The claim now
follows from Lemma \ref{windowlemma} as follows. Suppose $\pi(u) \ge C_S$.
Then there exists $v \in \mathcal{A}^*$ such that $v^{C_S} \in F_u$. Let $m =
|v|$. Now $f_{v^{C_S}}(m) \le m$ and hence $f_u(m) \le m$, a
contradiction.\hfill$\Box$
\medskip
The next lemma deduces the existence of powers from overlapping
palindromes in $u$. Together with the preceding lemma this allows us to
bound the distance between consecutive palindromes from below. Given an
occurrence of a palindrome $p=u_{k_1} \ldots u_{k_2} \in P_u$ in $u$, we
say that $p$ is {\it centered} at $c(p)$, where $c(p) = \lfloor \frac{k_2
+ k_1}{2} \rfloor$. This is slightly unnatural for palindromes of even
length, but will prevent us from having to treat the even and odd length
palindromes separately.
\begin{lemma}\label{repell}
Let $u$ be a word and suppose $p_1,p_2 \in \mathcal{A}^{2n}$ \lp resp.,
$\mathcal{A}^{2n+1}$\rp are palindromes occurring in $u$ centered at the
sites $c(p_1), c(p_2)$, respectively. Let $d = |c(p_2) - c(p_1)|$. Then
$u$ contains a $k$-th power, where $k = \lfloor \frac{n}{2d} \rfloor$.
\end{lemma}
{\it Proof.} Suppose that the occurrences of $p_1,p_2$ overlap, since
otherwise there is nothing to prove. We can reflect at the respective
centers of the palindromes to obtain relations between the symbols in the
part of $u$ where the palindromes overlap. In particular this yields a
power of a word of length $2d$. The power that can be deduced before
hitting the boundary is just $\lfloor \frac{n}{2d}
\rfloor$.\hfill$\Box$
\medskip
{\it Proof of Theorem \ref{comp}.} Fix $u$ and $n$. It is sufficient to
consider the case of aperiodic $u$ since any ultimately periodic sequence
has bounded complexity function. Choose any window in $u$ of length $C_S
n$. All words of length $n$ in $u$, and in particular, all palindromes
from $P_u(n)$ are contained in this window. By the last two lemmas, the
centers of these palindromes are separated by at least
$\frac{n}{2(\pi(u) + 1)}$. This yields the bound
$$
p_u(n) \le \frac{C_S n}{\left( \frac{n}{2(\pi(u) + 1)} \right) } \le
2C_S(C_S + 1)
$$
\noindent from which the claim follows.\hfill$\Box$
\medskip
{\it Proof of Theorem \ref{freq}.} The lower bound is immediate from the
window lemma and the upper bound can be proved by an argument similar to
the above, namely, that there is a linear lower bound with uniform
constant for the distance between two consecutive occurrences of a given
palindrome of length $n$ in $u$.\hfill$\Box$
\section{Strongly palindromic sequences}
In this section we provide a proof of Theorem \ref{ospmz}, that is, we
show that for aperiodic primitive substitution dynamical systems, the set
of strongly palindromic sequences has always measure zero. Given a
subshift $(\Omega,T)$ which derives from a primitive substitution $S$, we
define for $n \in \NN$ the following set which is easily seen to be a
Borel set,
$$
\Omega_n = \{ \omega \in \Omega : \omega \, {\rm contains} \, {\rm a} \,
{\rm palindrome} \, {\rm of} \, {\rm length} \, \ge \exp(n) \, {\rm
centered} \, {\rm at} \, n\}.
$$
\begin{lemma}
With the above definition, we have
\begin{equation}\label{ospsubsetlson}
\Omega_{{\rm sp}} \subseteq \limsup_{n \rightarrow \infty} \Omega_n,
\end{equation}
that is, every $\omega \in \Omega_{{\rm sp}}$ is contained in infinitely many of the $\Omega_n$.
\end{lemma}
{\it Proof.} Given $\omega \in \Omega_{{\rm sp}}$, we can find in $\omega$
palindromes $p_n$ of length $l_n$ centered at $c_n \rightarrow \infty$
such that for a certain $B \ge 1$, $\exp(B c_n) / l_n \rightarrow 0$ as $n
\rightarrow \infty$. Thus for a suitable $n_0 \in \NN$, we have $\exp(c_n)
\le l_n$ for all $n \ge n_0$. In particular, $\omega \in \Omega_{c_n}$ for
all $n \ge n_0$.\hfill$\Box$
\begin{lemma}
There exists a constant $F < \infty$ such that for every $n \in \NN$,
\begin{equation}\label{onbound}
\mu(\Omega_n) \le \frac{F}{\exp(n)}.
\end{equation}
\end{lemma}
{\it Proof.} Obviously, if $\omega \in \Omega$ contains a palindrome of
length $l \ge 3$ centered at $c$, then it contains a palindrome $p'$ of
length $l-2$ centered at $c$. Thus, we have for every $n \in \NN$,
\begin{center}
$\Omega_n = \{ \omega \in \Omega \, : \, \omega$ contains a palindrome of
length $\lceil \exp(n) \rceil$ centered at $n \} \cup$\\
\qquad \qquad $\{ \omega \in \Omega \, : \, \omega$ contains a palindrome
of length $\lceil \exp(n) \rceil + 1$ centered at $n \}$.
\end{center}
\noindent With the constants $C,E$ from Theorems \ref{comp} and
\ref{freq} along
with equation (\ref{cylsetmeas}), we obtain the bound
$$
\mu(\Omega_n) \le \frac{2CE}{\exp(n)}
$$
\noindent and hence the assertion.\hfill$\Box$
\medskip
{\it Proof of Theorem \ref{ospmz}.} The claim follows from equations
(\ref{ospsubsetlson}) and (\ref{onbound}) together with the standard
Borel-Cantelli lemma.\hfill$\Box$
\section{Concluding remarks}
We have considered palindromes in infinite words generated by substitution
sequences. By exhibiting linear repetitivity, that is, the window lemma
property, we were able to prove bounds on the number of palindromes of
given length as well as bounds on their frequency. These bounds in turn
implied that the set of strongly palindromic sequences in primitive
substitution dynamical systems always has measure zero with respect to the
unique ergodic measure. In this section we want to make a few remarks on
some more or less obvious extensions of the above theorems.
First, the bound (\ref{uniflin}) in Theorem \ref{freq} holds for all words
in $F_u(n)$, not only for words in $P_u(n)$. The lower bound was in fact
proven for all words since it directly follows from the window lemma. The
upper bound can be proven by a method similar to the proof of Lemma
\ref{repell}. Namely, the distance between two consecutive occurrences of
some word $w \in F_u(n)$ has a linear lower bound with a uniform constant
since an overlap also implies the occurrence of a power. This together
with Lemma \ref{powerbound} yields the claimed lower bound and thus the
upper bound on the frequency.
Second, note that the proofs only employ the window lemma property. Thus
all the results immediately extend to infinite words which are linearly
repetitive. These include, for example, Sturmian words $s_{\alpha,\beta} =
\lfloor (n+1) \alpha + \beta \rfloor - \lfloor n \alpha + \beta \rfloor$,
$\alpha \in (0,1)$ irrational and $\beta \in (0,1)$ arbitrary, in the case
where the coefficients $a_n$ in the continued fraction expansion of
$\alpha$ are bounded.
\medskip
{\it Acknowledgment.} D.~D.~would like to thank the German Academic
Exchange Service for financial support through Hochschulsonderprogramm III
(Postdoktoranden).
\begin{thebibliography}{99}
\bibitem{ab} P.~Alessandri and V.~Berth\'{e}, Three distance theorems and
combinatorics on words, {\it Enseign. Math.} {\bf 44} (1998), 103--132.
\bibitem{a} J.-P.~Allouche, Schr\"odinger operators with Rudin-Shapiro
potentials are not palindromic, {\it J. Math. Phys.} {\bf 38} (1997),
1843--1848.
\bibitem{am} J.-P.~Allouche and M.~Mend\`{e}s France, Automata and
automatic sequences, in ``Beyond Quasicrystals'' (Les Houches, 1994),
Springer, Berlin (1995), 293--367.
\bibitem{b} M.~Baake, A note on palindromicity, preprint math-ph/9907011, to appear in {\it Lett. Math. Phys.}
\bibitem{b2} V.~Berth\'{e}, Entropy in deterministic and random systems,
in ``Beyond Quasicrystals'' (Les Houches, 1994), Springer, Berlin
(1995), 441--463.
\bibitem{b3} V.~Berth\'{e}, Sequences of low complexity: Automatic and
Sturmian sequences, preprint.
\bibitem{d3} D.~Damanik, Singular continuous spectrum for the
period doubling Hamiltonian on a set of full measure, {\it
Commun. Math. Phys.} {\bf 196} (1998), 477--483.
\bibitem{d4} D.~Damanik, Singular continuous spectrum for a class of
substitution Hamiltonians, {\it Lett. Math. Phys.} {\bf 46} (1998),
303--311.
\bibitem{d1} D.~Damanik, Local symmetries in the period doubling sequence,
{\it Discrete Appl. Math.} {\bf 100} (1999), 115--121
\bibitem{dl1} D.~Damanik and D.~Lenz, Uniform spectral properties of
one-dimensional quasicrystals, I. Absence of eigenvalues, {\it Commun. Math. Phys.} {\bf 207} (1999), 687--696.
\bibitem{d2} X.~Droubay, Palindromes in the Fibonacci word, {\it
Inf. Proc. Lett.} {\bf 55} (1995), 217--221.
\bibitem{dp} X.~Droubay and G.~Pirillo, Palindromes and Sturmian words, {\it Theoret. Comput. Sci.} {\bf 223} (1999), 73--85.
\bibitem{hks} A.~Hof, O.~Knill, and B.~Simon, Singular continuous
spectrum for palindromic Schr\"odinger operators, {\it Commun. Math.
Phys.} {\bf 174} (1995), 149--159.
\bibitem{k1} M.~Kaminaga, Absence of point spectrum for a class of
discrete Schr\"odinger operators with quasiperiodic potential, {\it
Forum Math.} {\bf 8} (1996), 63--69.
\bibitem{lp} J.~C.~Lagarias and P.~A.~B.~Pleasants, Repetitive Delone sets
and quasicrystals, preprint math.DS/9909033.
\bibitem{q} M.~Queff\'{e}lec, {\it Substitution Dynamical
Systems - Spectral Analysis}, Lecture Notes in Mathematics,
Vol. 1284, Springer, Berlin - Heidelberg - New York (1987).
\bibitem{s} B.~Simon, Operators with singular continuous spectrum: I.
General operators, {\it Ann. of Math.} {\bf 141} (1995), 131--145.
\end{thebibliography}
\end{document}