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