\documentclass[12pt,reqno]{article}

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

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

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

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

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

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

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/ ~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

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

\begin{center}
\vskip 1cm{\LARGE\bf On a class of Thue-Morse type sequences
}
\vskip 1cm
\large
Ricardo Astudillo\footnote{This work was done while the author was
supported by an NSF REU (Research Experience for Undergraduates)
program at the University of Illinois in Summer 2001 and Spring 2002,
and by the Ronald E. McNair Scholars Program in Summer 2002.  The
author would like to thank the referee for a thorough
and helpful report.}\\  
Department of Mathematics\\  
University of Illinois\\  
Urbana, IL 61801\\  
USA\\  
\href{mailto:rastudil@math.uiuc.edu}{\tt rastudil@math.uiuc.edu} \\
\end{center}

\vskip .2 in

\begin{abstract} We consider a class of binary sequences that
generalize the Thue-Morse sequence.  In particular, we investigate the
occurrences of palindromes in such sequences.  We also introduce the
notion of the first difference of a binary sequence and characterize
first differences of our class of Thue-Morse type sequences.  Finally,
we define the concept of a ``change sequence'' of a given binary
sequence, a sequence which encodes the positions at which a binary
sequence changes values.  We characterize the change sequences
corresponding to our class of Thue-Morse type sequences.
\end{abstract}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section] 
\newtheorem*{introtheorem1}{Theorem A} 
\newtheorem*{introtheorem2}{Theorem B}

\theoremstyle{definition} \newtheorem{definition}{Definition}[section]
\newtheorem{example}{Example}[section] \newtheorem*{remark}{Remark}

