<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
[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\usepackage{amsthm,amssymb,color,epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.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}}}

\def \prend{\vrule depth-1pt height7pt width6pt}
\def \endpf{{\hfill\prend\bigbreak}}


\begin{document}

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

\begin{center}
\vskip 1cm
{\LARGE\bf
The minimal density of a letter in an infinite ternary square-free word is
$0.2746\cdots$}
\vskip 1cm
\large Yuriy Tarannikov \\
\vskip .5cm
Mech. \&amp; Math. Department \\
Moscow State University\\
119992 Moscow, Russia\\
\vskip 0.5cm
{\href{mailto:yutaran@mech.math.msu.su}{\tt yutaran@mech.math.msu.su} \\
\href{taran@vertex.inria.msu.ru}{\tt taran@vertex.inria.msu.ru}}
\vskip 1cm
\bf {Abstract}
\end{center}

{\em

  We study the minimal density of letters in infinite
square-free words.   First, we give some definitions of
minimal density in infinite words and prove their
equivalence. Further, we propose a method that allows to
strongly reduce an exhaustive search for obtaining lower bounds for
minimal density. Next, we
develop a technique for constructing square-free morphisms
with extremely small density for one letter that gives
upper bounds on the minimal density.
As an application of our technique we prove that the minimal
density of any letter in infinite ternary square-free words is
$0.2746 \cdots$.
}


\vskip 1cm

%\section{Introduction}

  A word is called {\it square-free} if it cannot be written in the form
$axxb$ for two words $a$, $b$ and a nonempty word $x$. It is easy to see that
the maximal length of a binary square-free word is $3$. A.~Thue proved
\cite{T 06} that there exist ternary square-free words. The number of
ternary square-free words of length $n$ is given by the sequence {\bf A006156}
in The Encyclopedia of Integer Sequences \cite{SP 95}. Ekhad and Zeilberger \cite{EZ 98} 
proved that the number of ternary square-free words of length $n$ is at least
$2^{n/17}$.  Grimm \cite{G 01} gave a better bound; he proved that this
number is at least $65^{n/40}$.
Note that not every finite square-free word can be extended to an
infinite square-free word. In this paper we prove that the minimal density of
any letter in an infinite ternary square-free word is $0.2746\cdots$.

\section{Preliminary concepts and notions}

  Let $M$ be a finite alphabet, and let $M^*$ be the free monoid over $M$.
Let $M^{\omega}$ be the set of one-sided infinite words over $M$
(or mappings from ${\bf N}\to M$). A word $v\in M^*$ is called a {\it factor}
of the word $w\in M^*$ if $w$ can be written as $w=v_1 v v_2$ for some
$v_1,v_2\in M^*$. If $v_1$ is the empty word,
then $v$ is called also a {\it prefix} of $w$.
Let $F\subseteq M^*$. Denote by $l(F)$ the length of the longest word in
$F$; if the set $F$ is infinite we define $l(F) :=\infty$.
The set $F$ for $F\subseteq M^*$ is called
a {\it factorial language} if for any word $w\in F$ the set $F$ contains
every factor of $w$.  The length of the word $w$ is denoted by $|w|$.

  Any set $G$ of forbidden factors in $M^*$ generates a factorial language
$F=F(G)$ where 
$$F(G)=\{w\in M^* \ |\ \forall v\in G \quad v \hbox{ is not
a factor of } w\}.$$
Indeed, if the word $w\in F(G)$ does not contain any word $v\in G$ then
no factor $u$ of $w$ contains such a word, either.

We denote by $F^{\omega}\subseteq M^{\omega}$ the set of all infinite words
with every finite factor belonging to $F$.

\bigskip
\noindent {\bf Proposition 1.1}
{\it The set $F^{\omega}$ is not empty iff the language $F$ is infinite.}

\bigskip
{\it Proof.} If the language $F$ is finite then obviously the set
$F^{\omega}$ is empty.
If the language $F$ is infinite then we can construct an infinite word
with every finite prefix belonging to $F$ by K\"onig's Infinity Lemma.
It is easy to see that this word belongs to $F^{\omega}$.             \endpf

  Denote by $a(w)$ the number of occurrences of a letter $a\in M$ in the word
