<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}

\usepackage{tikz}
\usetikzlibrary{arrows,automata,positioning}
\usetikzlibrary {arrows.meta}

\usepackage{cases}
\usepackage[normalem]{ulem}

\newcommand{\stkout}[1]{\ifmmode\text{\sout{\ensuremath{#1}}}\else\sout{#1}\fi}

\def\modd#1 #2{#1\ \mbox{\rm (mod}\ #2\mbox{\rm )}}

\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}}}

\begin{document}

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

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

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

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

\begin{center}
\vskip 1cm{\LARGE\bf 
The Analog of Overlap-Freeness \\
\vskip .1in
for the Period-Doubling Sequence}
\vskip 1cm
\large
James D.\ Currie \\
Department of Mathematics and Statistics \\
The University of Winnipeg \\
Winnipeg, MB R3B 2E9 \\
Canada \\
\href{mailto: j.currie@uwinnipeg.ca}{\tt j.currie@uwinnipeg.ca}
\end{center}

\vskip .2 in

\begin{abstract}
Good words are defined to be binary words avoiding the
factors $11$ and $1001$, and the patterns $0000$ and $00010100$. We show that good words bear the same relationship to the period-doubling sequence that overlap-free words bear to the Thue-Morse sequence. We prove an analog of Fife's theorem for good words, exhibit the lexicographically least and greatest infinite good words, and determine the patterns avoided by the period doubling word.
\end{abstract}

\section{Introduction}

Let $A$ be a finite set.
A {\em word} over {\em alphabet} $A$ is a finite or infinite sequence over $A$. We use lower case letters to denote finite words, writing, for example, word $w=w_1w_2\cdots w_n$, where each $w_i\in A$. The {\em length} of $w$ is denoted by $|w|=n$. The {\em empty word}, of length 0, is denoted by $\epsilon$. A {\em non-empty word} is a word of positive length.  The {\em concatenation} of two words $u=u_1u_2\cdots u_n$ and $v=v_1v_2\cdots v_m$ is given by $uv=u_1u_2\cdots u_n v_1v_2\cdots v_m$. If $u, v, w, z$ are words and $w=uzv$, we say that word $u$ is a {\em prefix} of $w$, word $v$ is a {\em suffix} of $w$, and word $z$ is a {\em factor} of $w$. We say that $\langle u,z,v\rangle$ is an {\em occurrence of $z$ in $w$}, and that $z$ {\em occurs} in $w$ with {\em index} $|u|$. The set of finite words over $A$ is denoted by $A^*$. 

Let $A$ and $B$ be alphabets. A {\em morphism} from $A^*$ to $B^*$ is a function respecting concatenation; i.e., $f(xy)=f(x)f(y)$ for all $x,y\in A^*$. Thus $f$ is generated by its values on the elements of $A$. If $f(x)$ is non-empty whenever $x$ is non-empty, we call $f$ {\em non-erasing}. 
Let $p\in A^*$ and $w\in B^*$. We say that $w$ {\em encounters the pattern} $p$ if we can write $w=uf(p)v$ for some $u,v\in B^*$, and some non-erasing morphism $f$. Otherwise, we say that $w$ {\em avoids} $p$. An {\em overlap} is a word $v$ such that we can write $v=xyxyx$ for words $x$ and $y$ where $x$ is non-empty. If no factor of $w$ is an overlap, then $w$ is {\em overlap-free}. A word is overlap-free if and only if it avoids patterns $xxx$ and $xyxyx$. If $x$ is non-empty and $k$ is a positive integer, we  denote by $x^k$ the word consisting of $x$ repeated $k$ times in a row. A {\em fourth power} is a word $x^4$ where $x\ne \epsilon$.
The {\em reversal} of finite word $w=w_1w_2\cdots w_n$ is the word $w_nw_{n-1}\cdots w_1$. A word over $\{0,1\}$ is called a {\em binary word}. The complement of a binary word $w$ is obtained by replacing 0's with 1's and vice versa. 

\begin{example} Consider the word $u=\alpha\beta\beta\gamma\beta\beta\gamma\beta\alpha\alpha \in\{\alpha,\beta,\gamma\}^*$. Then $u$ has the factor $\beta\beta\gamma$. There are two occurrences of $\beta\beta\gamma$ in $u$, namely $\langle \alpha,\beta\beta\gamma,\beta\beta\gamma\beta\alpha\alpha \rangle$ and $\langle \alpha\beta\beta\gamma,\beta\beta\gamma,\beta\alpha\alpha \rangle$, so that $\beta\beta\gamma$ occurs in $u$ with index 1, and with index 4. Factor $\beta\beta\gamma\beta\beta\gamma\beta$ of $u$ is an overlap, with $x=\beta$, $y=\beta\gamma$. Thus $u$ is not overlap-free.

The word $v=0101010101=(01)^5$ contains overlaps $01010$ and $10101$, and fourth powers $(01)^4$ and $(10)^4$. The reversal of $v$ is $1010101010$, which is also the complement of $v$.

The word $bananas$ can be written $bananas=uf(pear)v$, where $u=ba$, $f(p)=f(a)=n$, $f(e)=a$, $f(r)=as$, $v=\epsilon$. Thus $bananas$ encounters the pattern $pear$. It also encounters $apple$, letting $u=v=\epsilon$, $f(a)=b$, $f(p)=an$, $f(l)=a$, $f(e)=s$. However, $apple$ avoids $bananas$ (since the image of $bananas$ under any non-erasing morphism has length 7 or more, whereas $|apple|=5$).
\end{example}


We use bold-face letters for infinite words, writing ${\boldsymbol w}=w_1w_2w_3\cdots$, where each $w_i\in A$. Thus we are concerned with infinite words where the domain is the positive integers, and we refer to them 
as {\em one-way infinite words} (in contrast to {\em two-way infinite words} where the domain would be the set of all integers). The set of finite words over $A$ is denoted by $A^*$, and the set of one-way infinite words is denoted by $A^\omega$.

Iteration of a morphism $f$ is denoted by exponentiation: 
\begin{displaymath}
f^i(x) = \begin{cases}
	  x,                 &amp; \text{ if $i=0$;}\\
	  f(f^{i-1}(x)), &amp; \text{ if $i&gt;0$.}
\end{cases}
\end{displaymath}

If $f:A^*\rightarrow A^*$ is a morphism such that for some $a\in A$, $|f(a)|&gt;1$ and the first letter of $f(a)$ is $a$, then $f^{n-1}(a)$ is a prefix of $f^n(a)$ for every positive integer $n$. We can then define ${\boldsymbol w}=\lim_{n\rightarrow\infty}f^n(a)$ to be the unique one-way infinite word such that for each $n$, word $f^n(a)$ is a prefix of ${\boldsymbol w}$; thus ${\boldsymbol w}$ is a fixed point of $f$. 


The famous Thue-Morse sequence ${\bf t}$ is a fixed point of the binary morphism $\mu$ given by $\mu(0)=01$, $\mu(1)=10$, namely 
\[{\bf t}=\lim_{n\rightarrow\infty}\mu^n(0).\]

It is sequence \seqnum{A010060} in the On-Line Encyclopedia of Integer Sequences (OEIS) \cite{oeis}.


Thue \cite{thue12} introduced ${\bf t}$ and proved that it is overlap-free. The sequence is also nascent in an earlier paper of Thue \cite{thue06}, where it could be obtained by applying Satz 6 to Satz 3. It is also implicit in an early memoir of Prouhet \cite{prouhet51} on multigrades.
\begin{theorem} Let $w$ be an overlap-free binary word. Then $\mu(w)$ is overlap-free.
\end{theorem}
He also showed that, in the case of two-sided infinite words and circular words, every overlap-free binary word is the image under $\mu$ of an overlap-free word \cite{thue12}. The analysis of words with `ends' is more complicated, but finite overlap-free binary words also arise via iterating $\mu$. (See Restivo and Salemi \cite{restivo84} for example.)
\begin{theorem}\label{thue.factorization} Let $w\in\{0,1\}^*$ be a finite overlap-free word. Then we can write $w=a\mu(u)b$, where $a, b\in\{\epsilon,0,00,1,11\}$, and $u$ is overlap-free. If $|w|\ge 7$ this factorization is unique. If ${\boldsymbol w}$ is a one-sided infinite overlap-free word, then we can write ${\boldsymbol w}=a\mu({\boldsymbol u})$, for some one-sided infinite overlap-free word ${\boldsymbol u}$ where $a\in\{\epsilon,0,00,1,11\}$.
\end{theorem}

Restivo and Salemi used their version of Theorem~\ref{thue.factorization} to give a rough enumeration of binary overlap-free words. Kobayashi \cite{kobayashi88} gave a better enumeration, obtaining a good lower bound by counting finite words which extend to infinite overlap-free words. For this, he used the deep theorem of Fife  \cite{fife80} characterizing the infinite overlap-free words.  The problem of enumerating binary overlap-free words was finally completely solved by Jungers, Protasov, and Blondel \cite{jungers09}, and by Guglielmi and Protasov \cite{guglielmi13}.

Because of Theorem~\ref{thue.factorization}, the
word ${\bf t}$ turns up frequently in the study of overlap-free binary words. An example is the following result of Berstel \cite{berstel94} (later greatly generalized by Allouche et al.\  \cite{allouche98}):
\begin{theorem}
The lexicographically greatest one-sided infinite overlap-free binary word starting with $0$ is 
${\bf t}$.
\end{theorem}

The relationship between ${\bf t}$ and $\mu$ was also key to establishing the following theorem of Shur \cite{shur96}:
\begin{theorem} Suppose ${\bf t}$ encounters a pattern $p\in\{0,1\}^*$. Then either $p$ is a factor of ${\bf t}$, or $p$ is one of $00100$ and $11011$. 
\end{theorem}

Another famous binary sequence is the period-doubling sequence, which is the fixed point
\[{\boldsymbol d}=01000101010001000100010101000101\cdots\]
of the binary morphism $\delta$ where $\delta(0)=01$, $\delta(1)=00$.  This sequence has been much studied in the context of quasi-crystal spectral theory. (See Damanik \cite{damanik00}, for example.) It 
 is sequence \seqnum{A096268} in the On-Line Encyclopedia of Integer Sequences (OEIS) \cite{oeis}.

Call a binary word $w$ {\em good} if it does not contain the factor $11$ or $1001$, and does not encounter either of the patterns $0000$ or $00010100$. We will show that ${\boldsymbol d}$ is good. In fact, we show that the period doubling morphism $\delta$ has the same relationship to good words that $\mu$ has to overlap-free words, namely
\begin{theorem}\label{f.good}Suppose $w$ is good. Then $\delta(w)$ is good.
\end{theorem}
\begin{theorem}\label{main.theorem} Let $w$ be a finite good word. Then we can write $w=a\delta(u)b$, where $a\in\{\epsilon,0,1\}$, $b\in\{\epsilon,0\}$, and $u$ is good. If $|w|\ge 4$ this factorization is unique. If ${\boldsymbol w}$ is a one-sided infinite good word, then we can write ${\boldsymbol w}=a\delta({\boldsymbol u})$, for a one-sided infinite good word ${\boldsymbol u}$ where $a\in\{\epsilon,0,1\}$.
\end{theorem}

We build on these theorems to
\begin{itemize}
\item Give a version of Fife's theorem for good words, characterizing infinite good words;
\item Exhibit lexicographically extremal one-sided infinite good words; 
\item Characterize the binary patterns avoided by ${\boldsymbol d}$.
\end{itemize}

\section{Good words}

Unless otherwise specified, our words and morphisms are over the binary alphabet $\{0,1\}$. We record morphisms inline, i.e., $g=[g(0),g(1)]$.

\begin{lemma}\label{delta.inverse.good}
Let $u$ be a finite binary word. Suppose $\delta(u)$ is good. Then $u$ is good. \end{lemma}
\begin{proof} If $u$ encounters pattern $0000$ or $00010100$, so does $\delta(u)$. If $u$  has factor $11$ or $1001$, then $\delta(u)$ has factor $\delta(11)=0000$ or $\delta(1001)=00010100$, and thus encounters pattern $0000$ or $00010100$.\end{proof}

\begin{remark} \label{parity} Let $w=w_1w_2w_3\cdots w_{2n}$ with $w_i\in\{0,1\}$. Word $w$ can be written as $w=\delta(u)$ for some $u$ if and only if $w_i=0$ for each odd index $i$.
\end{remark}
\begin{lemma}\label{factorization}
Let $w$ be a finite binary word with no factor $11$, $1001$, or $0000$. Then we can write $w=a\delta(u)b$ where $a\in\{\epsilon,0,1\}$ and $b\in\{\epsilon,0\}$. If $|w|\ge 4$ this factorization is unique. If ${\boldsymbol w}$ is a one-sided infinite word with no factor $11$, $1001$, or $0000$, then we can write ${\boldsymbol w}=a\delta({\boldsymbol u})$, some one-sided infinite word ${\boldsymbol u}$ where $a\in\{\epsilon,0,1\}$.
\end{lemma}
\begin{proof} First we demonstrate the existence of the factorization for finite words:  If $|w|_1\le 1$ then $w$ is a factor of $0001000$, and the result is established by a finite check. Suppose $|w|_1\ge 2$. If $10^k1$ is a factor of $w$, the conditions on $w$ force $k=1$ or $k=3$. By induction, if $1u1$ is a factor of $w$ then $|1u|$ is even; therefore, all the $1$'s in $w$ have an index in $w$ of the same parity. If the parity of the indices of $1$'s is even, let $|a|=0$; let $|b|$ be $0$ (resp., $1$) if $|w|$ is even (resp., odd).  If the parity of the indices of $1$'s is odd, let $|a|=1$; let $|b|$ be $1$ (resp., $0$) if $|w|$ is even (resp., odd). By Remark~\ref{parity} we can write $a^{-1}wb^{-1}=\delta(u)$ for some $u$. 

We have shown that we can write $w=a\delta(u)b$ and $a,b\in\{\epsilon, 0,1\}$. Suppose that $b=1$. Recall that $|w|_1\ge 2$. The parity of the indices of $a$ and $b$ is different, so we cannot have $a=1$. It follows that $|\delta(u)|_1\ge 1$. Then $\delta(u)1$ must have suffix $011$, $01001$, or $00001$, none of which are good. This is a contradiction so in fact $b\in \{\epsilon, 0\}$.
 
Now we show the uniqueness of the factorization for finite words: Suppose $|w|\ge 4$ and $w$ has two factorizations $w=a_1\delta(u_1)b_1=a_2\delta(u_2)b_2$. If $|a_1|=|a_2|$ we are forced to choose $a_1=a_2$, $u_1=u_2$, and $b_1=b_2$, so the factorizations are identical. Suppose without loss of generality then that $|a_1|=0$, $|a_2|=1$. Then by Remark~\ref{parity}, every $1$ in $a_1\delta(u_1)b_1$ has even index, but 
every $1$ in $a_2\delta(u_2)b_2$ has even index. Since $a_1\delta(u_1)b_1=w=a_2\delta(u_2)b_2$, we conclude that $|w|_1=0$, so that $w$ has $0000$ as a prefix, which is impossible. 

Now suppose that ${\boldsymbol w}$ is a one-sided infinite good word. For each non-negative $n$, let the length $n$ prefix of ${\boldsymbol w}$ be $p_n$. 
We have proved that finite words can be factored, so write each $p_n=a_n\delta(u_n)b_n$ where $a_n,b_n\in\{\epsilon,0,1\}$. Word $p_4$ cannot be $0000$, so that $|w_4|_1&gt;0$. By Remark~\ref{parity}, the index of the first $1$ in $w_4$ determines $a_4$ and all subsequent $a_n$, so that $a_n=a_4$ for $n\ge 4$. This implies that $\delta(u_n)$ is a prefix of $\delta(u_{n+1})$ for $n\ge 4$, so that $u_{n+4}$ is a prefix of $u_{n+5}$ for all $n$. 
Let ${\boldsymbol u}=\lim_{n\rightarrow\infty} u_{n+4}$.
Then
\begin{align*}{\boldsymbol w}&amp;=\lim_{n\rightarrow\infty} w_n\\
&amp;=\lim_{n\rightarrow\infty} w_{n+4}\\
&amp;=\lim_{n\rightarrow\infty} w_{n+4}b_{n+4}^{-1}\\
&amp;=\lim_{n\rightarrow\infty} a_4\delta(u_{n+4})\\
&amp;=a_4\lim_{n\rightarrow\infty} \delta(u_{n+4})\\
&amp;=a_4\delta(\lim_{n\rightarrow\infty} u_{n+4})\\
&amp;=a_4\delta({\boldsymbol u}).
\end{align*}
\end{proof}

\begin{proof}[Proof of Theorem~\ref{main.theorem}] This is immediate from Lemmas~\ref{delta.inverse.good} and \ref{factorization}.\end{proof}

Call a non-erasing morphism $g$ {\em even} if, for every letter $u$, $|g(u)|$ is even.
\begin{lemma}\label{even.lengths}
Let $p$ be a  pattern and let $w$ be a binary word. Suppose that $g(p)$ is a factor of $\delta(w)$ where $g$ is an even morphism. Then $w$ encounters pattern $p$.
\end{lemma}
\begin{proof}Write $p=u_1\cdots u_n$ with the $u_i$ letters. Write $\delta(w)=aU_1\cdots U_nb$, where $U_i=g(u_i)$ for each $i$. If $|a|$ is even, $w=\delta^{-1}(a)\delta^{-1}(U_1\cdots U_n)\delta^{-1}(b)$, and $w$ contains the instance $\delta^{-1}(g(p))$ of $p$.

If $|a|$ is odd, then $0$ is the last letter of $a$ and of each $U_i$. Thus
$$\delta(w)=a0^{-1}0U_10^{-1}0U_20^{-1}0\cdots U_n0^{-1}0b,$$
and $w$ contains the instance $\delta^{-1}(h(p))$ of $p$, where $h$ is the morphism defined on the letters of $p$ by $h(u_i)=0g(u_i)0^{-1}$.\end{proof}
\begin{lemma}\label{uvu} Let $w,u,v$ be binary words and suppose that $uvu$ is a factor of $\delta(w)$. If $|u|_1&gt;0$ then $|uv|$ is even.
\end{lemma}

\begin{proof} Since $uvu$ has period $|uv|$, $\delta(w)$ has a factor $1z1$ where $|1z|=|uv|$. The Lemma follows by Remark~\ref{parity}.
\end{proof}


\begin{proof}[Proof of Theorem~\ref{f.good}] To begin with, we show that $\delta(w)$ does not contain $11$, $0000$, $1001$, or $00010100$ as a factor. By Remark~\ref{parity}, $\delta(w)$ does not have a factor $11$ or $1001$. If $\delta(w)$ has factor $0000$, write $\delta(w)=a0000b$ for words $a$ and $b$. If $|a|$ is even, then $w$ has prefix $\delta^{-1}(a0000)$, which ends in $11$. This is impossible; if $|a|$ is odd, then the last letter of $a$ is $0$, so that $w$ has prefix $\delta^{-1}((a0^{-1})0000)$, which again ends in $11$. Finally, if $00010100$ is a factor of $\delta(w)$, then $w$ contains factor $\delta^{-1}(00010100)=1001$, which is impossible. (The index of $00010100$ in $\delta(w)$ must be odd by Remark~\ref{parity})

Suppose now that $\delta(w)$ encounters pattern $p=0000$, so that $XXXX$ is a factor of $\delta(w)$ for some non-empty $X$. Since $\delta(w)$ does not have $0000$ as a factor, we must have $|X|_1&gt;0$. Using $u=X$ and $v=\epsilon$ in Lemma~ \ref{uvu}, we conclude that $|X|$ is even. Then Lemma~ \ref{even.lengths}  implies that $w$ encounters $0000$, which is a contradiction.

Suppose that $\delta(w)$ encounters pattern $p=00010100$, so that $X^3YXYXX$ is a factor of $\delta(w)$ for some non-empty $X$ and $Y$. Suppose that $|X|_1&gt;0$. Since $XX$ is a factor of $\delta(w)$,  letting $u=X$ and $v=\epsilon$ in Lemma~ \ref{uvu} implies that $|X|$ is even. Again, since $XYX$ is a factor of $\delta(w)$,  letting $u=X$ and $v=Y$ in Lemma~ \ref{uvu} implies that $|XY|$ is even. It follows that $|Y|$ is even. Then Lemma~ \ref{even.lengths}  implies that $w$ encounters $00010100$, which is a contradiction. We therefore conclude that $|X|_1=0$, so that $X=0^n$ for some $n\ge 1$. Since $XX=0^{2n}$ is a factor of $\delta(w)$, but $0000$ is not, we conclude that $n=1$ and $X=0$. Thus $\delta(w)$ contains the factor $XXXYXYXX=000Y0Y00$.


Since $0000$ is not a factor of $\delta(w)$, the first letter of $Y$ is $1$. If $Y=1$, then 
$\delta(w)$ has factor $00010100$, which is impossible. Therefore $|Y|&gt;1$.

Suppose $Y$ ends in $0$. If $Y$ ends in $10$, then $\delta(w)$ contains factor $1001$ (inside $Y0Y$), which is impossible. If $|Y|$ ends in $00$, then $000Y0Y00$ ends in $Y00$, hence $0000$, which is again impossible. Thus $Y$ ends in $1$, hence in $01$. Write $Y=1Z1$ for some non-empty word $Z$. Word $\delta(w)$ has the factor $0001Z101Z100$.

If $|1Z1|=3$, then $\delta(w)$ contains $01Z101Z1=01010101$, an instance of $0000$, already proved impossible. It follows that $|1Z1|\ge 4$. If $Z$ begins $01$, then $Z10$ begins either $0101$ or $0100$. However, if $Z10$ begins $0101$ then, since $Z$ ends in $0$, $Z101Z10$ again contains $01010101$; if $Z10$ begins $0100$ then $0001Z10$ begins $00010100$, which is not a factor of $\delta(w)$.
We conclude that $Z$ does not begin $01$ and therefore begins $00$. 

If $Z10$ begins $001$ then $1Z10$ has the impossible factor $1001$. Thus  
$Z10$ begins $0001$. We now consider suffixes of $Z$. 
If $Z$ ends $10$, then $01Z$ ends either $1010$ or $0010$. However, if $01Z$ ends $1010$ then, since $Z$ begins with $0$, $01Z101Z$ contains $10101010$, an instance of $0000$, which is impossible; if $01Z$ ends in $0010$ then $101Z100$ ends $00010100$, which is not a factor of $\delta(w)$.
We conclude that $Z$ does not end $10$ and therefore ends $00$.
If $01Z$ ends $0100$ then $\delta(w)$ contains $01Z1$, hence the impossible factor $1001$. Thus  $01Z$ ends in $1000$. Since $Z$ begins $00$, this forces $01Z101Z$ to contain $00010100$, which is impossible.\end{proof}

\begin{corollary} The period-doubling word ${\boldsymbol d}$ is good.
\end{corollary}
\begin{theorem}\label{o.s.i.good} Let ${\bf w}$ be a one-sided infinite binary word. Then ${\boldsymbol w}$ is good if and only if $\delta({\boldsymbol w})$ is good.
\end{theorem}
\begin{proof}
 If $w_n$ is the length $n$ prefix of ${\bf w}$ then ${\bf w}=\lim_{n\rightarrow\infty}w_n$ and 
$
\delta({\bf w})=\lim_{n\rightarrow\infty}\delta(w_n)$. 
By Theorem~\ref{f.good} and Lemma~\ref{delta.inverse.good}, $w_n$ is good if and only if $\delta(w_n)$ is good.
\begin{align*}
{\bf w}\text{ is good }&amp;\iff\text{each }w_n\text{ is good }\\
&amp;\iff\text{each }\delta(w_n)\text{ is good }\\
&amp;\iff\lim_{n\rightarrow\infty}\delta(w_n)=\delta(\lim_{n\rightarrow\infty}w_n)=\delta({\bf w})\text{ is good.}
\end{align*}
\end{proof}


\begin{remark}\label{symmetry} While the set of binary overlap-free words is closed under complementation and reversal, the same is not true of good words. For example, $00101000$ is good, but neither its complement nor its reversal is good.
\end{remark}

\section{An analog of Fife's theorem}

We characterize the one-sided infinite good words, developing a theory analogous to Fife's \cite {fife80} theory for overlap-free binary words; however, we follow Rampersad's \cite{rampersad07} exposition of Fife, with appropriate modifications, rather than Fife's original paper. Let $G$ be the set of one-sided infinite good words.



\begin{lemma}\label{slide}
Suppose ${\boldsymbol u}$ is a one-sided infinite good word. Then $1{\boldsymbol u}$ is good if and only if $01{\boldsymbol u}$ is good.
\end{lemma}
\begin{proof}
Clearly if $01{\boldsymbol u}$ is good then $1{\boldsymbol u}$ is good. Suppose that $1{\boldsymbol u}$ is good but $01{\boldsymbol u}$ is  not. By Theorem~\ref{main.theorem}, write $1{\boldsymbol u}=1\delta({\boldsymbol v})$ for some ${\boldsymbol v}$.
Since $1{\boldsymbol u}$ is good, $01{\boldsymbol u}$ must have a prefix which is either factor $11$ or $1001$, or a pattern instance $g(0000)$ or $g(00010100)$ where $g=[X,Y]$ is some non-erasing morphism. Clearly neither of $11$ and $1001$ can be a prefix of $01{\boldsymbol u}$, so $01{\boldsymbol u}$ has a prefix $XXXX$ or $XXXYXYXX$ where $X$ and $Y$ are non-empty. 

Suppose $01{\boldsymbol u}$ has prefix $XXXX$. Write $X=0X'$. Since $|XXXX|$ is even, word $01{\boldsymbol u}=\delta(0{\boldsymbol v})$ has $XXXX0=0X'0X'0X'0X'0$ as a prefix. But now the good word  
$1{\boldsymbol u}$ contains the fourth power $X'0X'0X'0X'0$, which is a contradiction.

Now suppose that $01{\boldsymbol u}$ has prefix $XXXYXYXX$. Write $X=0X'$. If $X'=\epsilon$, then $X=0$. However then the length 2 prefix of  $01{\boldsymbol u}$ is $XX=00$, which is impossible. Thus $X'\ne\epsilon$, forcing $01$ to be a prefix of $X$, so that $|X|_1&gt;0$. Since $01{\boldsymbol u}=\delta(0{\boldsymbol v})$, considering the second $XX$ in $XXXYXYXX$, by Lemma~\ref{uvu} with $u=X$, $v=\epsilon$ we find that $|X|$ is even. Again,  $XYX$ is a factor of $\delta(0{\boldsymbol v})$, so applying Lemma~\ref{uvu} with $u=X$, $v=Y$ shows that $|XY|$ is also even. Since both $|X|$ and $|XY|$ are even, $|Y|$ is even. 
Since $|XXX|$ is even, $XXX0$ is a prefix of $01{\boldsymbol u}=\delta(0{\boldsymbol v})$, so that we can write 
$Y=0Y'$. Since $|XXXYXYXX|$ is even, word $01{\boldsymbol u}=\delta(0{\boldsymbol v})$ has $XXXYXYXX0=0X'0X'0X'0Y'0X'0Y'0X'0X'0$ as a prefix. But now the good word  
$1{\boldsymbol u}$ contains $X'0X'0X'0Y'0X'0Y'0X'0X'0=g'(00010100)$ where $g'=[X'0,Y'0]$. This is a contradiction.
\end{proof}
\begin{remark} This result uses the fact that  ${\boldsymbol u}$ is one-sided infinite. If $u=010101$, then $1u$ is good, but $01u=(01)^4$  is not.
\end{remark}

Let $G$ be the set of one-sided infinite good words. For $w\in\{0,1\}^*$, let $G_w=G\cap w\{0,1\}^\omega$.


\begin{lemma}\label{allouche}Let ${\boldsymbol w}$ be a one-sided infinite binary word.
\begin{enumerate}
\item[(a)] $\delta({\boldsymbol w})\in G\iff {\boldsymbol w}\in G$;
\item[(b)] $1\delta({\boldsymbol w})\in G\iff 0{\boldsymbol w}\in G$;
\item[(c)] $0\delta({\boldsymbol w})\in G\iff$ ($1{\boldsymbol w}\in G$) or (${\boldsymbol w}\in G_{001}$).
\end{enumerate}
\end{lemma}
\begin{remark} The cases in (c) are disjoint, since if $001$ is a prefix of ${\bf w}$, then $1{\bf w}$ has prefix $1001$ and is not good.
\end{remark}
\begin{proof}[Proof of (a)] This is just Theorem~\ref{o.s.i.good}. 
\end{proof}

\begin{proof}[Proof of (b)] If $0{\boldsymbol w}\in G$, then by Theorem~\ref{o.s.i.good}, $\delta(0{\boldsymbol w})=01\delta({\boldsymbol w})\in G$, so in particular $1\delta({\boldsymbol w})\in G$. 

In the other direction, suppose $1\delta({\boldsymbol w})\in G$. Applying Lemma~\ref{slide} to prefixes gives $01\delta({\boldsymbol w})=\delta(0{\boldsymbol w})\in G$. By Theorem~\ref{o.s.i.good}, $0{\boldsymbol w}\in G$.\end{proof}

\begin{proof}[Proof of (c)] If $1{\boldsymbol w}\in G$, then by Theorem~\ref{o.s.i.good} $\delta(1{\boldsymbol w})=00\delta({\boldsymbol w})\in G$, so in particular $0\delta({\boldsymbol w})\in G$. 

Suppose ${\boldsymbol w}\in G_{001}$. By Theorem~\ref{o.s.i.good}, $\delta({\boldsymbol w})\in G$. Suppose $0\delta({\boldsymbol w})\not\in G$. It, therefore, has a prefix $XXXX$ or $XXXYXYXX$ where $X$ is non-empty. Since $001$ is a prefix of ${\bf w}$, $p=0010100$ is a prefix of $0\delta({\bf w})$. The prefix $XXX$ of $0\delta({\bf w})$ has period $|X|$. If $|X|&lt;|p|$, then $|X|$ is a period of $p$, which has least period 5. We conclude that $|X|\ge 5$. This implies that, $|X|_1&gt;0$. The second $XX$ in $XXX$ is a factor of $\delta({\bf w})$. By Lemma~\ref{uvu} with $u=X$, and $v=\epsilon$, we conclude that $|X|$ is even. Therefore $|X|\ge 6$. Since $0^{-1}X$ is an odd-length prefix of $\delta({\boldsymbol w})$, $0$ is a suffix of $X$. 

If $|X|=6$ then the prefix $0^{-1}XXX$ of $\delta({\bf w})$ ends in $0XX=0$ $001010$ $001010$, which has prefix $00010100$. This is impossible, since $\delta({\bf w})\in G$. If $|X|&gt;6$, then $p=0010100$ is a prefix of $X$, and $0$ is a suffix of $X$, so factor $XX$ of $\delta({\bf w})$ contains $0$ $0010100$, again an impossibility.

In the other direction, suppose that $0\delta({\bf w})\in G$. Then ${\boldsymbol w}\in G$ by Theorem~\ref{o.s.i.good}, and we show that either $1{\boldsymbol w}\in G$, or  ${\boldsymbol w}\in 001\{0,1\}^*$. Suppose that $1{\boldsymbol w}\not\in G$ and $001$ is not  a prefix of ${\bf w}$. It follows that 
a prefix of $1{\boldsymbol w}$ has the form $11$, $1001$, $XXXX$, or $XXXYXYXX$ with non-empty $X$ and/or $Y$. 

By Theorem~\ref{main.theorem}, write ${\boldsymbol w}=a\delta({\boldsymbol u})$ where $a\in\{\epsilon,0,1\}$. 

If $11$ is a prefix of $1{\boldsymbol w}$, then $a=1$, and $10$ is a prefix of  ${\boldsymbol w}$. However, then $0\delta({\boldsymbol w})$ has prefix $0\delta(10)=00001$, and is not good.

If $1001$ is a prefix of $1{\boldsymbol w}$, then  $001$ is a prefix of ${\bf w}$, which is a contradiction.

Suppose $XXXX$ is a non-empty prefix of $1{\boldsymbol w}$. Then the final $XX$ of $XXXX$ is a factor of $\delta({\boldsymbol u})$ and $|X|_1&gt;0$, so by Lemma~\ref{uvu}, $|X|$ is even. Since $X$ is a prefix of $1{\boldsymbol w}$, the first letter of $X$ is $1$. Since $XX$ is a factor of ${\boldsymbol w}$, and ${\boldsymbol w}$ has no factor $11$, the last letter of $X$ is $0$. Write $X=1X'0$.

Word ${\boldsymbol w}$ has prefix $X'01X'01X'01X'0c$ for some $c\in\{0,1\}$.
This implies that $0\delta({\boldsymbol w})$ has prefix
\begin{align*}
0\delta(X'01X'01X'01X'0c)&amp;=0\delta(X'0)\delta(1)\delta(X'0)\delta(1)\delta(X'0)\delta(1)\delta(X'0)\delta(c)\\
&amp;=0\delta(X'0)00\delta(X'0)00\delta(X'0)00\delta(X'0)0\overline{c}\\
&amp;=(0\delta(X'0)0)^4\overline{c},
\end{align*}
and $0\delta({\boldsymbol w})$ contains a fourth power. This is a contradiction, since $0\delta({\boldsymbol w})\in G$.

Suppose $XXXYXYXX$ is a prefix of $1{\boldsymbol w}$. This means that $XX$ and $XYX$ are factors of $\delta({\boldsymbol u})$, and $|X|_1&gt;0$. We conclude by Lemma~\ref{uvu} that $|X|$ and $|Y|$ are even. The first letter of $X$ is $1$. Since $XX$ and $YX$ are factors of ${\boldsymbol w}$, and ${\boldsymbol w}$ has no factor $11$, the last letter of each of  $X$ and $Y$ is $0$. Write $X=1X'0$ and $Y=cY'0$ where $c\in\{0,1\}$. Since $X'01$ is an even length prefix of $a\delta({\boldsymbol u})$, Remark~\ref{parity} forces $a=\epsilon$.


Then 
${\boldsymbol w}$ has prefix $X'01X'01X'01Y'01X'01Y'01X'01X'0d$ for some $d\in\{0,1\}$.
Therefore $0\delta({\boldsymbol w})$ has prefix
\begin{align*}
&amp;0\delta(X'01X'01X'0cY'01X'0cY'01X'01X'0d)\\
&amp;=  0X^{\prime\prime}
               0X^{\prime\prime}
               0X^{\prime\prime}
\overline{c}Y^{\prime\prime}
               0X^{\prime\prime}
\overline{c}Y^{\prime\prime}
               0X^{\prime\prime}
               0X^{\prime\prime}\overline{d}\\
&amp;=h(00010100)\overline{d},
\end{align*}
where $X^{\prime\prime}=\delta(X')010$,  $Y^{\prime\prime}=\delta(Y')010$, and $h=[0\delta(X')010,\overline{c}\delta(Y')010]$. This is a contradiction, since $0\delta({\boldsymbol w})\in G$.
\end{proof}

Suppose $w\in\{0,1\}^*$ has a suffix $\delta^n(01)$, $n\ge 0$, and let $n$ be as large as possible. Write $w=y\delta^{n}(01)$. Define mappings $\alpha$, $\beta$ and $\gamma$ on $w$ by
\begin{align*}
\alpha(w)&amp;=w\delta^n(00)=y\delta^{n+1}(01)\\
\beta(w)&amp;=w\delta^n(0100)=y\delta^{n+1}(001)\\
\gamma(w)&amp;=w\delta^n(010100)=y\delta^{n+1}(0001).
\end{align*}
For example, if $w=0001000101$, then $y=00$, $n=2$, $\delta^n(0)=0100$, $\delta^n(1)=0101$, so that 
\begin{align*}
\alpha(w)&amp;= 00\text{ }0100\text{ }0101\text{ }0100\text{ }0100\\
\beta(w)&amp;= 00\text{ }0100\text{ }0101\text{ }0100\text{ }0101\text{ } 0100\text{ }0100\\
\gamma(w)&amp;= 00\text{ }0100\text{ }0101\text{ }0100\text{ }0101\text{ }0100\text{ }0101\text{ } 0100\text{ }0100.
\end{align*}
Let ${\boldsymbol f}=f_1f_2f_3\cdots, \text{ where each } f_i\in B=\{\alpha,\beta,\gamma\}$. Suppose $w$ has some suffix $\delta^n(01)$. Then $w$ is a proper prefix of $f_1(w)$, which is a proper prefix of $f_2(f_1(w))$, which is a proper prefix of $f_3(f_2(f_1(w)))$, etc. We define the infinite composition
${\boldsymbol x} = (\cdots\circ f_3 \circ f_2 \circ f_1)(01)$ to be the one-sided infinite word
\[{\boldsymbol x}=\lim_{n\rightarrow\infty} f_n(f_{n-1}(\cdots f_2(f_1(w))\cdots ),\] 
which has each $f_n(f_{n-1}(\cdots f_2(f_1(w))\cdots )$ as a prefix. Following Rampersad, we use the notation ${\boldsymbol x} = w\bullet{\boldsymbol f}$. 


Let $u\in B^k$. Then 

\begin{equation}\label{2.3.01}
01\bullet u{\boldsymbol f} = (01\bullet u)\delta^k(01)^{-1}\delta^k({\boldsymbol x}).\end{equation}

Define the sets $I$ and $F$ by
\begin{align*}
I &amp;=(\beta+\gamma)(\alpha\alpha)^*\alpha(\gamma+\beta\beta)\cup\gamma(\alpha\beta)^*\alpha\gamma, \\
F &amp;= B^\omega-B^*IB^\omega.
\end{align*}
\begin{theorem}\label{fife01}
Let ${\boldsymbol x}\in\{0, 1\}^\omega$.
If ${\boldsymbol x}$ begins with $01$, then ${\boldsymbol x}$ is good if and only if ${\boldsymbol x}= 01\bullet {\boldsymbol f}$ for some
${\boldsymbol f}\in F$.
\end{theorem}

We follow the notation of Berstel, also used by Rampersad. Here $I$ stands for `ideal', and $B^*IB^\omega$ is the ideal generated by $I$, consisting of the forbidden factors for $F$. 

Let
$W = \{{\boldsymbol f}\in B^\omega
: 01\bullet{\boldsymbol f}\in G\}$. 
To prove Theorem~\ref{fife01} it is enough to prove that $W = F$.
Let $L\subseteq\Sigma^\omega$
 and let $x\in\Sigma^*$. We define the (left) quotient $x^{-1}L$ by
$x^{-1}L= \{{\boldsymbol y} \in  \Sigma^\omega 
: x{\boldsymbol y} \in  L\}$.
The next lemma establishes several
identities concerning quotients of the set $W$. They are proved using (\ref{2.3.01}) and Lemma~\ref{allouche}. The identities demonstrate that $W$ is precisely the set of infinite labeled paths through the automaton ${A_{01}}$ given in
Figure~\ref{automaton}. These are just the labeled paths omitting factors in $I$, so that  $W = F$. Thus, proving Lemma~\ref{identities} establishes Theorem~\ref{fife01}.

\begin{lemma}\label{identities}The following identities hold:
\begin{enumerate}\item[(a)]$W = \alpha^{-1}W$;
\item[(b)]$(\beta\alpha\alpha)^{-1}W=(\beta\beta)^{-1}W=\beta^{-1}W$;
\item[(c)]$(\beta\alpha\beta)^{-1}W=\gamma^{-1}W=(\beta\gamma)^{-1}W=(\gamma\gamma)^{-1}W$;
\item[(d)]$(\beta\alpha)^{-1}W=(\gamma\alpha)^{-1}W$;
\item[(e)]$(\beta\alpha\gamma)^{-1}W=(\gamma\beta)^{-1}W=\emptyset$.
\end{enumerate}
\end{lemma}
Each set of identities corresponds to the state of ${A_{01}}$ with the same label as the identities. The non-accepting sink (e) is not shown in the figure.

\begin{figure}
\begin{center}
\begin{tikzpicture}[shorten &gt;=1pt,node distance=100pt,auto]

  \tikzstyle{every state}=[fill={rgb:black,1;white,10}]


  \node[state,initial]   (a)                      {$a$};
  \node[state] (b) [above right of=a]  {$b$};
  \node[state] (c) [below right of=a] {$c$};
  \node[state]           (d) [below right of=b]     {$d$};

  \path[-&gt;,arrows = {Latex[width=7pt, length=7pt]-},every loop/.style={arrows = {-Latex[width=7pt, length=7pt]}}]

  (a)   edge [loop right]    node {$\alpha$} (a)
  (b) edge  node {$\beta$} (a)
       edge  [loop above] node {$\beta$} (b)
       edge  [bend right] node {$\alpha$} (d)
  (c) edge   node {$\gamma$} (a)
       edge [bend right]  node {$\beta$} (d)
       edge [loop below]    node {$\gamma$} (c)
       edge   node {$\gamma$} (b)
  (d) edge [bend right]  node {$\alpha$} (b)
       edge  [bend right] node {$\alpha$} (c)
 ;
\end{tikzpicture}
\caption{`Fife' automaton ${A_{01}}$ for $G_{01}$.}
\label{automaton}
\end{center}
\end{figure}
\begin{proof}
Suppose ${\boldsymbol f}\in B^*$. Let $01\bullet{\boldsymbol f} = {\boldsymbol x}$. Thus $01$ is a prefix of ${\boldsymbol x}$.
\begin{enumerate}
\item[(a)] We have 
 \begin{align*}
\alpha{\boldsymbol f}\in W&amp;\iff 01\bullet\alpha{\boldsymbol f}\in G\\
&amp;\iff(01\bullet\alpha)\delta(01)^{-1}\delta({\boldsymbol x})\in G\\
&amp;\iff \stkout{0100(0100)}^{-1}\delta( {\boldsymbol x})\in G\\
&amp;\iff {\boldsymbol x}\in G\\
&amp;\iff 01\bullet{\boldsymbol f}\in G\\
&amp;\iff {\boldsymbol f}\in W,
\end{align*} 
so that $\alpha^{-1}W=W$.

\item[(b)] Here \begin{align*}
\beta{\boldsymbol f}\in W&amp;\iff 01\bullet\beta{\boldsymbol f}\in G\\
&amp;\iff (01\bullet\beta)\delta(01)^{-1}\delta({\boldsymbol x})\in G\\
&amp;\iff 01~\stkout{0100(0100)}^{-1}\delta({\boldsymbol x})\in G\\
&amp;\iff \delta(0{\boldsymbol x})\in G\iff 0{\boldsymbol x}\in G.
\end{align*}

Similarly we find that \begin{align*}
\beta\beta{\boldsymbol f}\in W&amp;\iff 01\bullet\beta\beta{\boldsymbol f}\in G\\
&amp;\iff (01\bullet\beta\beta)\delta^2(01)^{-1}\delta^2({\boldsymbol x})\in G\\
&amp;\iff 010100~\stkout{01000101(01000101)}^{-1}\delta^2({\boldsymbol x})\in G\\
&amp;\iff \delta(0\delta(0{\boldsymbol x}))\in G\\
&amp;\iff 0\delta(0{\boldsymbol x})\in G\\
&amp;\iff 10{\boldsymbol x}\in G\text{ or }0{\boldsymbol x}\in G_{001}\\
&amp;\iff 0{\boldsymbol x}\in G.
\end{align*}
Here we use the fact that $01$ is a prefix of ${\boldsymbol x}$, so that  $10{\boldsymbol x}\not\in G$ and $0{\boldsymbol x}\in 001\{ 0,1 \}^\omega$.

Finally we get 
\begin{align*}
\beta\alpha\alpha{\boldsymbol f}\in W&amp;\iff 01\bullet\beta\alpha\alpha{\boldsymbol f}\in G\\
&amp;\iff (01\bullet\beta\alpha\alpha)\delta^3(01)^{-1}\delta^3({\boldsymbol x})\in G\\
&amp;\iff 01\delta^3({\boldsymbol x})\in G\\
&amp;\iff \delta(0\delta^2({\boldsymbol x}))\in G\\
&amp;\iff 0\delta^2({\boldsymbol x})\in G\\
&amp;\iff 1\delta({\boldsymbol x})\in G\text{ or }\delta({\boldsymbol x})\in G_{001}\\
&amp;\iff 1\delta({\boldsymbol x})\in G\\
&amp;\iff 0{\boldsymbol x}\in G.
\end{align*}
Here again note that $01$ is a prefix of $\delta({\boldsymbol x})$.
We have shown that $(\beta\alpha\alpha)^{-1}W=(\beta\beta)^{-1}W=\beta^{-1}W$, as desired.

\item[(c)] We have \begin{align*}
\gamma{\boldsymbol f}\in W&amp;\iff 01 \bullet\gamma{\boldsymbol f}\in G\\
&amp;\iff (01\bullet\gamma)\delta(01)^{-1}\delta({\boldsymbol x})\in G\\
&amp;\iff 0101~\stkout{0100(0100)}^{-1}\delta({\boldsymbol x})\in G\\
&amp;\iff \delta(00{\boldsymbol x})\in G\\
&amp;\iff 00{\boldsymbol x}\in G.
\end{align*}
We also find 
\begin{align*}
\beta\alpha\beta{\boldsymbol f}\in W&amp;\iff 01\bullet\beta\alpha\beta{\boldsymbol f}\in G\\
&amp;\iff(01\bullet\beta\alpha\beta)\delta^3(01)^{-1}\delta^3({\boldsymbol x})\in G\\
&amp;\iff 0101000101\delta^3({\boldsymbol x})\in G\\
&amp;\iff \delta(0\delta^2({0\boldsymbol x}))\in G\\
&amp;\iff 0\delta^2(0{\boldsymbol x})\in G\\
&amp;\iff 1\delta(0{\boldsymbol x})\in G\text{ or }\delta(0{\boldsymbol x})\in G_{001}\\
&amp;\iff 1\delta(0{\boldsymbol x})\in G\\
&amp;\iff 00{\boldsymbol x}\in G.
\end{align*}
Similarly, we get 
\begin{align*}
\beta\gamma{\boldsymbol f}\in W&amp;\iff 01\bullet\beta\gamma{\boldsymbol f}\in G\\
&amp;\iff(01\bullet\beta\gamma)\delta^2(01)^{-1}\delta^2({\boldsymbol x})\in G\\
&amp;\iff 0101000100~\stkout{01000101(01000101)}^{-1}\delta^2({\boldsymbol x})\in G\\
&amp;\iff\delta(0\delta(00{\boldsymbol x}))\in G\\
&amp;\iff 0\delta(00{\boldsymbol x})\in G\\
&amp;\iff 100{\boldsymbol x}\in G\text{ or }00{\boldsymbol x}\in G_{001}\\
&amp;\iff 00{\boldsymbol x}\in G.
\end{align*}
We also have 
\begin{align*}
\gamma\gamma{\boldsymbol f}\in W&amp;\iff 01\bullet\gamma\gamma{\boldsymbol f}\in G\\
&amp;\iff (01\bullet\gamma\gamma)\delta^2(01)^{-1}\delta^2({\boldsymbol x})\in G\\
&amp;\iff 010101000100~\stkout{01000101(01000101)}^{-1}\delta^2({\boldsymbol x})\in G\\
&amp;\iff\delta^2(100{\boldsymbol x})\in G\\
&amp;\iff 100{\boldsymbol x}\in G.
\end{align*}
Finally, suppose $00{\boldsymbol x}\in G$. Then $0001$ is a prefix of  $00{\boldsymbol x},$ and by Theorem~\ref{main.theorem} we can write $00{\boldsymbol x}=\delta(10{\boldsymbol y})$, some  $10{\boldsymbol y}\in G$. Then
by Lemma~\ref{slide}, $010{\boldsymbol y}\in G$. Thus $\delta(010{\boldsymbol y})=0100{\boldsymbol x}\in G$, and in particular, $100{\boldsymbol x}\in G$. We conclude that 
$100{\boldsymbol x}\in G\iff 00{\boldsymbol x}\in G$, which gives the desired result.

\item[(d)] In this case we see that
\begin{align*}
\beta\alpha{\boldsymbol f}\in W&amp;\iff 01\bullet\beta\alpha{\boldsymbol f}\in G\\
&amp;\iff(01\bullet\beta\alpha)\delta^2(01)^{-1}\delta^2({\boldsymbol x})\in G\\
&amp;\iff 01~\stkout{01000101(01000101)}^{-1}\delta^2({\boldsymbol x})\in G\\
&amp;\iff\delta(0\delta({\boldsymbol x}))\in G\\
&amp;\iff 0\delta({\boldsymbol x})\in G\\
&amp;\iff 1{\boldsymbol x}\in G\text{ or }{\boldsymbol x}\in G_{001}\\
&amp;\iff 1{\boldsymbol x}\in G.
\end{align*}
Also we have
\begin{align*}
\gamma\alpha{\boldsymbol f}\in W&amp;\iff 01\bullet\gamma\alpha{\boldsymbol f}\in G\\
&amp;\iff(01\bullet\gamma\alpha)\delta^2(01)^{-1}\delta^2({\boldsymbol x})\in G\\
&amp;\iff 0101~\stkout{01000101(01000101)}^{-1}\delta^2({\boldsymbol x})\in G\\
&amp;\iff\delta(00\delta({\boldsymbol x}))\in G\\
&amp;\iff\delta^2(1{\boldsymbol x})\in G\iff 1{\boldsymbol x}\in G.
\end{align*}

Thus $(\beta\alpha)^{-1}W=(\gamma\alpha)^{-1}W$.

\item[(e)] Here

\begin{align*}
\beta\alpha\gamma{\boldsymbol f}\in W&amp;\iff 01\bullet\beta\alpha\gamma{\boldsymbol f}\in G\\
&amp;\iff(01\bullet\beta\alpha\gamma)\delta^3(01)^{-1}\delta^3({\boldsymbol x})\in G\\
&amp;\iff 
010100010101000101\delta^3({\boldsymbol x})\in G\\
&amp;\iff\delta(0\delta^2(00{\boldsymbol x}))\in G\\
&amp;\iff 0\delta^2(00{\boldsymbol x})\in G\\
&amp;\iff 1\delta(00{\boldsymbol x})\in G\text{ or }\delta(00{\boldsymbol x})\in G_{001}\\
&amp;\iff 1\delta(00{\boldsymbol x})\in G\\
&amp;\iff 000{\boldsymbol x}\in G.
\end{align*}
But $000{\boldsymbol x}$ has prefix $0000$. Thus $(\beta\alpha\gamma)^{-1}W=\emptyset$.
We also find
\begin{align*}
\gamma\beta{\boldsymbol f}\in W&amp;\iff 01\bullet\gamma\beta{\boldsymbol f}\in G\\
&amp;\iff(01\bullet\gamma\beta)\delta^2(01)^{-1}\delta^2({\boldsymbol x})\in G\\
&amp;\iff 01010100~\stkout{01000101(01000101)}^{-1}\delta^2({\boldsymbol x})\in G\\
&amp;\iff\delta^2(10{\boldsymbol x})\in G\\
&amp;\iff 10{\boldsymbol x}\in G.
\end{align*}

But $10{\boldsymbol x}$ has prefix $1001$, so $(\gamma\beta)^{-1}W=\emptyset$.
\end{enumerate}
\end{proof}

  We have
\[G=G_{01}\cup G_{001}\cup G_{0001}\cup G_1.\]
We can write Theorem~\ref{fife01} as \[G_{01}=01\bullet W.\] 

 By Lemma~\ref{slide}, ${\boldsymbol x}\in G_1$ if and only if 
$0{\boldsymbol x}\in G_{01}$, so that \[G_{1}=0^{-1}G_{01}.\] Also, by Theorem~\ref{main.theorem} and Theorem~\ref{f.good}, \[G_{0001}=\delta(G_{1}),\] since $G_{10}=G_1$.
If ${\boldsymbol x}\in G_{001}$, we can write ${\boldsymbol x}=0\delta(0{\boldsymbol y})$ for some ${\boldsymbol y}$. However, by Lemma~\ref{allouche} we get
\begin{align*}
0\delta(0{\boldsymbol y})\in G
\iff &amp;10{\boldsymbol y}\in G\text{ or }0{\boldsymbol y}\in G_{001}\\
\iff&amp; 010{\boldsymbol y}\in G\text{ or }0{\boldsymbol y}\in G_{001}\text{ by Lemma~\ref{slide}}\\
\iff&amp; 010{\boldsymbol y}\in G_{01}\text{ or }0{\boldsymbol y}\in G_{001}\\
\iff&amp; 0{\boldsymbol y}\in (01)^{-1}G_{01}\text{ or }0{\boldsymbol y}\in G_{001}\\
\iff&amp; 0\delta(0{\boldsymbol y})\in0\delta((01)^{-1}G_{01}\cup G_{001}),\text{ so that}
\end{align*}
\[G_{001}=0\delta((01)^{-1}G_{01}\cup G_{001}).\]

We summarize these results in a theorem. 
\begin{theorem}\label{fullfife}The following identities hold:
\begin{align*}
G_{01}&amp;= 01\bullet W;\\
G_{001}&amp;= 0\delta((01)^{-1}G_{01}\cup G_{001});\\
G_{0001}&amp;= \delta(G_{1});\\
G_{1}&amp;= 0^{-1}G_{01}.
\end{align*}
\end{theorem}

Since $I$ is a regular language one could give an enumeration of finite prefixes of $G_{01}$ (and hence $G_{0001}$, $G_1$) following the approach of Kobayashi \cite{kobayashi88}. This would give a lower bound on good words of length $n$.
Obtaining an enumeration of all prefixes of $G$ would involve dealing with the 
recursion in the equation for $G_{001}$, and would give a better lower bound on the number of length $n$ good words.

It would be nice to remove the recursion in the equation for $G_{001}$. With ${\cal I}$, ${\cal F}$, $\hat{\alpha}$, $\hat{\beta}$, $\hat{\gamma}$, $\hat{\bullet}$, etc.,  corresponding to $ I$, $ F$, $\alpha$, $\beta$, $\gamma$, $\bullet$, etc., but for overlaps, Rampersad's formulation of Fife's theorem has the following (nonrecursive) form:
\begin{theorem}
Let ${\boldsymbol x}\in\{0, 1\}^\omega$.
\begin{enumerate}
\item If ${\boldsymbol x}$ begins with $01$, then ${\boldsymbol x}$ is overlap-free if and only if ${\boldsymbol x}= 01\hat{\bullet} {\boldsymbol f}$ for some
${\boldsymbol f}\in {\cal F}$.
\item If ${\boldsymbol x}$ begins with $001$, then ${\boldsymbol x}$ is overlap-free if and only if ${\boldsymbol x}= 01\hat{\bullet} {\boldsymbol f}$ for some
$\beta{\boldsymbol f}\in {\cal F}$.
\end{enumerate}
\end{theorem}

\begin{remark} In the second part of this theorem the condition can be rewritten as saying that ${\boldsymbol x}\in 001 \{ 0,1\}^\omega$ is not overlap-free, if and only if $\hat{\beta}{\boldsymbol f}$ has a factor in ${\cal I}$, where ${\boldsymbol f}$ describes the canonical decomposition of 
${\boldsymbol x}$ . In particular, if ${\boldsymbol f}$ has a factor in ${\cal I}$, then ${\boldsymbol x}$
 is not overlap-free. No result analogous to this seems possible for good words; we shall see that there are words ${\boldsymbol x}\in G_{001}$ with description ${\boldsymbol x}=001\bullet{\boldsymbol f}$ such that ${\boldsymbol f}$ has a factor $\beta\alpha\beta\beta\in I$. On the other hand, $\alpha\alpha\alpha\gamma\not\in I$, but cannot be a factor of an infinite word ${\boldsymbol f}$ such that $001\bullet{\boldsymbol f}\in G$.
\end{remark}

Let ${\boldsymbol f} \in B^\omega$
such that $001 \bullet {\boldsymbol f} = {\boldsymbol x}$. Let $w\in B^k$. Then 

\begin{equation}
001\bullet w{\boldsymbol f} = (001\bullet w)\delta^k(01)^{-1}\delta^k({\boldsymbol x}).\end{equation}

Let $F_{001}$ be the set of infinite words walkable on the automaton ${A_{001}}$ of Figure~\ref{automaton2}. 
\begin{theorem}\label{fife001}
Let ${\boldsymbol x}\in\{0, 1\}^\omega$.
If ${\boldsymbol x}$ begins with $001$, then ${\boldsymbol x}$ is good if and only if ${\boldsymbol x}= 001\bullet {\boldsymbol f}$ for some
${\boldsymbol f}\in F_{001}$.
\end{theorem}
Let
$W_{001} = \{{\boldsymbol f}\in B^\omega
: 001\bullet{\boldsymbol f}\in G\}$.
We prove that $W_{001} = F_{001}$.

The identities in the following lemma correspond to the states of ${A_{001}}$, except for state $\beta\gamma\alpha$, which is labeled for its shortest path from the state $a$. The non-accepting sink (d) is omitted from the figure. Proving the identities thus proves 
Theorem~\ref{fife001}. One notes that $\beta\alpha\beta\beta\in I\cap F_{001}$. However, $\alpha\alpha\alpha\gamma$ is a prefix of words in $F$, but cannot be a factor of a word ${\boldsymbol f}\in F_{001}$.

\begin{lemma}The following identities hold:
\begin{enumerate}\item[(a)]$(\beta\alpha)^{-1}W_{001}=W_{001} = \alpha^{-1}W_{001}$;
\item[(b)]$(\beta\gamma\alpha\alpha)^{-1}W_{001}=(\beta\gamma\beta)^{-1}W_{001}=(\beta\beta)^{-1}W_{001}=\beta^{-1}W_{001}$;
\item[(c)]$(\beta\gamma\alpha\beta)^{-1}W_{001}=(\beta\gamma\gamma)^{-1}W_{001}=(\beta\gamma)^{-1}W_{001}$;
\item[(d)]$(\beta\gamma\alpha\gamma)^{-1}W_{001}=\gamma^{-1}=\emptyset$.
\end{enumerate}
\end{lemma}
\begin{figure}
\begin{center} \begin{tikzpicture}[shorten &gt;=1pt,node distance=100pt,auto]
  \tikzstyle{every state}=[fill={rgb:black,1;white,10}]

  \node[state,initial]   (a)                      {$a$};
  \node[state] (b) [right of=a]  {$b$};
  \node[state] (c) [above right of=b] {$c$};
  \node[state]           (d) [below right of=b]     {$\beta\gamma\alpha$};

  \path[&lt;-,arrows = {-Latex[width=7pt, length=7pt]},every loop/.style={arrows = {-Latex[width=7pt, length=7pt]}}]
  (a)   edge [loop above]    node {$\alpha$} (a)
     edge     [bend right] node {$\beta$} (b)

  (b) edge  [loop below] node {$\beta$} (b)
edge  [bend right] node {$\alpha$} (a)       
edge  [bend right=5] node {$\gamma$} (c)
  (c) edge   node {$\alpha$} (d)
       edge [bend right=45]  node {$\beta$} (b)
       edge [loop above]    node {$\gamma$} (c)
  (d) edge [bend left=5]  node {$\alpha$} (b)
       edge  [bend right] node {$\beta$} (c)
 ;
\end{tikzpicture}
\caption{`Fife' automaton ${A_{001}}$ for $G_{001}$.}
\label{automaton2}
\end{center}
\end{figure}
\begin{proof}
Suppose ${\boldsymbol f}\in B^*$. Let $001\bullet{\boldsymbol f} = {\boldsymbol x}$. Thus $001$ is a prefix of ${\boldsymbol x}$.
\begin{enumerate}
\item[(a)] We have \begin{align*}
\alpha{\boldsymbol f}\in W_{001}&amp;\iff 001\bullet\alpha{\boldsymbol f}\in G\\
&amp;\iff(001\bullet\alpha)\delta(01)^{-1}\delta({\boldsymbol x})\in G\\
&amp;\iff 0~\stkout{0100(0100)}^{-1}\delta( {\boldsymbol x})\in G\\
&amp;\iff 1{\boldsymbol x}\in G\text{ or }{\boldsymbol x}\in G_{001}\\
&amp;\iff{\boldsymbol x}\in G\\
&amp;\iff {\boldsymbol f}\in W_{001}.
\end{align*}

We also find that \begin{align*}
\beta\alpha{\boldsymbol f}\in W_{001}&amp;\iff 001\bullet\beta\alpha{\boldsymbol f}\in G\\
&amp;\iff (001\bullet\beta\alpha)\delta^2(01)^{-1}\delta^2({\boldsymbol x})\in G\\
&amp;\iff 001~\stkout{01000101(01000101)}^{-1}\delta^2({\boldsymbol x})\in G\\
&amp;\iff 0\delta(0\delta({\boldsymbol x}))\in G\\
&amp;\iff 10\delta({\boldsymbol x})\in G\text{ or }0\delta({\boldsymbol x})\in G_{001}\\
&amp;\iff 0\delta({\boldsymbol x})\in G\\
&amp;\iff 1{\boldsymbol x}\in G\text{ or }{\boldsymbol x}\in G_{001}\\
&amp;\iff {\boldsymbol x}\in G\\
&amp;\iff {\boldsymbol f}\in W_{001},
\end{align*}
so that $(\beta\alpha)^{-1}W_{001}=\alpha^{-1}W_{001}=W_{001}$.

\item[(b)] Here we have \begin{align*}
\beta{\boldsymbol f}\in W_{001}&amp;\iff 001\bullet\beta{\boldsymbol f}\in G\\
&amp;\iff(001\bullet\beta)\delta(01)^{-1}\delta({\boldsymbol x})\in G\\
&amp;\iff 001~\stkout{0100(0100)}^{-1}\delta({\boldsymbol x})\in G\\
&amp;\iff 0\delta(0{\boldsymbol x})\in G\\
&amp;\iff 10{\boldsymbol x}\in G\text{ or }0{\boldsymbol x}\in G_{001}\\
&amp;\iff 10{\boldsymbol x}\in G.
\end{align*}

In the same way we get \begin{align*}
\beta\beta{\boldsymbol f}\in W_{001}&amp;\iff 001\bullet\beta\beta{\boldsymbol f}\in G\\
&amp;\iff(01\bullet\beta\beta)\delta^2(01)^{-1}\delta^2({\boldsymbol x})\in G\\
&amp;\iff  010100~\stkout{01000101(01000101)}^{-1}\delta^2({\boldsymbol x})\in G\\
&amp;\iff\delta(0\delta(0{\boldsymbol x}))\in G\\
&amp;\iff 0\delta(0{\boldsymbol x})\in G\\
&amp;\iff 10{\boldsymbol x}\in G\text{ or }0{\boldsymbol x}\in G_{001}\\
&amp;\iff 10{\boldsymbol x}\in G.
\end{align*}

Finally we find that \begin{align*}
\beta\gamma\alpha\alpha{\boldsymbol f}\in W_{001}
&amp;\iff 001\bullet\beta\gamma\alpha\alpha{\boldsymbol f}\in G\\
&amp;\iff(01\bullet\beta\gamma\alpha\alpha)\delta^4(01)^{-1}\delta^4({\boldsymbol x})\in G\\
&amp;\iff 001 0100 0100 \delta^4({\boldsymbol x})\in G\\
&amp;\iff 0\delta(0\delta^2(1\delta({\boldsymbol x})))\in G\\
&amp;\iff 10\delta^2(1\delta({\boldsymbol x}))\in G\text{ or }0\delta^2(1\delta({\boldsymbol x}))\in G_{001}\\
&amp;\iff 0\delta^2(1\delta({\boldsymbol x}))\in G\\
&amp;\iff 1\delta(1\delta({\boldsymbol x}))\in G\text{ or }\delta(1\delta({\boldsymbol x}))\in G_{001}\\
&amp;\iff 1\delta(1\delta({\boldsymbol x}))\in G\\
&amp;\iff 01\delta({\boldsymbol x})\in G\\
&amp;\iff \delta(0{\boldsymbol x})\in G\\
&amp;\iff 0{\boldsymbol x}\in G\\
&amp;\iff 10{\boldsymbol x}\in G.
\end{align*}
Thus $(\beta\gamma\alpha\alpha)^{-1}W_{001}=(\beta\gamma\beta)^{-1}W_{001}=(\beta\beta)^{-1}W_{001}=(\beta\alpha)^{-1}W_{001}=\beta^{-1}W_{001}$.
We have $0{\boldsymbol x}\in G \iff 10{\boldsymbol x}\in G$ by the same argument as at the end of case (c) of Lemma~\ref{identities}.


\item[(c)] Here we have
\begin{align*}
\beta\gamma{\boldsymbol f}\in W_{001}&amp;\iff 001\bullet\beta\gamma{\boldsymbol f}\in G\\
&amp;\iff(001\bullet\beta\gamma)\delta^2(01)^{-1}\delta^2({\boldsymbol x})\in G\\
&amp;\iff 001 01000100 ~\stkout{01000101(01000101)}^{-1}\delta^2({\boldsymbol x})\in G\\
&amp;\iff 0\delta(0\delta(00{\boldsymbol x}))\in G\\
&amp;\iff 10\delta(00{\boldsymbol x})\in G\text{ or }0\delta(00{\boldsymbol x})\in G_{001}\\
&amp;\iff 0\delta(00{\boldsymbol x})\in G\\
&amp;\iff 100{\boldsymbol x}\in G\text{ or }00{\boldsymbol x}\in G_{001}\\
&amp;\iff 100{\boldsymbol x}\in G.
\end{align*}

We also have that \begin{align*}
\beta\gamma\gamma{\boldsymbol f}\in W_{001}
&amp;\iff 001\bullet\beta\gamma\gamma{\boldsymbol f}\in G\\
&amp;\iff (001\bullet\beta\gamma\gamma)\delta^3(01)^{-1}\delta^3({\boldsymbol x})\in G\\
&amp;\iff 001 01000100 01000101 01000101\delta^3({\boldsymbol x})\in G\\
&amp;\iff 0\delta(0\delta^2(100{\boldsymbol x}))\in G\\
&amp;\iff 0\delta^2(100{\boldsymbol x})\in G\text{ or }\delta^2(100{\boldsymbol x})\in G_{001}\\
&amp;\iff 0\delta^2(100{\boldsymbol x})\in G\\
&amp;\iff 1\delta(100{\boldsymbol x})\in G\text{ or }\delta(100{\boldsymbol x})\in G_{001}\\
&amp;\iff 1\delta(100{\boldsymbol x})\in G\\
&amp;\iff 0100{\boldsymbol x}\in G\\
&amp;\iff 100{\boldsymbol x}\in G.
\end{align*}

Finally we compute that \begin{align*}\beta\gamma\alpha\beta{\boldsymbol f}\in W_{001}&amp;\iff 001\bullet\beta\gamma\alpha\beta{\boldsymbol f}\in G\\
&amp;\iff(001\bullet\beta\gamma\alpha\beta)\delta^4(01)^{-1}\delta^4({\boldsymbol x})\in G\\
&amp;\iff 001 01000100 0100010101000100 \delta^4({\boldsymbol x})\in G\\
&amp;\iff 0\delta(0\delta^2(1\delta(0{\boldsymbol x})))\in G\\
&amp;\iff 10\delta^2(1\delta(0{\boldsymbol x}))\in G\text{ or }0\delta^2(1\delta(0{\boldsymbol x}))\in G_{001}\\
&amp;\iff 0\delta^2(1\delta(0{\boldsymbol x}))\in G\\
&amp;\iff 1\delta(1\delta(0{\boldsymbol x}))\in G\text{ or }\delta(1\delta(0{\boldsymbol x}))\in G_{001}\\
&amp;\iff 1\delta(1\delta(0{\boldsymbol x}))\in G\\
&amp;\iff 01\delta(0{\boldsymbol x})\in G\\
&amp;\iff \delta(00{\boldsymbol x})\in G\\
&amp;\iff 00{\boldsymbol x}\in G\\
&amp;\iff 100{\boldsymbol x}\in G.
\end{align*}

\item[(d)] In this instance we see that 

\begin{align*}\gamma{\boldsymbol f}\in W_{001}&amp;\iff 001\bullet\gamma{\boldsymbol f}\in G\\
&amp;\iff(001\bullet\gamma)\delta(01)^{-1}\delta({\boldsymbol x})\in G\\
&amp;\iff 00101~\stkout{0100(0100)}^{-1}\delta({\boldsymbol x})\in G\\
&amp;\iff 0\delta(00{\boldsymbol x}))\in G.
\end{align*} But $00{\boldsymbol x}$ has prefix $0000$. Thus $\gamma^{-1}W_{001}=\emptyset$.

In the same way we find that \begin{align*}&amp;\beta\gamma\alpha\gamma{\boldsymbol f}\in W_{001}\\
\iff &amp;001\bullet\beta\gamma\alpha\gamma{\boldsymbol f}\in G\\
\iff &amp;(001\bullet\beta\gamma\alpha\gamma)\delta^4(01)^{-1}\delta^4({\boldsymbol x})\in G\\
\iff &amp; 001 0100 0100 0100010101000100 0100010101000100 \delta^4({\boldsymbol x})\in G\\
\iff &amp; 0 \delta(0\delta(^2(1\delta(00{\boldsymbol x})))\in G.
\end{align*}
We see that  $001\bullet\beta\gamma\alpha\gamma{\boldsymbol f} $ contains the prefix $0000$ of $00{\boldsymbol x}$, so that $(\beta\gamma\alpha\gamma)^{-1}W_{001}=\emptyset$.
\end{enumerate}
\end{proof}


\section{Lexicographically extremal good words}

If $u$ is a word of positive length we let $u^{-}$ denote the word obtained from $u$ by deleting its last letter. The lexicographic order on finite binary words is given recursively by
\begin{displaymath}
u&lt; v \iff \begin{cases}
     v\ne\epsilon, &amp; \text{if $u=\epsilon$;}\\
     (u^-&lt;v^-)\text{ or }((u=u^-0)\text{ and }(v=u^-1)), &amp; \text{otherwise.}
\end{cases}
\end{displaymath}

This extends to an ordering of one-sided infinite binary words; for infinite binary words ${\boldsymbol u}$ and ${\boldsymbol v}$, we say that ${\boldsymbol u}&lt;{\boldsymbol v}$ exactly when there is a prefix $u$ of ${\boldsymbol u}$
 and a prefix $v$ of ${\boldsymbol v}$ with $|u|=|v|$ and $u&lt;v$.

The morphism $\delta$ is order-reversing on infinite words: Let ${\boldsymbol u}$ and ${\boldsymbol v}$ be infinite binary words such that ${\boldsymbol u}&lt;{\boldsymbol v}$. Write ${\boldsymbol u}=u'0{\boldsymbol u}^{\prime}$, ${\boldsymbol v}=u'1{\boldsymbol v}^{\prime}$ where $u'$ is the longest common prefix of ${\boldsymbol u}$ and ${\boldsymbol v}$. Then $\delta(u')01$ is a prefix of $\delta({\boldsymbol u})$, while $\delta(u')00$ is a prefix of $\delta({\boldsymbol v})$, so that $\delta({\boldsymbol u})&gt;\delta({\boldsymbol v})$. 


For each non-negative integer $n$, let $\ell_n$ (resp., $m_n$) be the lexicographically least (resp., greatest) word of length $n$ such that $\ell_n$ (resp., $m_n$) is the prefix of a one-sided infinite good word. 

\begin{lemma} Let $n$ be a non-negative integer. Word $\ell_n$ is a prefix of $\ell_{n+1}$. Word $m_n$ is a prefix of $m_{n+1}$. 
\end{lemma}
\begin{proof} We prove the result for the $\ell_n$; the proof for the $m_n$ is similar. Let $\ell_n{\bf r}$ be a one-sided infinite good word. Let $p$ be the length $n+1$ prefix of
$\ell_n{\bf r}$, and let $q$ be the length $n$ prefix of
$\ell_{n+1}$. We need to show that $q=\ell_n$. Both $p$ and $q$ are prefixes of one-sided infinite good words. By definition we have $\ell_{n+1}\le p$ and $\ell_n\le q$. If $\ell_n&lt;q$, then $p^-=\ell_n&lt;q=\ell_{n+1}^-$, so that $p&lt;\ell_{n+1}$. This is a contradiction. Therefore $\ell_n= q$, as desired.
\end{proof}

Let ${\bf {\boldsymbol\ell}}=\lim_{n\rightarrow\infty}\ell_n$, ${\bf m}=\lim_{n\rightarrow\infty}m_n$.

\begin{lemma} Word ${\bf {\boldsymbol\ell}}$ is the lexicographically least one-sided infinite good word. Word ${\bf m}$ is the lexicographically greatest one-sided infinite good word. 
\end{lemma}
\begin{proof} We show that ${\bf {\boldsymbol\ell}}$ is lexicographically least. The proof that ${\bf m}$ is lexicographically greatest is similar. Let ${\bf w}$ be a one-sided infinite good word. For each $n$ let $w_n$ be the length $n$ prefix of ${\bf w}$, so that ${\bf w}=\lim_{n\rightarrow\infty}w_n$. 

If for some $n$ we have $w_n&gt;\ell_n$, then ${\bf w}&gt;{\bf {\boldsymbol\ell}}$. 

Otherwise $w_n\le \ell_n$ for all $n$. By the definition of the $\ell_n$ we have  $w_n\ge \ell_n$, so that $w_n= \ell_n$ for all $n$. Thus ${\bf w}=\lim_{n\rightarrow\infty}w_n=\lim_{n\rightarrow\infty}\ell_n={\bf {\boldsymbol\ell}}$. 

In all cases we find ${\bf w}\ge{\bf {\boldsymbol\ell}}$.
\end{proof}

\begin{lemma}\label{least} We have ${\boldsymbol\ell}=\delta({\bf m})$. 
\end{lemma}
\begin{proof} Word $0001$ is the least good word of length 4. Also,  $0001$ is a factor of ${\boldsymbol d}$, so there are one-sided infinite good words (which are suffixes of ${\boldsymbol d}$) with prefix $0001$. Therefore, $\ell_4=0001$.
Since $0001$ is a prefix of ${\boldsymbol\ell}$, and ${\boldsymbol\ell}$ is good, we can write ${\boldsymbol\ell}=\delta({\bf m'})$ for some ${\bf m'}$ by Theorem~\ref{main.theorem}. Since ${\boldsymbol\ell}$ is good, ${\bf m'}$ is good by Lemma~\ref{delta.inverse.good}. It follows that ${\bf m'}\le {\bf m}$. However if ${\bf m'}&lt; {\bf m}$ then $\delta({\bf m})&lt;\delta({\bf m'})={\boldsymbol\ell}$ since $\delta$ is order-reversing. This is impossible, since ${\boldsymbol\ell}$ is least. Therefore ${\bf m'}= {\bf m}$, and ${\boldsymbol\ell}=\delta({\bf m})$.
\end{proof}



\begin{lemma}\label{greatest} We have $0{\bf m}=\delta({\boldsymbol\ell})$.
\end{lemma}
\begin{proof} Since $1$ is the greatest good word of length $1$, and ${\boldsymbol d}$ has suffixes that begin with $1$, we have $m_1=1$. By Lemma~\ref{slide}, $0{\bf m}$ is good. Since $01$ is a prefix of $0{\bf m}$, by Theorem~\ref{main.theorem} we can write $0{\bf m}=\delta({\boldsymbol \ell'})$ for some ${\boldsymbol \ell'}$. Since $0{\bf m}$ is good, ${\boldsymbol \ell'}$ is good, so that ${\boldsymbol \ell'}\ge{\boldsymbol \ell}$. However, $\delta$ is order-reversing, so that if 
${\boldsymbol \ell'}&gt;{\boldsymbol \ell}$, then $\delta({\boldsymbol \ell})&gt;\delta({\boldsymbol \ell'})={\boldsymbol m}$, contradicting the maximality of ${\boldsymbol m}$. Thus ${\boldsymbol \ell'}={\boldsymbol \ell}$ and $0{\bf m}=\delta({\boldsymbol \ell})$.
\end{proof}

\begin{theorem} Word ${\boldsymbol m}$ is the fixed point
\begin{equation}{\boldsymbol m}=h_1({\boldsymbol m}),\end{equation}
where $h_1=[1000,1010]$.
Word ${\boldsymbol \ell}$ is the fixed point 
\begin{equation}{\boldsymbol \ell}=h_2({\boldsymbol \ell}),\end{equation}
where $h_2=[0001,0101]$.
\end{theorem}
\begin{proof}
From Lemma~\ref{least} and Lemma~\ref{greatest} we 
find ${\boldsymbol m}=0^{-1}\delta^2({\boldsymbol m})$, so that for each $n$ we have
$m_{4n-2}=0^{-1}\delta^2(m_n)$. 
However, $\delta^{2}(a)=0h_1(a)0^{-1}$ for $a\in\{0,1\}$, so that $\delta^2(w)=0h_1(w)0^{-1}$ for $w\in\{0,1\}^*$. 
Thus $m_{4n-2}=h_1(m_n)0^{-1}$.
Then \begin{align*}
{\boldsymbol m}&amp;= \lim_{n\rightarrow\infty} m_n\\
&amp;= \lim_{n\rightarrow\infty} m_{4n-2}\\
&amp;= \lim_{n\rightarrow\infty} h_1(m_n)0^{-1}\\
&amp;= \lim_{n\rightarrow\infty} h_1(m_n)\\
&amp;= h_1(\lim_{n\rightarrow\infty} m_n)\\
&amp;= h_1({\boldsymbol m}).
\end{align*} 
The proof for ${\boldsymbol \ell}$ is similar, using the fact that $h_2=(01)^{-1}\delta^201$.
\end{proof}
\begin{corollary}Every finite factor of ${\boldsymbol \ell}$ or ${\boldsymbol m}$ is a factor of ${\boldsymbol d}$, and vice versa. However, words ${\boldsymbol \ell}$, ${\boldsymbol m}$, and ${\boldsymbol d}$ have no common suffix.
\end{corollary}
\begin{proof} Because $\delta^2$, $h_1$, and $h_2$ are conjugates of each other, their fixed points have the same factors. For example, let $u$ be a factor of ${\boldsymbol d}=\lim_{n\rightarrow\infty}\delta^{n}(0)$. Then for some $n$, $u$ is a factor of $\delta^{2n}(0)=0h_1^{2n}(0)0^{-1}$, which is a factor of $h_1^{2n}(1010)=
h_1^{2n+1}(1)$, which is a prefix of ${\boldsymbol m}=\lim_{n\rightarrow\infty}h_1^{n}(1)$. Thus $u$ is a factor of ${\boldsymbol m}$.

Now suppose ${\boldsymbol d}$ and ${\boldsymbol \ell}$ have a common suffix ${\boldsymbol s}$. (The proofs for the other pairs of fixed points are similar.) Write 
${\boldsymbol d}=d_i{\boldsymbol s}$ and ${\boldsymbol \ell}=\ell_j{\boldsymbol s}$ for some $i$ and $j$, where $d_n$ is the prefix of ${\boldsymbol d}$ of length $n$. Then 
\begin{align*}
d_i{\boldsymbol s}&amp;= {\boldsymbol d}\\
&amp;= \delta^2({\boldsymbol d})\\
&amp;= \delta^2(d_i)\delta^2({\boldsymbol s}),
\end{align*} 
so that  ${\boldsymbol s}=s_{3i}\delta^2({\boldsymbol s})$ where is $s_n$ is the prefix of ${\boldsymbol s}$ of length $n$. Similarly,
\begin{align*}
\ell_j{\boldsymbol s}&amp;= {\boldsymbol \ell}\\
&amp;= h_2({\boldsymbol \ell})\\
&amp;= h_2(\ell_j)h_2({\boldsymbol s}),
\end{align*} 
so that  ${\boldsymbol s}=s_{3j}h_2({\boldsymbol s})$. Thus
\begin{align*}
s_{3j}h_2({\boldsymbol s})&amp;= {\boldsymbol s}\\
&amp;= s_{3i}\delta^2({\boldsymbol s})\\
&amp;= s_{3i}01h_2({\boldsymbol s})\\
&amp;= s_{3i+2}h_2({\boldsymbol s}).
\end{align*}
It follows that $h_2({\boldsymbol s})$ has period $|3(i-j)+2|$. However, $h_2({\boldsymbol s})$ is good and does not contain fourth powers. Therefore, $3(i-j)+2=0$. This is impossible since $i$ and $j$ are integers.
\end{proof}
\section{Binary patterns in \texorpdfstring{${\boldsymbol d}$}{\bf d}}

Every word encounters its factors as patterns. If a word encounters some binary pattern $p$, it necessarily encounters the complement $\overline{p}$. Shur \cite{shur96} has shown that, up to complementation, the only binary patterns encountered by ${\bf t}$ are its factors and $00100$.  The situation with ${\boldsymbol d}$ is more complicated. 

\begin{lemma} Any factor $0u$ of ${\boldsymbol d}$ can be written as $h_1(p)$ for some word $p$ where $h_1=[0,01]$. Any factor $u0$ of ${\boldsymbol d}$ can be written as $h_2(p)$ for some word $p$ where $h_2=[0,10]$. 
Word ${\boldsymbol d}$ thus has an inverse image under each of $h_1$ and $h_2$.
\end{lemma}
\begin{proof} Every occurrence of $1$ in ${\boldsymbol d}$ is preceded and followed by $0$.
\end{proof}

\begin{corollary} Let $0u$ be a factor of ${\boldsymbol d}$ such that $|0u|\ge 13$. Then $0u$ can be written as $h_1(p)$ where $p$ is neither a factor of ${\boldsymbol d}$ nor the complement of a factor of ${\boldsymbol d}$. Thus ${\boldsymbol d}$ encounters infinitely many patterns $p$ such that neither of $p$ and $\overline{p}$ is a factor of ${\boldsymbol d}$. 
\end{corollary}
\begin{proof}
The longest factor of ${\boldsymbol d}$ not containing $010001$ is $100010101000$, which has length 12. Therefore, $0u=h_1(p)$ has the factor $010001=h_1(1001)$, and $p$ has the factor $1001$. Neither of $1001$ and $0110$ is a factor of ${\boldsymbol d}$ so neither $p$ nor $\overline{p}$ is a factor of ${\bf d}$.
\end{proof}

For every particular pattern $p$, the automatic proving system Walnut \cite{mousavi16} can in theory, given enough computing power and time, determine whether ${\boldsymbol d}$ encounters $p$. However, in the next theorem, we effectively characterize all binary patterns $p$ encountered by ${\boldsymbol d}$. The remainder of this section is devoted to its proof.
\begin{theorem} Word $p$ is a binary pattern encountered by ${\boldsymbol d}$ if and only if one of the following holds:
\begin{enumerate}
\item One of $p$ and $\overline{p}$ is a factor of ${\boldsymbol d}$, $h^{-1}_1({\boldsymbol d})$, or $h^{-1}_2({\boldsymbol d})$.
\item One of $p$ and $\overline{p}$ is among
 
$0010100$,
$01001001000$,
$00100100100$,
$001001001000$,
$00010010010$,

$000100100100$,
$0010001000100$,
$00100010001000$, 
$00010001000100$,
 and
$000100010001000$.
\end{enumerate}
The two possibilities are distinct.
\end{theorem}


The following analog of Lemma~\ref{uvu} will be useful for analyzing the patterns appearing in ${\bf w}$:
\begin{lemma}\label{uvu4} Let $u,v$ be binary words such that  $uvu$ is a factor of ${\boldsymbol d}$, $|u|\ge 3$, and either
\begin{itemize}
\item we have $|u|_{00}\ge 1$, or
\item we have $|u|_{10101}\ge 1$.
\end{itemize}
Then $|uv|\equiv \modd{0} {4}$.
\end{lemma}
\begin{proof} Suppose that $00$ is a factor of $u$, and $|u|\ge 3$. Then word $u$ contains one of the factors $000$, $001$, and $100$. These can only arise in ${\boldsymbol d}$ as suffixes of some prefix of ${\boldsymbol d}$ of the form $\delta^2(p0)0$, $\delta^2(p0)01$, and $\delta^2(p0)$, respectively. The index of every occurrence of factor $000$, $001$, or $100$, and thus the index of every occurrence of $u$, in ${\boldsymbol d}$ is therefore fixed modulo 4, and the result follows.

Suppose $|u|_{10101}\ge 1$. The factor $10101$ only occurs in ${\boldsymbol d}$ as a suffix of some prefix of ${\boldsymbol d}$ of the form $\delta^2(p10)(00)^{-1}$ and the index of every occurrence of $u$ in ${\boldsymbol d}$ is again fixed, modulo 4.
\end{proof}

\begin{theorem}\label{patterns} Suppose that ${\boldsymbol d}$ encounters binary pattern $p$. Then one of $p$ and $\overline{p}$ either
\begin{enumerate}
\item  is a factor of ${\boldsymbol d}$, $h_1^{-1}({\boldsymbol d})$, or of $h_2^{-1}({\boldsymbol d})$, or
\item has the property that all its factors of the form $10^k1$ have the same length.
\end{enumerate}
\end{theorem}
\begin{proof}
Without loss of generality, replacing $p$ by $\overline{p}$ if necessary, assume that $0$ is the first letter of $p$. Assume that neither $p$ nor $\overline{p}$ is a factor of ${\boldsymbol d}$, $h^{-1}_1({\boldsymbol d})$, or $h^{-1}_2({\boldsymbol d})$. Since $000$ is a factor of ${\boldsymbol d}$ and ${\boldsymbol d}$ does not encounter $0000$,  we must have $|p|_1&gt;0$.
Let $g(p)$ be a factor of $\delta^n(0)$ where $g=[X,Y]$ is a non-erasing morphism, and $n$ is as small as possible. By Lemma~\ref{even.lengths}, $|X|$ and $|Y|$ are not both even. We consider cases based on $|X|_1$ and $|Y|_1$.

\begin{enumerate}
\setlength{\itemindent}{0.25in}
\item[{\bf Case 1}] We have $|X|_1$, $|Y|_1&gt;0$:
If $XX$ (resp., $YY$, $XYX$, $YXY$) is a factor of $\delta^n(0)$, then by Lemma~\ref{uvu}, $|X|$ (resp., $|Y|$, $|XY|$, $|YXY|$) is even. 
It follows that not both $XX$ and $YY$ are factors of $g(p)$. Also, not both $XX$ and $XYX$ are factors of $g(p)$, or else $|X|$ and $|XY|$ are even, forcing $|Y|$ to be even. Similarly, not both $YY$ and $YXY$ are factors of $g(p)$.

If neither of $XX$ and $YY$ is a factor of $g(p)$, then $g(p)$ is an alternating string of $X$'s and $Y$'s, and thus a prefix of $XYXYXYX$. (Since ${\boldsymbol d}$ is good, the fourth power $(XY)^4$ is not a factor of ${\boldsymbol d}$.) But then $p$ is a prefix of $0101010$, which is a factor of ${\boldsymbol d}$.  This is a contradiction.

Suppose then, that $XX$ is a factor of $g(p)$. Then neither of $YY$ and $XYX$ is a factor of $g(p)$. If $|p|_1\ge 2$, then $g(p)$ would have a prefix of the form $X^rYX^sY$, $r,s\ge 1$. This contains a factor $XYX$, which is impossible. It follows that $|p|_1\le 1$. Because ${\boldsymbol d}$ is good, $g(p)$ cannot have a factor $XXXX$, and we conclude that $p$ is a factor of $0001000$. But $0001000$ is seen to be a factor of ${\boldsymbol d}$. 

Finally, suppose that $YY$ is a factor of $g(p)$. Then $XX$ and $YXY$ are not factors of $g(p)$. Therefore, $p$ begins with $0$, and has a factor $11$, but not  $00$, $101$, or $1111$. (A factor $1111$ in $p$ would give a fourth power in the good word ${\boldsymbol d}$.) It follows that $p$ is one of $011$, $0110$, $0111$, and $01110$. However $h_1(\overline{011})=0100$, $h_1(\overline{0110})=010001$, $\overline{0111}=1000$, and  $\overline{0111}=1000$ are all factors of ${\boldsymbol d}$.

\item[{\bf Case 2}] We have $|X|_1=|Y|_1=0$. This forces $g(p)$ to be a factor of $000$, so that $p$ is a binary word of length 3 or less. Each such word, or its complement, is a factor of ${\boldsymbol d}$. 

\item[{\bf Case 3}] We have $|X|_1&gt;0$ but $|Y|_1=0$. Write $Y=0^n$ where $1\le n\le 3$.
   \begin{enumerate}
   \setlength{\itemindent}{0.5in}
   \item[{\bf Case 3(a)}] 
We have $|X|\ge 3$, and either $|X|_{00}\ge 1$ or
$|X|_{10101}\ge 1$.
If $p$ contains only a single $0$ (its first letter) then, since fourth powers do not appear in ${\boldsymbol d}$, $p$ must be a prefix of $0111$, which is the complement of a factor of ${\boldsymbol d}$. Otherwise, $p$ has a factor of the form $01^k0$ for some $k$, $0\le k\le 3$. 
Thus $XY^kX=X0^{nk}X$ is a factor of ${\boldsymbol d}$. By Lemma~\ref{uvu4} with $u=X$, $v=0^{nk}$, we have
$|X|\equiv -nk$ (mod 4). 

If $n=2$, then since $0^4$ is not a factor of ${\boldsymbol d}$, we have $0\le k\le 1$. Also, $|X|\equiv -nk$ (mod 4), so $|X|$ is even, giving $k\equiv -|X|/2$ (mod  2) and $k$ is determined; each pair of $0$'s in $p$ is separated by the same number of $1$'s. Then $\overline{p}$ has the property that all its factors of the form $10^k1$ have the same length.
If $n=1$ or $n= 3$, then since $0\le k\le 3$, $k$ is determined by the congruence $|X|\equiv -nk$ (mod 4), and again $\overline{p}$ has the property that all its factors of the form $10^k1$ have the same length.

   \item[{\bf Case 3(b)}] Either $|X|&lt; 3$, or $|X|_{00}=|X|_{10101}=0$. If $|X|_{00}=0$, then $X$ does not contain a factor $00$ or $11$, and is, therefore, an alternating string of $0$'s and $1$'s. Thus the given conditions imply that $X=00$, or $X$ is a factor of $01010$.

If $X=00$, then $g(p)$ must be a factor of $000$, which is a factor of ${\boldsymbol d}$.

Suppose then that $X$ is a factor of $01010$.
 If $p$ contained at most a single $0$ (its first letter), then $p$ would be a prefix of $0111$, the complement of a factor of ${\boldsymbol d}$. This is impossible. Therefore, assume that $p$ has a factor of the form $01^k0$. If $|X|\ge 3$, then $X$ is one of $010$, $101$, $0101$, $1010$, or $01010$. One checks that for each of these possibilities for $X$ there is exactly one value of $k$ such that $X0^kX$ is a factor of ${\boldsymbol d}$:
\begin{itemize}
\item If $X$ is $010$ or $01010$, $k=1$.
\item If $X=101$, then a factor $XX$ would imply ${\boldsymbol d}$ has factor $11$; a factor $X0X$ in ${\boldsymbol d}$ would extend on the right to a factor $X0X0=(10)^4$ in ${\boldsymbol d}$; a factor $X00X$ would imply ${\boldsymbol d}$ has factor $1001$; thus $k=3$.
\item If $X$ is $0101$ or $1010$, then $XX$ is a fourth power, while $X0X$ has the factor $1001$; $X000X$ contains $0000$; thus $k=2$.
\end{itemize}
Thus if $|X|\ge 3$ then $\overline{p}$ has the property that all its factors of the form $10^k1$ have the same length.
 We are left with the cases where $|X|\le 2$ and $X\ne 00$, i.e., word $X$ is among $1$, $01$, and $10$.
\begin{itemize}
\setlength{\itemindent}{.5in}
\item[$X=1$.]  Since ${\boldsymbol d}$ has a factor $XY^kX$, we cannot have $Y=00$ or else ${\boldsymbol d}$ contains $0000$ or $1001$. Thus $Y=0$. Then $g=[1,0]$, and $p$ is the complement of a factor of ${\boldsymbol d}$.  
\item[$X=01$.] Since $|X|$ is even, we must have $|Y|$ odd, so that $n=1$ or $n=3$. If $n=3$, then $YX=0^41$ and $YY=0^6$ are not factors of ${\boldsymbol d}$, forcing $|p|_1=1$, and $p$ is a factor of $00010000$, which is a factor of ${\boldsymbol d}$. Suppose then that $n=1$. Now, however $g=[01,0]$, and $h_1(\overline{p})=g(p)$ is a factor of ${\boldsymbol d}$, so  that $\overline{p}$ is a factor of $h_1^{-1}({\boldsymbol d})$.
\item[$X=10$.] Again $|X|$ is even, so we find $n=3$ or $n=1$. In the first case, $XY$ contains $0000$, which is impossible. Thus $p$ is a factor of $000$, a factor of ${\boldsymbol d}$. In the second case, $g=[10,0]$, and $\overline{p}$ is a factor of $h_2^{-1}({\boldsymbol d})$.
\end{itemize}
\end{enumerate}
\item[{\bf Case 4}] We have $|X|_1=0$ but $|Y|_1&gt;0$. Write $X=0^n$ where $1\le n\le 3$.
\begin{enumerate}
\setlength{\itemindent}{0.5in}
   \item[{\bf Case 4(a)}] 
We have $|Y|\ge 3$, and either $|Y|_{00}\ge 1$ or
$|Y|_{10101}\ge 1$.
If $p$ contains at most a single $1$ then, since fourth powers do not appear in ${\boldsymbol d}$, $p$ must be a factor of $0001000$, which is a factor of ${\boldsymbol d}$. Otherwise, $p$ has some factor of the form $10^k1$ for some $k$, $0\le k\le 3$. 
Thus $YX^kY=Y0^{nk}Y$ is a factor of ${\boldsymbol d}$. By Lemma~\ref{uvu4} with $u=Y$, $v=0^{nk}$, we have
$|Y|\equiv -nk$ (mod 4). 

If $n=2$, then since $0^4$ is not a factor of ${\boldsymbol d}$, we have $0\le k\le 1$. Also, $|Y|\equiv -nk$ so $|Y|$ is even, giving $k\equiv -|Y|/2$ (mod  2) and $k$ is determined. Therefore, $p$ has the property that all its factors of the form $10^k1$ have the same length.

If $n=1$ or $n= 3$, then since $0\le k\le 3$, $k$ is determined by the congruence $|Y|\equiv -nk$ (mod 4), and again $p$ has the property that all its factors of the form $10^k1$ have the same length.

\item[{\bf Case 4(b)}] Either $|Y|\le 3$, or $|Y|_{00}=|Y|_{10101}=0$. If $|Y|_{00}=0$, then $Y$ does not contain a factor $00$ or $11$, and is an alternating string of $0$'s and $1$'s. Thus the given conditions imply that $Y=00$, or $Y$ is a factor of $01010$.

If $Y=00$, then $g(p)$ must be a factor of $000$, which is a factor of ${\boldsymbol d}$.

Suppose then that $Y$ is a factor of $01010$.
If $p$ contains at most a single $1$, then $p$ must be a factor of $0001000$, a factor of ${\boldsymbol d}$. Therefore, assume that $p$ has a factor of the form $10^k1$. If $|Y|&gt;2$, an analysis as in Case 3(a),  shows that $p$ has the property that all its factors of the form $10^k1$ have the same length. The cases where $|Y|\le 2$ are impossible, with an analysis analogous to that of Case 3(a).
\end{enumerate}
\end{enumerate}
\end{proof}

\begin{lemma} The set of factors of ${\boldsymbol d}$ is closed under reversal.
\end{lemma}
\begin{proof} To begin, we notice that if $u$ is a binary word, then
\[(\delta(u))^R=0^{-1}\delta(u^R)0.\]
Suppose $v$ is a factor of ${\boldsymbol d}$.  The set of length 2 factors of ${\boldsymbol d}$ is seen to be $\{00, 01, 10\}$, which is closed under reversal. Therefore, if $|v|\le 2$, then $v^R$ is a factor of ${\boldsymbol d}$. Suppose that $|v|&gt;2$, and for every shorter factor $u$ of ${\boldsymbol d}$, the reversal $u^R$ is a factor of ${\boldsymbol d}$. However, $|v|&gt;2$ implies that $v$ is a factor of $\delta(u)$, for some factor $u$ of ${\boldsymbol d}$ which is shorter than $v$. Thus $u$ and $u^R$ are factors of ${\boldsymbol d}$. Then $(\delta(u))^R=0^{-1}\delta(u^R)0$ is also a factor of ${\boldsymbol d}$, so that $v^R$ is also. The result follows by induction.
\end{proof}
\begin{corollary}\label{reverse} If ${\boldsymbol d}$ encounters pattern $p$, then ${\boldsymbol d}$ encounters pattern $p^R$ also.
\end{corollary}


\begin{theorem} The following are equivalent:
\begin{enumerate}
\item Word $p$ is a binary pattern encountered by ${\boldsymbol d}$, but neither $p$ nor $\overline{p}$ is a factor of ${\boldsymbol d}$, $h^{-1}_1({\boldsymbol d})$, or $h^{-1}_2({\boldsymbol d})$.
\item One of $p$ and $\overline{p}$ is among
 
$0010100$,
$01001001000$,
$00100100100$,
$001001001000$,
$00010010010$,\\
$000100100100$,
$0010001000100$,
$00100010001000$, 
$00010001000100$,\\ and
$000100010001000$.
\end{enumerate} 
\end{theorem}
\begin{proof} $(1\Rightarrow 2)$: Suppose that $p$ is a binary pattern encountered by ${\boldsymbol d}$, but neither $p$ nor $\overline{p}$ is a factor of ${\boldsymbol d}$, $h^{-1}_1({\boldsymbol d})$, or $h^{-1}_2({\boldsymbol d})$. By Theorem~\ref{patterns}, replacing $p$ by $\overline{p}$ if necessary, there is a number $k$ such that there are exactly $k$ $0$'s between subsequent $1$'s in $p$. Thus $p=0^r(10^k)^s10^t$ for some $k,r,s,t$. Since ${\boldsymbol d}$ does not contain fourth powers, $k,r,s,t\le 3$. For the same reason, if $s=3$, then $r+s&lt;k$. If $s=0$, then $p$ is a factor of $0001000$, which is a factor of ${\boldsymbol d}$. We, therefore, have $s\ge 1$. We consider
cases based on the value of $k$:

\bigskip

\noindent $k=0$: In this case, to avoid fourth powers, we must also have $s\le 2$, and $p$ is a factor of $00011000$ or $000111000$. We note that  $h_1(\overline{00011000})=01010100010101$ 
is a factor of ${\boldsymbol d}$. Thus $p$ cannot be a factor of $00011000$, which would make $\overline{p}$ a factor of $h_1^{-1}({\boldsymbol d})$. We conclude that $p$ is a factor of $000111000$.
Note that, $h_2(00011100)=h_1(00111000)=00010101000$ is a factor of ${\boldsymbol d}$, so that $p$ cannot be a proper factor of $000111000$. It remains that we must have $p=000111000$. To obtain a contradiction, we show that ${\boldsymbol d}$ does not encounter $p$. 

Suppose $g(p)$ is a factor of ${\boldsymbol d}$, $g=[X,Y]$ a non-erasing morphism. By Lemma~\ref{even.lengths} assume that one of $|X|$ and $|Y|$ is odd. Both $XX$ and $YY$ are factors of $g(p)=XXXYYYXXX$, so by Lemma~\ref{uvu} we must have $|X|_1=0$ or $|Y|_1=0$. 

Suppose $|X|_1=0$. Thus $XXX$ ends in $000$. Since $XXXY$ is a factor of $g(p)$, which is a factor of ${\boldsymbol d}$, the first letter of $Y$ is $1$. Since $XXX$ begins with $000$ and $YXXX$ is a factor of $g(p)$, the last letter of $Y$ is $1$. But then $YY$ contains the factor $11$, so that $11$ is a factor of the good word ${\boldsymbol d}$, which is impossible.

Suppose $|Y|_1=0$. Switching $X$ and $Y$ in the argument of the previous paragraph shows that this is impossible also.

\bigskip

\noindent{$k=1$}: We consider subcases based on whether $s$ is 1, 2, or 3:
\bigskip

$s=1$: If $r+t\ge 5$, then $p$ contains $00010100$ or its reverse. However
${\boldsymbol d}$ is good, and therefore does not encounter $00010100$. By Corollary~\ref{reverse}, ${\boldsymbol d}$ does not encounter the reverse of ${\boldsymbol d}$. We conclude that $r+t\le 4$, so that $p$ is a factor of $0101000$, $0010100$, or $0001010$. However, $0101000$ and $0001010$ are factors of ${\boldsymbol d}$, so $p$ cannot be a factor of one of these. Therefore $p$ must be a factor of $0010100$. Both $010100$ and $010100$ are factors of ${\boldsymbol d}$, so $p$ cannot be a proper factor of $0010100$, forcing $p=0010100$.
\bigskip

$s=2$: In this case $p$ is a factor of $00010101000$, which is a factor of ${\boldsymbol d}$. 
\bigskip

$s=3$: If $r=t=0$, then $p=1010101$ is the complement of a factor of ${\boldsymbol d}$. However, if $r&gt;0$ or $t&gt;0$, then $p$ contains one of the fourth powers $01010101$ and $10101010$, so that ${\boldsymbol d}$ does not encounter $p$, which is a contradiction.
\bigskip

\noindent {$k=2$:} We consider subcases based on whether $s$ is 1, 2, or 3:
\bigskip

$s=1$: If $r+t\le 5$ then $p$ is factor of $000100100$ or of $001001000$. However $h_2(000100100)=00010001000=h_1(001001000)$ is a factor of ${\boldsymbol d}$, so $p$ is a factor of $h_1^{-1}({\boldsymbol d})$ or of $h_2^{-1}({\boldsymbol d})$, a contradiction. If $r=t=3$, then $p=0001001000=h_2(00010100)$, and ${\boldsymbol d}$ encounters $00010100$. Since ${\boldsymbol d}$ is good, this is impossible.
\bigskip

$s=2$: If $r+t\le 3$, then $p$ is a factor of $1001001000$, $0100100100$, $0010010010$, or $0001001001$; however each of \begin{align*}
h_1(1001001000)&amp;=0100010001000,\\
h_2(0100100100)&amp;=0100010001000,\\
h_1(0010010010)&amp;=0001000100010, \mbox{ and}\\ h_2(0001001001)&amp;=0001000100010
\end{align*}
 is a factor of ${\boldsymbol d}$, so that $p$ is a factor of $h_1^{-1}({\boldsymbol d})$ or of 
$h_2^{-1}({\boldsymbol d})$. 

If $r=t=3$, then $p=0001001001000$. To get a contradiction, we show that ${\boldsymbol d}$ does not encounter $p$. Otherwise, suppose without loss of generality that ${\boldsymbol d}$ has a factor $g(p)$ where $g=[X,Y]$ is a non-erasing morphism and  $|X|$, $|Y|$ are not both odd. Word ${\boldsymbol d}$ has the factor $XXXYXXYXXYXXX$. We cannot have $|X|_1&gt;0$, or since $XX$ and $XYX$ are factors of ${\boldsymbol d}$,  Lemma~\ref{uvu} would force both $|X|$ and $|Y|$ to be even. Write $X=0^n$. Since $XX$ is a factor of ${\boldsymbol d}$, we must have $n=1$ and $X=0$. Since $XXXY$ and $YXXX$ are factors of ${\boldsymbol d}$,  the first and last letters of $Y$ are $1$. Then $YXXY$ contains the factor $1001$, which cannot be a factor of ${\boldsymbol d}$. This is a contradiction.

We conclude that $4\le r+t\le 5$, so that $p$ is one of $01001001001000$, $00100100100100$, $00010010010010$, $001001001001000$, and $000100100100100$.
\bigskip

$s=3$: If $r+t\le 1$, then $p$ is a factor of $01001001001$ or $10010010010$. However $h_2(01001001001)=010001000100010$ and $h_1(010001000100010)$ are factors of ${\boldsymbol d}$, so $p$ is a factor of $h_1^{-1}({\boldsymbol d})$ or of $h_2^{-1}({\boldsymbol d})$, which is a contradiction. On the other hand, if $r+t\ge 2$, then one of the fourth powers $(001)^4)$, $(010)^4$ and $(100)^4$ is a factor of $p$, and ${\boldsymbol d}$ contains a fourth power, which is impossible.
\bigskip

\noindent $k=3$:  We consider subcases based on whether $s$ is 1, 2, or 3:
\bigskip

$s=1$: In this case $p$ is a factor of $00010001000$, which is a factor of ${\boldsymbol d}$. 
\bigskip

$s=2$: If $r\le 1$ then $p$ is a factor of $0100010001000$ which is a factor of ${\boldsymbol d}$. This is impossible. Similarly, $t\le 1$ is impossible. Thus $p$ must be one of $0010001000100$, $00010001000100$, $00100010001000$, and $000100010001000$.
\bigskip

$s=3$: If $r,t\le 1$ then $p$ is a factor of $010001000100010$, which is a factor of ${\boldsymbol d}$, a contradiction. Suppose $r\ge 2$ or $t\ge 2$. Then $p$ has $q=001000100010001$ or its reverse as a factor. By Corollary~\ref{reverse}, it suffices to show that ${\boldsymbol d}$ does not encounter $q$.

To get a contradiction, suppose that $g(q)$ is a factor of ${\boldsymbol d}$ for some non-erasing morphism $g=[X,Y]$ where one of $|X|$ and $Y$ is odd. Thus word ${\boldsymbol d}$ has the factor  
$$XXYXXXYXXXYXXXY.$$ 
Since $XX$ and $XYX$ are factors of ${\boldsymbol d}$, we must have $X=0^n$ for some $n$; otherwise, Lemma~\ref{uvu} implies that $|X|$ and $|Y|$ are even, a contradiction. Since $XX$ is a factor of ${\boldsymbol d}$, we have $n=1$ and $X=0$. Since $YXXX=Y000$ is a factor of ${\boldsymbol d}$, the last letter of $Y$ is $1$. Therefore, $Y$ is always followed by $0$ in ${\boldsymbol d}$, so $XXYXXXYXXXYXXXY0$ is a factor of ${\boldsymbol d}$. However $XXYXXXYXXXYXXXY0=(00Y0)^4$, and ${\boldsymbol d}$ contains a fourth power. This is impossible.

\bigskip

  $(1\Leftarrow 2)$: We show that ${\boldsymbol d}$ encounters each of the listed patterns, but none of these patterns or their complements is a factor of ${\boldsymbol d}$, $h^{-1}_1({\boldsymbol d})$, or $h^{-1}_2({\boldsymbol d})$.

First we show that ${\boldsymbol d}$ encounters the listed patterns. Note that each of these patterns is   a factor of 
$0010100$, 
$001001001000$, $000100100100$, or
$000100010001000$. Since $001001001000$ is the reverse of $000100100100$, by Lemma~\ref{reverse} it suffices to show that ${\boldsymbol d}$ encounters 
$0010100$, 
$001001001000$, or
$000100010001000$.
\begin{itemize}
\item $p=0010100$: Word ${\boldsymbol d}$ has the factor \[00010001000=g(0010100),\] where $g=[0,010]$.

\item $p=001001001000$: Word ${\boldsymbol d}$ has the factor \[0001010100010101000010101000=g(001001001000),\] where $g=[0,010101]$.

\item $p=000100010001000$: Word ${\boldsymbol d}$ has the factor \[0001010100010101000010101000=g(000100010001000),\] where $g=[0,10101]$.
\end{itemize}

Next, we show that 
none of these patterns or their complements is a factor of ${\boldsymbol d}$, $h_1^{-1}({\boldsymbol d})$, or $h_2^{-1}({\boldsymbol d})$.
Notice that $h_1(101)=01001$ and $h_2(101)=10010$, and $1001$ is not a factor of ${\boldsymbol d}$, since ${\boldsymbol d}$ is good. The complements of all the listed patterns contain $101$ as a factor, so none of the complements is a factor of $h_1^{-1}({\boldsymbol d})$, or $h_2^{-1}({\boldsymbol d})$. Further, all the complements of the listed factors contain $11$ as a factor, so none of the complements is a factor of ${\boldsymbol d}$.
It therefore suffices to show that none of the listed patterns is a factor of ${\boldsymbol d}$, $h_1^{-1}({\boldsymbol d})$, or $h_2^{-1}({\boldsymbol d})$.

Each of the listed patterns has one of 
$0010100$, 
$01001001000$,
$00100100100$,
$00010010010$,
 and
$0010001000100$ as a factor. 
It, therefore, suffices to show that none of these five patterns is a factor of ${\boldsymbol d}$, $h_1^{-1}({\boldsymbol d})$, or $h_2^{-1}({\boldsymbol d})$. 
\bigskip

\noindent {Case 1: $0010100$.} If this was a factor of ${\boldsymbol d}$, the $1$'s would force it to appear in the context $00010100$, which is impossible since ${\boldsymbol d}$ is good. Since $101$ is a factor of $0010100$, it is not a factor of $h_1^{-1}({\boldsymbol d})$, or $h_2^{-1}({\boldsymbol d})$ either.
\bigskip

\noindent {Case 2: $01001001000$.} This has $1001$ as a factor, and therefore is not a factor of ${\boldsymbol d}$.

Word $00100010001000=h_1(01001001000)$ cannot be a factor of ${\boldsymbol d}$; if it preceded $0$ then $0000$ would be a factor of ${\boldsymbol d}$; if it preceded $10$ then $(0100)^4$ is a factor of ${\boldsymbol d}$, which is impossible.

Word $h_2(01001001000)$ ends in the fourth power $0000$ and cannot be a factor of ${\boldsymbol d}$.
\bigskip

\noindent {Case 3: $00100100100$.} This has $1001$ as a factor, and therefore is not a factor of ${\boldsymbol d}$.

Word $h_1(00100100100)=00010001000100$ cannot be a factor of ${\boldsymbol d}$; if it preceded $1$ then $1001$ would be a factor of ${\boldsymbol d}$; if it preceded $00$ then $0000$ is a factor of ${\boldsymbol d}$; if it preceded $01$ then $(0001)^4$ is a factor of ${\boldsymbol d}$, which is impossible.

Word $00100010001000=h_2(00100100100)$ cannot be a factor of ${\boldsymbol d}$ as argued in Case 2.
\bigskip


\noindent{Case 4: $00010010010$.} This has $1001$ as a factor, and therefore is not a factor of ${\boldsymbol d}$.

Word $h_1(00010010010)$ begins with $0000$ and cannot be a factor of ${\boldsymbol d}$.

Word $00010001000100=h_2(00010010010)$ cannot be a factor of ${\boldsymbol d}$ as argued in Case 3.
\bigskip

\noindent{Case 5: $0010001000100$.} This cannot be a factor of ${\boldsymbol d}$. Recall that ${\boldsymbol d}$ is recurrent and does not contain factors 1001 or 0000. However, a second occurrence of this factor in ${\boldsymbol d}$ would be in the context $0001000100010001=(0001)^4$, which is impossible.

Word $h_1(0010001000100)$ begins $00010000$, containing $0000$, and cannot be a factor of ${\boldsymbol d}$.

Word $h_2(0010001000100)$ ends $00001000$, containing $0000$, and cannot be a factor of ${\boldsymbol d}$.
\end{proof}

\section{Acknowledgment}

The author was supported by the Natural Sciences and Engineering Research
Council of Canada (NSERC), funding reference number 2017-03901.

\begin{thebibliography}{99}

\bibitem{berstel94} J.\ Berstel, A rewriting of Fife's theorem about overlap-free words, in J.\ Karhum\"aki, H.\ Maurer, and G.\ Rozenberg, eds., {\em Results and Trends in Theoretical Computer Science}, Lect. Notes in Comp. Sci., Vol. 812, Springer-Verlag, 1994, pp.\ 19--29. 
\bibitem{allouche98} J.-P.\ Allouche, J.\ Currie, and J.\ Shallit, Extremal infinite overlap-free binary words, {\em Electron.\ J.\ Combin.} {\bf 5} (1998), \#R27.
\bibitem{allouche99} J.-P.\ Allouche and J.\ Shallit, The ubiquitous Prouhet-Thue-Morse sequence, in C.\ Ding, T.\ Helleseth, H.\ Niederreiter, eds., {\em Sequences and their Applications, Proceedings of SETA '98}, Springer-Verlag, 1998,  pp.\ 1--16.
\bibitem{carpi93} A.\ Carpi, Overlap-free words and finite automata, {\em Theoret.\ Comput.\ Sci.}
{\bf 115} (1993), 243--260.
\bibitem{cassaigne93} J.\ Cassaigne, Counting overlap-free binary words, in P.\ Enjalbert, A.\ Finkel, and K. Wagner, eds., {\em STACS 93, Proc. 10th Symp. Theoretical Aspects of Comp.\ Sci.}, Lect. Notes in Comp. Sci., Vol. 665, Springer-Verlag, 1993,  pp.\ 216--225.
\bibitem{damanik00} D.\ Damanik, Local symmetries in the period-doubling sequence, {\em Discrete Appl.\ Math.} {\bf 100} (2000), 115--121.
\bibitem{fife80} E.\ Fife, Binary sequences which contain no $BBb$, {\em Trans.\ Amer.\ Math.\ Soc.} {\bf 261} (1980), 115--136.
\bibitem{guglielmi13} N.\ Guglielmi and V.\  Protasov, Exact computation of joint spectral characteristics of linear operators. {\em Found.\  Comput.\  Math.}  {\bf 13} (2013), 37--97.
\bibitem{jungers09} R.\ M.\  Jungers, V.\ Y.\  Protasov, and V.\ D.\  Blondel, Overlap-free words and spectra of matrices. {\em Theoret. Comput. Sci.} {\bf 410} (38-40), 3670--3684.
\bibitem{kobayashi88} Y.\ Kobayashi, Enumeration of irreducible binary words. {\em Discrete\ Appl.\ Math.} {\bf 20} (1988), 221--232.
\bibitem{mousavi16}H.\ Mousavi, Automatic theorem proving in Walnut.  
Preprint, available at \url{https://arxiv.org/abs/1603.06017}~.
\bibitem{prouhet51} E.\ Prouhet, M\'emoire sur quelques relations entre les puissances des nombres, {\it C.\ R.\  Acad.\  Sci.  Paris} {\bf 33} (1851), 225.
\bibitem{rampersad07}N.\ Rampersad, {\em Overlap-Free Words and Generalizations}, Ph.D. thesis, University of Waterloo, 2007.
\bibitem{restivo84} A.\ Restivo and S.\ Salemi, Overlap-free words on two symbols, in M.\ Nivat and D.\ Perrin, eds., {\em Automata on Infinite Words}, Vol. 192 of {\em Lect. Notes in Comp. Sci.}, Springer-Verlag, 1984, pp.\ 198--206.
\bibitem{shur96} A.\ M.\ Shur, Binary words avoided by the Thue-Morse sequence, {\em Semigroup Forum} {\bf 53} (1996), pp.\ 212--219.
\bibitem{oeis} N.\ J.\ A.\ Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2023. Available
at \url{https://oeis.org}.
\bibitem{thue06} A.\ Thue, \"Uber unendliche Zeichenreihen.  {\em Kra.\ Vidensk.\ Selsk.\ Skrifter.\ I.\
Mat.\ Nat.\ Kl.} {\bf 7} (1906), pp.\ 1--22. Reprinted in {\em Selected Mathematical Papers of Axel Thue}, T.\ Nagell et al., editors, Universitetsforlaget, Oslo, 1977, pp. 139--158.
\bibitem{thue12} A.\ Thue, \"Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen.
{\em Kra.\ Vidensk.\ Selsk.\ Skrifter.\ I.\ Mat.\ Nat.\ Kl.} {\bf 1} (1912), pp.\ 1--67. Reprinted in {\em Selected Mathematical Papers of Axel Thue}, T.\ 
Nagell et al., editors, Universitetsforlaget, Oslo, 1977, pp. 413--477.
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification}: Primary 68R15.

\noindent \emph{Keywords:} combinatorics on words, word avoiding a pattern,
period-doubling word, Thue-Morse word, Fife's theorem.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  June 10 2023;
revised version received  September 18 2023; September 26 2023.
Published in {\it Journal of Integer Sequences}, September 27 2023.

\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>