\numberwithin{equation}{section}
\renewcommand{\labelenumi}{(\roman{enumi})}
\newcommand{\ci}[1]{\framebox{#1}} \newcommand{\ul}[1]{\underline{#1}}
\newcommand{\ol}[1]{\overline{#1}}
\newcommand{\note}[1]{\marginpar{#1}}



\section{Introduction} The Thue-Morse sequence
	\begin{equation*} \{t(n)\}_{n=0}^\infty =
	0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,\ldots \end{equation*} is
defined by $t(n) = 0$ if $n$ has an even sum of binary digits, and
$t(n)=1$ otherwise.  This sequence has attracted much attention since
its discovery by Axel Thue in the early 1900's, and is still the focus
of much study.  The Thue-Morse sequence can be constructed in a
surprising variety of ways and has numerous applications in diverse
fields such as differential geometry, algebra, number theory, and
physics; see, for example, \cite{ubiquitous}.

The Thue-Morse sequence can be generalized as follows:  For $k \geq 2$,
define $s_k(n)$  as the sum of digits in the base-$k$ representation of
a nonnegative integer $n$, and let $t_k(n) = s_k(n) \bmod{2}$.  The
sequence $\{t_k(n)\}_{n=0}^\infty$ is thus a binary sequence, and the
special case $k=2$ yields the Thue-Morse sequence $t_2(n)=t(n)$.

In a recent paper, Allouche and Shallit \cite{palindromes} investigated
palindromes in the sequences $\{t_k(n)\}$.  Here a palindrome is
defined in the usual sense: a sequence digits is a palindrome if it
reads the same forward and backward.  For example, in the Thue-Morse
sequence, the first four terms $0$,$1$,$1$,$0$ form a palindrome, as do
the first 16 terms.  Allouche and Shallit proved the following result:

\begin{introtheorem1}[Allouche and Shallit
\cite{palindromes}]\label{th:intro1} For all $k \geq 2$, the sequence
$\{t_k(n)\}_{n=0}^\infty$ contains palindromes of arbitrary length.
\end{introtheorem1}

In our main result, Theorem
\ref{th:arbitrarilylongpalindromeswithininfiniteblockproducts}, we
generalize this result to a larger class of binary sequences (which
contains the sequences $\{t_k(n)\}$).  These sequences also can be
defined as fixed points of a class of mappings on binary words.

In the course of proving this result, we introduce the concept of the
first difference of a binary sequence.  In Theorem
\ref{th:firstdifferencesofinfiniteproducts} we characterize the first
differences of our class of Thue-Morse type sequences.  The
characterization involves another class of maps, so-called Toeplitz
maps, which we study in Section \ref{preliminaries}.

We relate the first difference to another concept, that of a change
sequence of a binary sequence.  This is a sequence which encodes the
positions at which the sequence changes values.  In a recent paper,
Allouche et al. \cite{relative} determined the change sequence of the
Thue-Morse sequence and proved the following result:

\begin{introtheorem2}[Allouche et al. \cite{relative}]\label{th:intro2}
Let $S$ be the set of integers $n$ such that $t_2(n-1) \not= t_2(n)$,
i.e.,
	\begin{equation*} S = \{1,3,4,5,7,9,11,12,13,15,\ldots \}.
	\end{equation*} Then $S$ is the set of integers $n$ such that
an even power of $2$ exactly divides $n$.  \end{introtheorem2}

In Theorem \ref{th:changesequenceofaninfinitewordproduct} we generalize
this result to our class of Thue-Morse type sequences.

\section{Notation and Preliminaries}\label{preliminaries} We consider
the set $\Sigma^*$ of finite words over the alphabet $\Sigma =
\{0,1\}$.  We also consider the set $\Sigma^{\infty}$ of infinite and
finite words over $\Sigma$.  For a finite word $w$ we let $|w|$ denote
the length of $w$, and we set $|w| = \infty$ if $w$ is an infinite
word.  We denote the $i$th letter of $w$ by $w(i)$, i.e., $w(i) = t_i$
if $w = t_1t_2\ldots t_b$, where $t_k \in \Sigma$ for all $k$.  Given
two words $w_{1}$ and $w_{2}$, we let $w_{1}w_{2}$ denote the word
obtained by the concatenation of $w_2$ to the right of $w_1$.  The
concatenation of an arbitrary finite or infinite sequence of words is
denoted analogously.  We define the \emph{complement} of $w$ to be the
word obtained by interchanging the letters $0$ and $1$ in $w$, or
equivalently, by adding $1$ modulo $2$ to each letter of $w$.  We
denote the complement of $w$ by $\ol{w}$.

We next define two morphisms, $\phi_w$ and $\psi_w$, on $\Sigma^{\infty}$. 
 
Let $w$ be a word with $|w| \geq 2$.  We let $\phi_w:\Sigma^{\infty}\to\Sigma^\infty$ 
be the morphism defined by 
	\begin{align*} 
	\phi_w(0) &= w,	\\ 
	\phi_w(1) &= \ol{w}.	 
	\end{align*} 

It is not hard to see that if $|w| \geq 2$ and $w(1)=0$,  
then there exists a unique fixed point beginning with $0$ of the morphism $\phi_w$;  
i.e., there is a unique infinite word $\textbf{w}$ beginning with $0$ such that 
	\begin{equation*} 
	\textbf{w}	=	\phi_w(\textbf{w}).		 
	\end{equation*} 
Furthermore, $\textbf{w}$ can be obtained by iterating $\phi_w$: 
	\begin{equation*} 
	\textbf{w}	=	\phi_w^\infty(0) := \lim_{n\to\infty}\phi_w^n(0). 
	\end{equation*} 
For example, if $w=01$, then $\textbf{w}$ is the Thue-Morse sequence mentioned in the introduction.
The morphisms $\phi_w$ are special cases of so-called symmetric morphisms; see \cite{frid}.  
 
We also consider a second morphism $\psi_w:\Sigma^{\infty}\to\Sigma^{\infty}$ 
defined by 
	\begin{equation*} 
	\psi_w(a) = wa, 
	\end{equation*} 
where $a \in \Sigma$.  Such a morphism is a special case of the \emph{Toeplitz morphisms} 
(see \cite{toeplitz, toeplitz2}).  It is not hard to see that there is a unique 
fixed point of $\psi_w$ beginning with $w(1)$; i.e., there is a unique infinite 
word $w_*$ with $w_*(1) = w(1)$ such that 
	\begin{equation*} 
	w_*	 =	\psi_w(w_*), 
	\end{equation*} 
and we can obtain $w_*$ by iterating $\psi_w$: 
	\begin{equation*} 
	w_*	= \psi_w^\infty(w(1)) := \lim_{n\to\infty}\psi_w^n(w(1)). 
	\end{equation*} 
The fixed point $w_*$ is of the form
	\begin{equation*}
	w_*	= w\ w_*(1)\ w\ w_*(2)\ w\ w_*(3)\cdots.
	\end{equation*}
This allows one to construct $w_*$ by starting with a sequence of the form
	\begin{equation*}
	w\ \ul{\ }\ w\ \ul{\ }\ w\ \ul{\ }\ \cdots
	\end{equation*}
and successively filling in the ``holes'' with the terms of this sequence.

Allouche et al. \cite[pp. 456--458]{relative} showed that if  
$w=101$, then $w_*$ encodes the places at which the Thue-Morse 
sequence changes values, i.e., $w_*(n)=1$ if and only if $t(n) \not= t(n-1)$. 
 
In Sections \ref{firstdifferencesofwords} and \ref{palindromes} we shall need an operation 
$\oplus$ on the set $\Sigma^*$ that is defined as follows:   
Let $w$ and $v$ be binary words of the same length $b$.  Then 
	\begin{equation*} 
	w_1 \oplus w_2 = (w_1(1)+w_2(1))(w_1(2)+w_2(2))\cdots(w_1(b)+w_2(b)), 
	\end{equation*} 
where addition is taken modulo $2$. 
 
To conclude this section, we define a product operation $\times$ on $\Sigma^*$ as follows: For 
any words $w, v \in \Sigma^*$ with $|v|=c$, set 
	\begin{equation}   
	w \times 0 = w, \quad w \times 1 = \overline{w},  
	\end{equation}   
and   
	\begin{equation}   
	w\times v=(w\times v(1))(w\times v(2))\cdots(w\times v(c)).   
	\end{equation}  
This operation was introduced by Jacobs in  
\cite{jacobs} and was generalized by Hoit \cite{hoit2,hoit} to words over alphabets 
$\{0,1,\ldots,m\}$.  This product is closely related to the morphisms $\phi_w$ defined above;
indeed, it is clear that $w\times v = \phi_w(v)$. 
 
 
 
 
 
\section{Change Sequences}\label{changesequences}   
  
Let $C$ be the set of indices $n$ such that $t_2(n-1) \not= t_2(n)$,  
where   
	\begin{equation*}   
	\{t_2(n)\}_{n=0}^\infty =   
\{0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,\ldots\}   
	\end{equation*}   
is the Thue-Morse sequence.  As stated in the Introduction (see Theorem B), the set $C$ is characterized by the property that $n \in C$ if and only if an even power of  
$2$ exactly divides $n$.  In this section we generalize this result to the class of all fixed points of the morphisms $\phi_w$.  To this end, we introduce the concept of a change sequence of a word as follows: 
   
\begin{definition} 
Let $w$ be a finite or infinite word with $|w|\geq 2$.  We define the change sequence   
$C_w$ of $w$ as the sequence of $n\in\{1,2,\ldots,|w|-1\}$ such that  
$w(n)\neq w(n+1)$.    
\end{definition}   
   
For example, if $w=0010$ and $\textbf{w}$ is the associated infinite word, i.e.,   
	\begin{equation*}   
	\textbf{w}	= 0010001011010010\cdots,   
	\end{equation*}   
then $C_{w} = \{2,3\}$ and $C_{\textbf{w}} = \{2,3,6,7,8,10,11,12,\ldots\}$. 
 
In the following theorem we give a   
general method for determining $C_{\textbf{w}}$ for an arbitrary fixed points
$\textbf{w}$.   
   
\begin{theorem}\label{th:changesequenceofaninfinitewordproduct}   
Let $w$ be a word with $|w|=b \geq 2$ such that $w(1)=w(b)=0$, let $\emph{\textbf{w}} = \phi_w^\infty(0)$, and let $C_w$ be the change sequence of $w$.  Then   
$C_\emph{\textbf{w}}=\{n \in \mathbb{N} : d_b(n) \in C_w\}$, where $d_b(n)$ is the last non-zero digit in the base-$b$ 
representation of $n$.   
\end{theorem}   
\begin{proof} 
 
Let $w=t_1t_2\cdots t_b$.  Since for $1\leq r \leq b-1$ we have $d_b(n) = r$ if and only if 
$n = b^i(bk+r)$ for some $i, k \geq 0$, it suffices to show that   
	\begin{equation}   
	C_{\textbf{w}}=\{b^i(bk+r):i,k\geq 0, \quad r\in C_w\}.   
	\end{equation}     
To prove this, it suffices to show the following two equivalences:   
	\begin{align}\label{changeproof1}   
	r \in C_w &\iff bk+r \in C_{\textbf{w}} \qquad \text{$(k\geq 0$,   
$1\leq r \leq b-1)$}.	\\   
	\label{changeproof2}   
	m \in C_{\textbf{w}} &\iff bm \in C_{\textbf{w}} \qquad \text{$(m   
\geq 1)$}.   
	\end{align}   
   
To prove \eqref{changeproof1}, notice that $\textbf{w} =   
w_0w_1w_2w_3\ldots$ with $w_k \in \{w,\overline{w}\}$   
for all $k$.  Clearly we have $C_w = C_{w_k}$ for all $k$. 
Since the words $w_k$ all have length $b$, for $1 \leq r   
\leq b$ the ($bk+r$)th letter in $\textbf{w}$ is equal to the $r$th   
letter in $w_k$.  Hence, for $1 \leq r \leq b-1$ and all $k$,   
we have $\textbf{w}(bk+r) \not= \textbf{w}(bk+r+1)$ if and only if $w_k(r)   
\not=w_k(r+1)$; i.e., $bk+r \in C_{\textbf{w}}$ if and only if $r \in   
C_{w_k} = C_w$.  This proves \eqref{changeproof1}.   
   
To show that \eqref{changeproof2} holds, fix $m \geq 1$ and choose  
$j \geq 1$ such that $1 \leq m \leq b^j$.  We set 
	\begin{equation*} 
	v = \phi_w^j(t_1) = t_1t_2\cdots t_{b^j} 
	\end{equation*}  
and note that $m\in C_{\textbf{w}}$ if and only if $m\in C_v$.  By definition, $m \in C_v$ if and only if $t_m \neq t_{m+1}$, which is equivalent to  
	\begin{equation*} 
	\phi_w(t_m) = \overline{\phi_w(t_{m+1})}. 
	\end{equation*} 
Now consider 
	\begin{align*} 
	\phi_w(v)	&=	\phi_w^{j+1}(t_1)			\\ 
		&=	\phi_w(t_1)\phi_w(t_2)\cdots\phi_w(t_m)\phi_w(t_{m+1})\cdots 
				\phi_w(t_{b^j})		\\ 
		&=	\phi_w(t_1)\phi_w(t_2)\cdots\phi_w(t_m)\overline{\phi_w(t_{m})}\cdots 
				\phi_w(t_{b^j}). 
	\end{align*} 
Since $|\phi_w(t_i)|=b$ for all $i$ and $\phi_w(t_m)$ begins and ends with the same letter,  
it follows that $m \in C_{\textbf{w}}$ is equivalent to $bm\in C_{\phi_w(v)} \subset C_{\textbf{w}}$.  
\end{proof}   
   
\begin{remark}   
Theorem \ref{th:changesequenceofaninfinitewordproduct} requires that   
$w$ begins and ends with a $0$.  However, it is easy to check that for   
any word $w$ with $w(1)=0$, the word $v = \phi_w(w) = \phi_w(\phi_w(0))$ both 
begins and ends with a $0$. 
Thus we can find the change sequence of $\textbf{w}$ by  
applying Theorem \ref{th:changesequenceofaninfinitewordproduct} to the word $v$ 
and noting that $\textbf{v} = \lim_{n\to\infty}\phi_v^n(0) = 
\lim_{n\to\infty}\phi_w^n(0) = \textbf{w}$.  
\end{remark}   
   
By the result of Allouche et al. quoted in the Introduction (Theorem B), 
the change sequence of $\textbf{01}$ is given by  
	\begin{equation}\label{changeoftm}   
	C_{\textbf{01}} = \{n = 2^{2i}m : i \geq 0, \quad m \text{ odd}\}.   
	\end{equation}   
We now verify this with Theorem  
\ref{th:changesequenceofaninfinitewordproduct}.  Since $w=01$  
ends in a $1$, we must apply the theorem to $v=\phi_{01}(01)=0110$.  We have $|v|=4$ and  
$C_{v}=\{1,3\}$, and so by Theorem  
\ref{th:changesequenceofaninfinitewordproduct} it follows that  
	\begin{align*}   
	C_{\textbf{01}}	&= \{n = 4^i(4k+r) : i,k \geq 0, \quad r  
\in \{1,3\}\}	\\   
				&= \{n = 4^{i}m : i \geq 0, \quad m  
\text{ odd} \}	\\   
				&= \{n = 2^{2i}m : i \geq 0, \quad m  
\text{ odd}\},   
	\end{align*}   
which proves \eqref{changeoftm}.   
 


\section{First Differences}\label{firstdifferencesofwords}   
   
In this section we define the concept of the first difference of a word,   
and we determine the first differences of words $\phi_w^\infty(0)$ for $w(1)=0$.  
First Differences of words over a general alphabet have been used implicitly 
in a recent paper of Frid \cite[pp. 359--360]{frid}.  For first differences 
of infinite integer sequences in a different context, see Chalice \cite{derivatives}. 
 
\begin{definition}   
We define the first difference of a finite or infinite word $w$ to be the word   
	\begin{equation*}   
	\Delta w =(w_1(2)-w_1(1))(w_1(3)-w_1(2))\cdots, 
	\end{equation*}   
where subtraction is interpreted modulo $2$.  
\end{definition}   
   
Note that $|\Delta w| = |w|-1$ for $w$ of finite length.  The following lemma relates the concept  
of a first difference to that of the change sequence introduced in Section \ref{changesequences}.
The proof is trivial.
   
\begin{lemma}\label{lem:connection}   
Let $w$ be a word.  Then $\Delta w(i)=1$ if and only if $i \in C_w$.   
\end{lemma}   
 
Recall the sum operator $\oplus$, defined in Section \ref{preliminaries} as the term-wise addition of two words modulo $2$.  The next lemma states the relationship between the first difference of a sum 
and the sum of the first differences:   
   
\begin{lemma}\label{lem:firstdifferencesofsums}   
Let $w_1$ and $w_2$ be finite words.  Then $\Delta (w_1 \oplus w_2) =   
\Delta w_{1} \oplus \Delta w_{2}$.   
\end{lemma}   

We now turn to the first differences of fixed points $\textbf{w}$.  Notice, for   
example, that if $w=011010$, then $\Delta w = 10111$.  Now consider   
	\begin{equation*}   
	\phi_w(w)	= 011010\ 100101\ 100101\ 011010\ 100101\ 011010.	  
	\end{equation*}   
Computing the first difference of $\phi_w(w)$, we obtain   
	\begin{align*} 
	\Delta(\phi_w(w))	&= 10111\  \ul{1}\  10111\ \ul{0}\ 10111\ \ul{1}\  
10111\ \ul{1}\ 10111\ \ul{1}\ 10111	\\  
		&= \Delta w\ \ul{\Delta w(1)}\ \Delta w\ \ul{\Delta w(2)}\ \Delta w\ \ul{\Delta w(3)}\ \Delta w\ 
\ul{\Delta w(4)}\ \Delta w\ \ul{\Delta w(5)}\ \Delta w	\\   
		&= \psi_{\Delta w}(\Delta w) \Delta w,  
	\end{align*} 
where $\psi_{\Delta w}$ is the map introduced in Section \ref{preliminaries}.  It is not 
hard to see that the latter word $\psi_{\Delta w}(\Delta w)\Delta w$ agrees with 
the word $\psi_{\Delta w}(\psi_{\Delta w}(\Delta w(1)))$ in all but the rightmost 
position.  Since $\phi_w^\infty(0) = \textbf{w}$ and 
$\psi_{\Delta w}^\infty(\Delta w(1)) = (\Delta w)_*$, 
this suggests the following connection between $\Delta\textbf{w}$ and $(\Delta w)_*$: 
   
\begin{theorem}\label{th:firstdifferencesofinfiniteproducts}  
Let $w$ be a word with $|w|=b\geq 2$ and $w(1)=w(b)=0$.  Then the first difference 
of the fixed point of the morphism $\phi_w$ is exactly the fixed point of 
$\psi_{\Delta w}$, i.e., $\Delta\emph{\textbf{w}} = (\Delta w)_*$.   
\end{theorem}   
\begin{proof} 
It is sufficient to show that $\Delta\textbf{w}(i)=1$ if and only if $(\Delta w)_*(i)=1$.  
   
\textit{Case 1}. $i \not\equiv 0 \pmod{b}$.  Then we have $i=bk+r$,   
where $k \geq 0$ and $1\leq r \leq b-1$.  By the construction of   
$(\Delta w)_*$ we have $(\Delta w)_*(i)=1$ if and only if $\Delta w(r)=1$.  By Lemma  
\ref{lem:connection} this holds if and only if $r \in C_w$.  As in the   
proof of Theorem \ref{th:changesequenceofaninfinitewordproduct}, we   
see that    
$r \in C_w$ holds if and only if $i = bk+r \in C_{\textbf{w}}$. Hence,   
$(\Delta w)_*(i)=1$ holds if and only if $i \in C_{\textbf{w}}$, which by   
Lemma \ref{lem:connection} is equivalent to $\Delta\textbf{w}(i)=1$.   
   
\textit{Case 2}. $i \equiv 0 \pmod{b}$.  Then $i=b^{j}m$ for some $j   
\geq 0$, with $m \not\equiv 0 \pmod{b}$.  Now as in the proof of   
Theorem \ref{th:changesequenceofaninfinitewordproduct} we see that   
$b^{j}m \in C_{\textbf{w}}$ (i.e., $\Delta\textbf{w}(b^{j}m)=1$) if and only   
if $m \in C_{\textbf{w}}$.  Since $m \not\equiv 0 \pmod{b}$, by Case $1$ we have $m \in   
C_{\textbf{w}}$ if and only if $(\Delta w)_*(m)=1$.  By the construction of $(\Delta w)_*$ we see that 
the latter is equivalent to $(\Delta w)_*(i) = 1$.   
\end{proof}   
 
 
 
\section{Palindromes}\label{palindromes}   
We now turn our attention to palindromes.  
Recall that the complement $\overline{w}$ is the word obtained by  
interchanging $0$ and $1$ in $w$.  If $|w|$ is finite, then we define the  
\emph{reversal} $w^R$ to be the word $w$ written ``backwards''; that  
is, for $|w|=b$,   
	\begin{equation*}   
	w^R=w(b)w(b-1) \cdots w(2)w(1).   
	\end{equation*}   
   
The complement and reversal operations have the following properties,  
whose proofs are immediate from the definitions.   
   
\begin{proposition}\label{prop:miscellaneousproperties}   
\mbox{}   
	\begin{itemize}   
	\item[(i)] $(\overline{w})^R=\overline{w^R}$.   
	\item[(ii)] $(w^R)^R=\overline{\overline{w}}=w$.   
	\item[(iii)] $(\Delta w)^R=\Delta(w^R)$ .  
	\item[(iv)] $(w_{1}w_{2} \cdots w_{n})^R =  
w_n^R w_{n-1}^R\cdots w_1^R$.   
	\end{itemize}   
\end{proposition}   
   
\begin{definition}\label{def:quasi}    
A \emph{palindrome} is a word $w$ such that $w^R = w$.  A  
\emph{skew-palindrome} is a word $v$ such that $v^R =  
\overline{v}$.  If a word is either a palindrome or a skew-palindrome, then  
it is said to be a \emph{quasi-palindrome}.  We denote the sets of  
palindromes, skew-palindromes, and quasi-palindromes by $\mathcal{P}$,  
$\mathcal{S}$, and $\mathcal{Q}$, respectively.  
\end{definition}   
   
For example, the words $0110110$ and $011001$ are both quasi-palindromes.  
Specifically, the word $0110110$ is a palindrome and the word $011001$ is 
a skew-palindrome.
   
\begin{proposition}\label{prop:propertiesofquasi-palindromes}  
Let $w$ and $v$ be words of lengths $b$ and $c$, respectively.  Then:   
\mbox{}   
	\begin{itemize}   
	\item[(i)] $w\in\mathcal{P}$ if and only if $w(i)=w(b-i+1)$  
for $1\leq i \leq b$.    
	\item[(ii)] $v\in\mathcal{S}$ if and only if $v(j)\neq  
v(c-j+1)$ for $1\leq j \leq c$.    
	\item[(iii)] $v\in\mathcal{S}$ implies that $|v|$ is even.   
	\item[(iv)] $w\in\mathcal{P}$ if and only if $w\oplus w^R =  
00\cdots 0$;  $v\in\mathcal{S}$ if and only if $w\oplus w^R =  
11\cdots 1$.  
	\item[(v)] $\mathcal{P}\cap\mathcal{S}=\emptyset$.   
	\end{itemize}   
\end{proposition}   
\begin{proof}   
(i) and (ii) follow from Definition \ref{def:quasi}.  To prove (iii),   
observe that if $|v|=c$ were odd, then $v(j)=v(c-j+1)$ for $j=\lceil   
c/2 \rceil$, which violates (ii).  The last two properties follow from  
(i) and (ii).   
\end{proof}   
   
Recall that the product of two words $w$ and $v$ is defined by 
	\begin{equation*} 
	w \times v = \phi_w(v). 
	\end{equation*} 
Given two sets of words $\mathcal{U}$ and $\mathcal{V}$, we let $\mathcal{U} \times  
\mathcal{V}$ denote the set of all words $u \times v$, with $u \in \mathcal{U}$ and 
$v\in\mathcal{V}$.  We show that quasi-palindromes are closed with 
respect to this product operation. 
 
\begin{proposition}\label{prop:closureofquasi-palindromes}  
Let $w$ and $v$ be finite words.  Then $w$,$v\in\mathcal{Q}$ if and only   
if $w\times v \in \mathcal{Q}$.  Moreover, we have the following  
containment relations:  
	\begin{align}   
		\label{prop:closure1}  
	\mathcal{P} \times \mathcal{P} &\subset \mathcal{P},	\\   
		\label{prop:closure2}  
	\mathcal{P} \times \mathcal{S} &\subset \mathcal{S},	\\   
		\label{prop:closure3}  
	\mathcal{S} \times \mathcal{P} &\subset \mathcal{S},	\\   
		\label{prop:closure4}  
	\mathcal{S} \times \mathcal{S} &\subset \mathcal{P}. 
	\end{align}   
\end{proposition}   
\begin{proof}   
Suppose first that $w$,$v \in \mathcal{P}$ with $|w|=b$ and $|v|=c$.  
Then   
	\begin{equation*}   
	w \times v = \phi_w(v) = w_1w_2\cdots w_c,   
	\end{equation*}   
with $w_i=\phi_w(v(i))$ for $1\leq i \leq c$.  Notice for each  
$i$ that we have $w_i \in \{w,\overline{w}\} \subset \mathcal{P}$.  
Applying Proposition \ref{prop:miscellaneousproperties} (iv), we  
obtain   
	\begin{align*}   
	(\phi_w(v)) \oplus (\phi_w(v))^R	&= w_1 w_2 \cdots w_c \oplus w_c^R w_{c-1}^R \cdots w_1^R   
\\    
			&= (w_1 \oplus w_c^R)(w_2 \oplus   
w_{c-1}^R)\cdots (w_c \oplus w_1^R).   
	\end{align*}   
Since $v \in \mathcal{P}$, Proposition \ref{prop:propertiesofquasi-palindromes} (i) implies 
	\begin{align*}   
	w_{i}	&=	\phi_w(v(i))		\\   
		&=	\phi_w(v(c-i+1))\notag	\\   
		&=	w_{c-i+1}. \notag   
	\end{align*}   
Since $w_i \in \mathcal{P}$, it follows from this and Proposition \ref{prop:propertiesofquasi-palindromes} (iv) that 
	\begin{align*}   
	(w_i \oplus w_{c-i+1}^R)	&= (w_i \oplus w_i^R)	\\   
			&= 00\cdots0. 
	\end{align*}   
Hence   
	\begin{equation*}   
	(\phi_w(v)) \oplus (\phi_w(v))^R = 00\cdots 0,   
	\end{equation*}   
which implies that $\phi_w(v) \in  
\mathcal{P}$.  This proves \eqref{prop:closure1}.  The relations  
\eqref{prop:closure2}--\eqref{prop:closure4} can be proved by similar  
arguments.  It follows from (10.1)--(10.4) that $\phi_w(v) \in \mathcal{Q}$ whenever $w \in \mathcal{Q}$ and $v \in \mathcal{Q}$. 
   
Conversely, suppose $\phi_w(v) \in \mathcal{Q}$.  Then $\phi_w(v)$ is given by 
	\begin{equation*} 
	\phi_w(v) = \phi_w(v(1))\phi_w(v(2))\cdots \phi_w(v(c)).   
	\end{equation*}  
By definition $\phi_w(v) \in \mathcal{Q}$ implies that either   
	\begin{equation*}   
	\phi_w(v) = (\phi_w(v))^R   
	\end{equation*}   
or   
	\begin{equation*}   
	\overline{\phi_w(v)} = (\phi_w(v))^R.   
	\end{equation*}   
In particular, we have   
	\begin{equation*}   
	\phi_w(v(1))	= (\phi_w(v(c)))^R   
	\end{equation*}   
or   
	\begin{equation*}   
	\ol{\phi_w(v(1))}	= (\phi_w(v(c)))^R.   
	\end{equation*}   
It follows that either $w = w^R$ or $\overline{w} =   
w^R$, and in any case we have $w \in \mathcal{Q}$.  It remains to be  
shown that $v \in \mathcal{Q}$, and to do this we again distinguish  
several cases. Suppose first that $w \in \mathcal{P}$ and $\phi_w(v)  
\in \mathcal{S}$.  Now $\phi_w(v)$ is of the form   
	\begin{equation*}   
	\phi_w(v) = \phi_w(v(1))\phi_w(v(2))\cdots \phi_w(v(c)).   
	\end{equation*}   
By our assumption that $\phi_w(v) \in \mathcal{S}$ it follows that  
	\begin{equation}\label{eq:closureproof2}   
	\overline{\phi_w(v(i))} = (\phi_w(v(c-i+1)))^R 
	\end{equation}   
for $1 \leq i \leq c$.  If $v(i)=0$, then \eqref{eq:closureproof2} and our assumption $w \in   
\mathcal{P}$ implies that $v(c-i+1)=1$.  Likewise, $v(i)=1$ implies that   
$v(c-i+1)=0$.  Hence we have $v(i) \neq v(c-i+1)$ for all $i$, so $v  
\in \mathcal{S}$ by Proposition  
\ref{prop:propertiesofquasi-palindromes} (ii).  The proofs of the  
remaining cases are similar.  
\end{proof}   
   
We now characterize first differences of palindromes.   
   
\begin{lemma}\label{lem:firstdifferencesofquasi-palindromes}   
Given a finite word $w\in\Sigma^*$ with $|w|\geq 2$, we have $w\in\mathcal{Q}$ if and only if   
$\Delta w\in\mathcal{P}$.   
\end{lemma}   
\begin{proof}   
Applying Proposition \ref{prop:propertiesofquasi-palindromes} (iv), it follows that $\Delta w \in \mathcal{P}$ is equivalent to 
	\begin{align*}   
	00\cdots0	&= \Delta w \oplus (\Delta w)^R  \\  
			&= \Delta w \oplus \Delta(w^R)   
&(\text{Prop.} \ \ref{prop:miscellaneousproperties} (\text{iii}))		\\   
			&= \Delta(w \oplus w^R)  
&(\text{Lemma} \ \ref{lem:firstdifferencesofsums}).  
	\end{align*}   
Hence $w \oplus w^R$ is either $00\cdots 0$ or   
$11\cdots 1$, and by Proposition  
\ref{prop:propertiesofquasi-palindromes} (iv) this is equivalent to $w  
\in \mathcal{Q}$.  
\end{proof}     

We now consider palindromes in infinite words of the form 
	\begin{equation*}
	w_* = \psi_w^\infty(w(1))
	\end{equation*}
introduced in Section \ref{preliminaries}.
   
\begin{lemma}\label{lem:arbitrarilylongpalindromeswithinself-generatingwords}  
Let $w$ be a finite word.  If $w_*$ contains arbitrarily long palindromes,  
then $w$ itself is a  
palindrome.  
\end{lemma}   
\begin{proof}   
Let $v$ be a subword of $w_*$ that is a palindrome.  Then $v$ is of the form   
	\begin{equation}\label{eq:v}   
	v=x[u_1]w[u_2]w\cdots w[u_n]y,   
	\end{equation}   
where $[u_i]$ for $1 \leq i \leq n$ are the letters filling the  
``holes'' arising in the construction of $w_*$, and $x$ and $y$ are a  
suffix and prefix of $w$, respectively.  (We allow the possibility that $x$ or $y$ 
or both are empty.)   
   
Suppose first that $|x|=|y|$.  If we subtract $|x|+1$ letters from  
each side of \eqref{eq:v}, then the remaining word   
	\begin{equation}   
	v_0 = w[u_2]w[u_3] \cdots [u_{n-1}]w   
	\end{equation}   
is still a palindrome.  Notice that $v_0$ both begins and ends with   
$w$.  Since $v_0 \in \mathcal{P}$, it follows that $w = w^R$,   
and hence $w \in \mathcal{P}$.  
   
Now assume without loss of generality that $|x| > |y|$.  Let $|w|=b$,   
and let $|x| = b-m$ for some $m$ with $0 \leq m < b$.  Then $|y| =   
b-m-r$ for some $r$ with $1 \leq r \leq b-m$ (since $|x| > |y|$).   
Now let $x_1$ be the suffix of $x$ of length $|x|-|y|-1$, so that   
$|x_1|=r-1$.  If we remove $|y|+1$ letters from each side of $v$, then   
the resulting word   
	\begin{equation}\label{eq:v_1}   
	v_1 = x_1[u_1]w[u_2] \cdots [u_{n-1}]w   
	\end{equation}   
must still be a palindrome.  Since $x_1$ is a suffix of $w$, we can   
write $w$ as   
	\begin{equation}\label{eq:w}   
	w = aw(b-r+1)x_1,   
	\end{equation}   
where $a$ is the prefix of $w$ of length $b-r$, and $w(b-r+1)$ is the  
$(b-r+1)$st letter of $w$.  Substituting   
\eqref{eq:w} into \eqref{eq:v_1} we obtain  
	\begin{equation}\label{eq:v_1new}   
	v_1 = x_1[u_1]aw(b-r+1)x_1[u_2] \cdots [u_{n-1}]aw(b-r+1)x_1.   
	\end{equation}   
Subtracting $r-1$ letters from each side of \eqref{eq:v_1new}, we  
obtain  
	\begin{equation}\label{eq:v_2}   
	v_2 = [u_1]aw(b-r+1)x_1[u_2] \cdots [u_{n-1}]aw(b-r+1), 
	\end{equation} 
which again is a palindrome.  Since $v_2 \in \mathcal{P}$, it follows that   
	\begin{align*}   
	[u_1]aw(b-r+1)	&= ([u_{n-1}]aw(b-r+1))^R	\\   
			&= w(b-r+1) a^R [u_{n-1}].   
	\end{align*}   
Hence $[u_{1}] = w(b-r+1) = [u_{n-1}]$.  Proceeding inductively (by  
removing at each step $b+1$ letters from each side) we see that $[u_1]  
= [u_2] = \cdots = [u_{n-1}]$.  Since, by assumption, $w_*$ contains  
arbitrarily long palindromes, we can take $n$ in \eqref{eq:v}  
arbitrarily large.  In particular, the ``holes'' arising in the  
construction of $w_*$ must include arbitrarily long strings of  
consecutive $0$'s or consecutive $1$'s.  This is only possible if $w =  
00\cdots0$ or $w = 11\cdots1$.  Thus $w$ is a palindrome.  
\end{proof}   
   
\begin{remark}   
The converse of the lemma is also true (though we will not need this  
fact here):  If $w$ is a palindrome, then   
$w_*$ contains arbitrarily long palindromes. 
\end{remark}   
   
We are now ready to state and prove our main result, giving us a necessary and 
sufficient condition for a fixed point \textbf{w} to contain palindromes of arbitrary 
length.  For similar subject matter, see Hof, Knill, and Simon \cite{knill}.
 
\begin{theorem}\label{th:arbitrarilylongpalindromeswithininfiniteblockproducts}   
Let $w$ be a finite word with $|w| = b\geq 2$, and $w(1)=0$.  Then  
$\emph{\textbf{w}}$ contains arbitrarily long palindromes if and only if $w$ is  
a quasi-palindrome.   
\end{theorem}   
\begin{proof}   
Suppose first that $w\in\mathcal{Q}$.  Then by Proposition   
\ref{prop:closureofquasi-palindromes} we have $\phi_w(w) \in \mathcal{P}$,  
and hence $\phi_w^{2n+1}(w)\in\mathcal{P}$  
for all $n$.  Thus $\phi_w^\infty(w) = \textbf{w}$ contains arbitrarily long palindromes.  
  
Conversely, if $\textbf{w}$ contains arbitrarily long palindromes, then by  
Lemma \ref{lem:firstdifferencesofquasi-palindromes} its first difference 
$\Delta\textbf{w}$ also contains  
arbitrarily long palindromes.  If $w(b) = 0$, then we can apply  Theorem  
\ref{th:firstdifferencesofinfiniteproducts} to conclude that   
$(\Delta w)_*$ contains arbitrarily long palindromes.  By  
Lemma  \ref{lem:arbitrarilylongpalindromeswithinself-generatingwords}  
it follows that $\Delta w\in\mathcal{P}$, which by Lemma  
\ref{lem:firstdifferencesofquasi-palindromes} implies that $w \in \mathcal{Q}$.  
If $w(b) = 1$, then we cannot apply Theorem  
\ref{th:firstdifferencesofinfiniteproducts} directly to $w$.  However, we  
may apply the theorem to the word $u = \phi_w(w)$ to obtain $\Delta\textbf{w} = 
\Delta\textbf{u} = (\Delta u)_*$.  It follows that  
$(\Delta u)_*$ contains arbitrarily long palindromes.  As  
before, this implies that $\phi_w(w) =  u \in \mathcal{Q}$.  By  
Proposition \ref{prop:closureofquasi-palindromes} it follows that $w  
\in \mathcal{Q}$.  
\end{proof}   
 

\begin{thebibliography} {99}

\bibitem{relative} Jean-Paul Allouche, Andr{\'e} Arnold, Jean Berstel,
Sre{\v{c}}ko Brlek, Simon Plouffe, and Bruce E. Sagan, A relative of
the Thue-Morse sequence, \emph{Discrete Math.} \textbf{139} (1995),
455--461.

\bibitem{toeplitz} Jean-Paul Allouche and Roland Bacher, Toeplitz
sequences, paperfolding, Towers of Hanoi and progression-free sequences
of integers, \emph{Enseign.\ Math.} \textbf{38} (1992), 315--327.

\bibitem{ubiquitous} Jean-Paul Allouche and Jeffrey Shallit, The
ubiquitous Prouhet-Thue-Morse sequence,
\emph{Sequences and Their Applications:  Proceedings of SETA '98},
Springer Ser.\ Discrete
Math.\ Theor.\ Comput.\ Sci., Springer, London, 1999, pp.\ 1--16.

\bibitem{palindromes} Jean-Paul Allouche and Jeffrey Shallit, 
\href{http://dmtcs.loria.fr/volumes/abstracts/dm040101.abs.html}{Sums of digits, overlaps, and palindromes},
\emph{Discrete Math.\ Theor.\ Comp.\ 
Sci.} \textbf{4} (2000), 1--10 (electronic).

\bibitem{toeplitz2} Julien Cassaigne and Juhani Karhum{\"a}ki, Toeplitz
words, generalized periodicity and periodically iterated morphisms,
\emph{European J. Combin.} \textbf{18} (1997), 497--510.

\bibitem{derivatives} D.~Chalice, How to differentiate and integrate
sequences, \emph{Amer.\ Math.\ Monthly} \textbf{108} (2001), 911--921.

\bibitem{frid} Anna E.~Frid, Overlap-free symmetric D0L words,
\emph{Discrete Math.\ Theor.\ Comput.\ Sci.} \textbf{4} (2001), 357--362.

\bibitem{knill} A.~Hof, O.~Knill, and B.~Simon, Singular continuous
spectrum for palindromic Schr{\"o}dinger operators, \emph{Comm.\ Math.\ 
Phys.} \textbf{174} (1995), 149--159.

\bibitem{hoit2} A.~Hoit, The distribution of generalized sum-of-digits
functions, Ph.D. thesis, Univ. of Illinois, Urbana-Champaign, 1999.

\bibitem{hoit} A.~Hoit, Block products, preprint, 2002.

\bibitem{jacobs} K.~Jacobs, Maschinenerzeugte 0-1-folgen, \emph{Selecta
Math.} \textbf{1} (1969), 1--27.


\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11B85; Secondary 68R15.

\noindent \emph{Keywords:}   Thue-Morse,
binary sequence,
first difference,
palindrome,
skew-palindrome,
quasi-palindrome,
change sequence,
cross product,
block product,
Toeplitz morphism.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A010060}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received September 6 2002;
revised versions received   April 28 2003; December 2 2003.
Published in {\it Journal of Integer Sequences},
December 12 2003.


\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                



\end{document}