$w\in F$. The proportion $\rho_a(w)={a(w)\over |w|}$ is called the
{\it density} of the letter $a$ in the finite word $w$. To define the density
of a letter in the infinite word $w$ is a more complicated problem. We can
consider the sequence $(\rho_a(w_n))$, $n=1,2,\dots$, where $w_n$ is the
prefix of $w$ of length $n$ but it is possible that this sequence does not
converge to a limit. An example of such a situation is given by the
infinite word
$$
w=a\underbrace{b\dots b}_{10} \ 
\underbrace{a\dots a}_{10^2} \ 
\underbrace{b\dots b}_{10^4} \ 
\underbrace{a\dots a}_{10^8} \ 
\underbrace{b\dots b}_{10^{16}} \ \cdots
$$
It is not hard to see that for any positive integer $N$, positive real
$\varepsilon$ and real $\xi$, $0\le\xi\le 1$, there exists $n&gt;N$ such that
$|\rho_a(w_n)-\xi|&lt;\varepsilon$.

  Thus, it is possible that the limit of the densities for the sequence
of prefixes in an infinite word does not exist. Nevertheless, we can define
the lower limit of this sequence.

\bigskip
\noindent  {\bf Definition 1.1 }
{\it Let $F$ be an infinite factorial language. We define
$$
F(l) :=\{w\in F\,|\,\,\,|w|=l\};
$$
$$
\rho_a(F,l) :=\min\limits_{w\in F(l)} \rho_a(w); \ {\rm and}
$$
$$
\rho_a(F):= {\mathop{\underline{\rm lim}}\limits_{l\to\infty}}\rho_a(F,l).
$$
}

  The next two lemmas are proved in Kolpakov, Kucherov, and Tarannikov \cite{KKT 99}.

\bigskip
\noindent  {\bf Lemma 1.1 }
{\it For every $l\in {\bf N}$, the inequality $\rho_a(F,l)\le\rho_a(F)$ holds.}

\bigskip
\noindent  {\bf Lemma 1.2 }
{\it $\rho_a(F)=\lim\limits_{l\to\infty}\rho_a(F,l)=
\sup\limits_{l\ge 1}\rho_a(F,l)$.}
\bigskip

  Thus, we can write
$$
\rho_a(F)=\lim\limits_{l\to\infty} \rho_a(F,l).
$$

\bigskip
\noindent  {\bf Definition 1.2 } {\it We denote
$$
{\cal{A}}_a^{-}(\xi)=\{w\in F\,|\, \forall \ \hbox{\rm prefixes $u$ of } w:\,
\rho_a(u)\le \xi\},
$$
$$
{\cal{A}}_a^{-}(\xi-)=\{w\in F\,|\, \forall \ \hbox{\rm prefixes $u$ of } w:\,
\rho_a(u)&lt;\xi\}.
$$}

\bigskip
\noindent  {\bf Theorem 1.1 } {\it If $\rho_a(F)\le\xi$ then
the set ${\cal{A}}_a^{-}(\xi)$ is infinite.}

\bigskip
  {\it Proof. } Assume the converse. Then
we can decompose an arbitrary infinite word $w$
in $F^{\omega}$ into $w=v_1 v_2\dots$ where $|v_i|\le
l({\cal{A}}_a^{-}(\xi))+1$ and $\rho_a(v_i)\ge \rho_a(F)+\varepsilon$
for some $\varepsilon&gt;0$. Therefore,
$$
\lim\limits_{l\to\infty}\rho_a(F,l)\ge \rho_a(F)+\varepsilon.
$$
This contradiction proves the theorem.  \endpf

\bigskip
\noindent  {\bf Corollary 1.1 } 
\begin{itemize}
\item[(a)] {\it The set ${\cal{A}}_a^{-}(\xi)$ is infinite
iff $\xi\ge\rho_a(F)$.}

\item[(b)] {\it The set ${\cal{A}}_a^{-}(\xi-)$ is infinite
iff $\xi&gt;\rho_a(F)$.}
\end{itemize}

\bigskip
\noindent  {\bf Corollary 1.2 } {\it There exists a word $w\in F^{\omega}$ such that
any prefix $u$ of $w$ belongs to
${\cal{A}}_a^{-}(\rho_a(F))$.}

\bigskip
\noindent  {\it Proof. } We can construct easily this word $w$ by K\"onig's Lemma on
an infinite tree.  \endpf

\bigskip

  The above facts allow us to obtain lower bounds $\xi$ for the minimal
density of a letter $a$ in a factorial language $F$ proving by an exhaustive
search that the set ${\cal{A}}_a^{-}(\xi)$ (${\cal{A}}_a^{-}(\xi-)$) is
finite. As it will be shown below in many cases for sufficiently small $\xi$
this exhaustive search can be produced in a very short time.


\section{Minimal letter density for some special factorial languages}

  For some special factorial languages the problem of finding the minimal
letter density is (almost) trivial.

\bigskip
\noindent
  {\it Example 2.1 } The factorial language $F=F(G)$ is generated by
a finite set $G$ of prohibited factors. Then the minimal letter density
$\rho_a(F)$ is rational and equal to the minimal density of the letter $a$
over all cycles (accessible from the starting vertex) in the transition graph
of language $F(G)$. (For transition graphs of factorial languages see
Rosaz \cite{R 93}.)

\bigskip
\noindent
  {\it Example 2.2 } Let $M=\{0,1\}$, and let $\xi$ be a real number with $\xi\in (0;1)$.
Let $F$ be the set of all finite factors of a standard Sturmian word
$(a_1 a_2 \cdots)$ where $a_i=\lfloor (i+1)\xi\rfloor - \lfloor i\xi\rfloor$,
$i=1,2,\ldots$. Then any infinite word in $F^{\omega}$ has density $\xi$.
So, $\rho_1(F)=\xi$.

\bigskip
\noindent
  {\it Example 2.3 } Let $M=\{a,b\}$ and let $F$ be the set of all overlap-free
binary words (i.~e.,~words that do not contain a factor $w$ that has the
form $w=v_1 v_2 c$ where $c$ is the first letter of the word $v_1$).
Restivo and Salemi \cite{RS 83} proved that any infinite overlap-free binary
word is a concatenation of factors $(ab)$ and $(ba)$ with a preperiod
of one or two symbols. It follows that $\rho_a(F)=\rho_b(F)=1/2$.

\bigskip
\noindent
  {\it Example 2.4 } Infinite square-free words on the alphabet $M$
(i.~e.,~words that do not contain a factor $w$ that has the form $w=vv$).
It is obvious that if $|M|=2$ then there are no infinite square-free
words over alphabet $M$. There exist infinite square-free words on
the ternary alphabet. A. Thue was the first to construct an example of
such a word \cite{T 06}. Therefore, if $|M|\ge 4$ we can construct an
infinite square-free word over the alphabet $M\setminus\{a\}$. Consequently,
$\rho_a(F)=0$. Thus, the only interesting case in this respect
is $|M|=3$.

\section{Lower bounds for the minimal letter density in ternary square-free
words}

  In what follows $F$ denotes the set of all ternary square-free words.
The technique used to obtain the results given in this
section was developed in Section 1. In the following table we give
calculated values of numbers
$l({\cal{A}}_a^{-}(\xi-))$ and $l({\cal{A}}_a^{-}(\xi))$ for
``critical'' $\xi$ (i.~e., for $\xi$ such that these numbers differ).
In our computer search we used the standard backtracking technique.
For $\xi&gt;39/142$ we did not calculate all ``critical'' values of $\xi$
because of the increasing of the required computer time.

\bigskip
\noindent  {\bf Theorem 3.1 } {\it $l({\cal{A}}_a^{-}(1780/6481-))=17312$.}

  The last result took near 40 hours on a Pentium, 166 MHz.

\bigskip
\noindent  {\bf Corollary 3.1 } {\it Let $F$ be the set of ternary square-free words.
Then $\rho_a(F)\ge 1780/6481=0.274648 \cdots$ for all letters $a$.}

\begin{center}
\begin{tabular}{|l||r|r|r|}
\hline
$\xi$ (Proportion) &amp; $\xi$ (Decimal) &amp; $l({\cal{A}}_a^{-}(\xi-))$
&amp; $l({\cal{A}}_a^{-}(\xi))$ \\
\hline
\hline
0        &amp;  0               &amp;      0              &amp;            3   \\
\hline
1/4      &amp;  0.25            &amp;      3              &amp;           15   \\
\hline
4/15     &amp;  0.266666        &amp;     15              &amp;           59   \\
\hline
16/59    &amp;  0.271186        &amp;     59              &amp;           63   \\
\hline
3/11     &amp;  0.272727        &amp;     63              &amp;           74   \\
\hline
20/73    &amp;  0.273973        &amp;     74              &amp;          136   \\
\hline
37/135   &amp;  0.274074        &amp;    136              &amp;          198   \\
\hline
54/197   &amp;  0.274112        &amp;    198              &amp;          252   \\
\hline
17/62    &amp;  0.274194        &amp;    252              &amp;          307   \\
\hline
14/51    &amp;  0.274510        &amp;    307              &amp;          324   \\
\hline
81/295   &amp;  0.274576        &amp;    324              &amp;          771   \\
\hline
67/244   &amp;  0.274590        &amp;    771              &amp;          801   \\
\hline
53/193   &amp;  0.274611        &amp;    801              &amp;         1034   \\
\hline
145/528  &amp;  0.274621        &amp;   1034              &amp;         1318   \\
\hline
92/335   &amp;  0.274627        &amp;   1318              &amp;         1481   \\
\hline
407/1482 &amp;  0.274629        &amp;   1481              &amp;         1500   \\
\hline
354/1289 &amp;  0.274631        &amp;   1500              &amp;         1765   \\
\hline
485/1766 &amp;  0.274632        &amp;   1765              &amp;         1784   \\
\hline
170/619  &amp;  0.274637        &amp;   1784              &amp;         2028   \\
\hline
549/1999 &amp;  0.274637        &amp;   2028              &amp;         2494   \\
\hline
209/761  &amp;  0.274639        &amp;   2494              &amp;         2778   \\
\hline
613/2232 &amp;  0.274642        &amp;   2778              &amp;         3488   \\
\hline
691/2516 &amp;  0.274642        &amp;   3488              &amp;         3772   \\
\hline
443/1613 &amp;  0.274644        &amp;   3772              &amp;         4168   \\
\hline
950/3459 &amp;  0.274646        &amp;   4168              &amp;         4715   \\
\hline
1028/3743&amp;  0.274646        &amp;   4715              &amp;         4999   \\
\hline
1223/4453&amp;  0.274646        &amp;   4999              &amp;         5709   \\
\hline
1301/4737&amp;  0.274646        &amp;   5709              &amp;         5993   \\
\hline
1496/5447&amp;  0.274647        &amp;   5993              &amp;         6703   \\
\hline
1574/5731&amp;  0.274647        &amp;   6703              &amp;         6987   \\
\hline
1769/6441&amp;  0.274647        &amp;   6987              &amp;         7383   \\
\hline
1847/6725&amp;  0.274647        &amp;   7383              &amp;         7667   \\
\hline
39/142   &amp;  0.274647        &amp;   7667              &amp;        10882   \\
\hline
\strut  &amp; &amp; &amp; \\
\hline
1780/6481&amp;  0.274648        &amp;  17312              &amp;                \\
\hline
\end{tabular}
\end{center}

\vskip 3truemm

\centerline{Table 1. Numbers
$l({\cal{A}}_a^{-}(\xi-))$ and $l({\cal{A}}_a^{-}(\xi))$ for some ``critical''
$\xi$.}

\section{Upper bound}

  The most natural way to prove an upper bound for
the minimal letter density is to construct a concrete word. As a result
the letter density in this word will be a desired upper bound. One of the main
ways for constructing concrete infinite words is to use expansive morphisms. We consider
morphisms of the form $\,h:\,M^*\to M^*$. In our case $M=\{a,b,c\}$. For
$d\in M$ the infinite word $h^*(d)$ is generated by the infinite sequence of
its prefixes 
$$d, h(d), h(h(d)), h(h(h(d))),\ldots  \ .$$
A morphism $h$ is called
{\it square-free} if $h(w)$ is square-free whenever $w$ is square-free.
If $h$ is a square-free morphism then, obviously, for any letter $d\in M$
the word $h^*(d)$ will be square-free. If for any letter $m\in M$
we have $\rho_a(h(m))=\xi$ then, obviously, $\rho_a(h^*(d))=\xi$ too.
The words $h(m)$ are finite, therefore here $\xi={p\over q}$ is rational.
Thus, the simplest way is to try to construct a morphism where images
of all letters consist of fragments of lengths $q$ that contain the letter $a$
exactly $p$ times for some positive integers $p$ and $q$. The problem is how
to choose $p$ and $q$? Here we give an empirical method of selecting good
parameters $p$ and $q$.

  Let $\xi={p\over q}$ be a rational number. Define
$${\cal{A}}_a^{-}(\xi*)=\{w\in F\,|\, \forall \ \hbox{\rm prefixes $u$ of } w:\,
\rho_a(u)&lt;\xi
\hbox{ \rm and if } |u|=nq, n\in {\bf N},
\hbox{ \rm then }
\rho_a(u)=\xi\}.
$$

  For a given rational $\xi$ we search an (infinite) word in the set
${\cal{A}}_a^{-}(\xi*)$ by the usual backtracking technique. In many cases
we obtain in a short time that the set ${\cal{A}}_a^{-}(\xi*)$ is finite.
Thus, we cannot apply the proposed method for the construction of a morphism.
If the length
of the maximal found prefix increases with stable high speed then we do an
empirical conclusion that a morphism with proportion $p$ to $q$ can exist.
If the length of the maximal found prefix increases very slowly
we conclude that probably such a morphism does not exist.

  This empirical method can be applied to the problem of minimal letter
density in any factorial language. At first, we tried it for ternary
square-free words. We obtained very strong empirical confirmation
for the ratio $64/233$. The set
${\cal{A}}_a^{-}(64/233*)$ contains only 10 words of length $233$
($5$ up to replacing $b\leftrightarrow c$).
Combining these words we tried to construct a square-free morphism.
We used the following test of Bean, Ehrenfeucht, and McNulty \cite{BEM 79}
that guarantees that a morphism is square-free:

\begin{quote}
  \underline{\bf If}

  (0) $h(w)$ is square-free whenever $w$ is a word on $M$ which is
square-free and of length not greater than three,

  and

  (1) $a=b$ whenever $a,b\in M$ with $h(a)$ a subword of $h(b)$

  \underline{\bf then}

  $h(u)$ is square-free whenever $u$ is a square-free word on $M$.
\end{quote}

  In our case it is sufficient to check that

  (1) $h(a)$, $h(b)$ and $h(c)$ are not factors of one another,

  (0) the words
$$
\begin{array}{ccc}
h(a)h(b)h(a) &amp; h(b)h(a)h(b) &amp; h(c)h(a)h(b) \\
h(a)h(b)h(c) &amp; h(b)h(a)h(c) &amp; h(c)h(a)h(c) \\
h(a)h(c)h(a) &amp; h(b)h(c)h(a) &amp; h(c)h(b)h(a) \\
h(a)h(c)h(b) &amp; h(b)h(c)h(b) &amp; h(c)h(b)h(c)
\end{array}
$$
are square-free.

  The desired morphism was constructed. We give it here.
Denote
$$
\begin{array}{lcc}
A = bcbacbcabcbabcacbcabcbacbcacbabcbacbcabcbabcacbabcbacbcacbabcacbcabcbacbcacb \\
abcbacbcabcbabcacbcabcbacbcacbabcacbcabcbabcacbabcbacbcabcbabcacbcabcbacbcacbabc \\
bacbcabcbabcacbabcbacbcacbabcacbcabcbacbcacbabcbacbcabcbabcacbcabcbacbcabacba \\
\\
B = bcbacbcabcbabcacbcabcbacbcacbabcbacbcabcbabcacbabcbacbcacbabcacbcabcbacbcacb \\
abcbacbcabcbabcacbcabcbacbcacbabcacbcabcbabcacbabcbacbcabcbabcacbcabcbacbcacbabc \\
bacbcabcbabcacbabcbacbcacbabcacbcabcbacbcacbabcbacbcabcbabcacbcabcbacbcacbaca \\
\\
B'= cbcabcbacbcacbabcbacbcabcbabcacbcabcbacbcacbabcacbcabcbabcacbabcbacbcabcbabc \\
acbcabcbacbcacbabcbacbcabcbabcacbabcbacbcacbabcacbcabcbacbcacbabcbacbcabcbabcacb \\
cabcbacbcacbabcacbcabcbabcacbabcbacbcabcbabcacbcabcbacbcacbabcbacbcabcbabcaba \\
\\
C = bcbacbcabcbabcacbcabcbacbcacbabcbacbcabcbabcacbcabcbacbcabacbabcbacbcabcbabc \\
acbcabcbacbcacbabcbacbcabcbabcacbabcbacbcacbabcacbcabcbacbcacbabcbacbcabcbabcacb \\
cabcbacbcacbabcacbcabcbabcacbabcbacbcabcbabcacbcabcbacbcacbabcbacbcabcbabcaba \\
\\
D = bcbacbcabcbabcacbcabcbacbcacbabcbacbcabcbabcacbcabcbacbcabacbabcbacbcabcbabc \\
acbcabcbacbcacbabcbacbcabcbabcacbabcbacbcacbabcacbcabcbacbcacbabcbacbcabcbabcacb \\
cabcbacbcacbabcacbcabcbabcacbabcbacbcabcbabcacbcabcbacbcacbabcbacbcabcbacabca \\
\\
D'= cbcabcbacbcacbabcbacbcabcbabcacbcabcbacbcacbabcbacbcabcbacabcacbcabcbacbcacb \\
abcbacbcabcbabcacbcabcbacbcacbabcacbcabcbabcacbabcbacbcabcbabcacbcabcbacbcacbabc \\
bacbcabcbabcacbabcbacbcacbabcacbcabcbacbcacbabcbacbcabcbabcacbcabcbacbcabacba
\end{array}
$$
(the words $B'$ and $D'$ can be derived from $B$ and $D$ respectively
by replacing $b\leftrightarrow c$).

  The constructed morphism $h$ is
$$
\begin{array}{lcc}
h(a)=BA \\
h(b)=BDB'D'\\
h(c)=BCB'D'
\end{array}
$$

  As a result of this construction we conclude that

\bigskip
\noindent {\bf Theorem 4.1 }
{\it Let $F$ be the set of ternary square-free words.
Then $\rho_a(F)\le 64/233=0.274678\cdots$ for all letters $a$.}

\bigskip

  In combination with the lower bound given in Corollary 4.1 we have

\bigskip
\noindent  {\bf Theorem 4.2 } {\it Let $F$ be the set of ternary square-free words.
Then $0.274648\cdots =1780/6481\le\rho_a(F)\le 64/233=0.274678 \cdots$ for all letters
$a$.

  Thus, $\rho_a(F)=0.2746 \cdots$.}

\section{Acknowledgments}

  The author is grateful to the anonymous referee for the detailed comments
which improved the readability of the paper.

\begin{thebibliography}{8}

\bibitem {BEM 79}
D. R. Bean, A. Ehrenfeucht, and G. F. McNulty, Avoidable patterns in strings
of symbols, {\it Pacific J. Math.} {\bf 85} (1979), 261--294.

\bibitem {EZ 98}
S. B. Ekhad and D. Zeilberger, There are more than $2^{n/17}$ $n$-letter ternary
square-free words, {\it J. Integer Sequences} {\bf 1} (1998), Article 98.1.9.

\bibitem {G 01}
U. Grimm, Improved bounds on the number of ternary square-free words,
{\it J. Integer Sequences} {\bf 4} (2001), Article 01.2.7.

\bibitem {KKT 99}
R. Kolpakov, G. Kucherov, and Yu. Tarannikov, On repetition-free binary words of
minimal density, {\it Theoret.\ Comput.\ Sci.} {\bf 218} (1999), 161--175.

\bibitem {RS 83}
A. Restivo, S. Salemi, On weakly square free words, {\it Bulletin of the EATCS},
No.\ 21 (1983), 49--56.

\bibitem {R 93}
L.~Rosaz, Unavoidable sets of words, Th\`{e}se de doctorat,
Universit\'{e} Paris 7, 1993.

\bibitem {SP 95}
N. J. A. Sloane, S. Plouffe, {\it The Encyclopedia of Integer Sequences},
Academic Press, 1995. See also On-line Encyclopedia of Integer Sequences.
Available at
{\tt http://www.research.att.com/\~{}njas/sequences/}.

\bibitem {T 06}
A. Thue, \"Uber unendliche Zeichenreihen,
{\it Norske Videnskabers Selskabs Skrifter I, Matematisk-Naturvidenskapelig Klasse},
Kristiania, {\bf 7} (1906), 1--22.


\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: 11B05 .\ \ 

\noindent \emph{Keywords:  Combinatorics on words; square-free word;
factorial languages; minimal density}

\bigskip
\hrule
\bigskip

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


\vspace*{+.1in}
\noindent
Received March 21, 2002;
revised version received  October 20, 2002.
Published in Journal of Integer Sequences October 24, 2002.



\bigskip
\hrule
\bigskip

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


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