\documentclass[12pt]{article} \usepackage{e-jc} \usepackage[english]{babel} \usepackage{gastex} \usepackage{amssymb,amsfonts,amsmath, amsthm} \usepackage{cite} \usepackage{cancel} \DeclareMathOperator{\per}{per} \DeclareMathOperator{\lexp}{lexp} \def\SF{{\sf SF}} \def\A{{\sf A}} \def\B{{\sf B}} \def\cwd{{\sf cwd}} \def\cwk{{\sf cwk}} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \title{\bf Avoiding Letter Patterns in Ternary Square-Free Words} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Elena A. Petrova\\ \small Department of Mathematics and Computer Science\\[-0.8ex] \small Ural Federal University\\[-0.8ex] \small Ekaterinburg, Russia\\ \small\tt Elena.Petrova@urfu.ru\\ } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Jul 10, 2015}{}\\ \small Mathematics Subject Classification: 68R15} \begin{document} \maketitle \begin{abstract} We consider special patterns of lengths 5 and 6 in a ternary alphabet. We show that some of them are unavoidable in square-free words and prove avoidability of the other ones. Proving the main results, we use Fibonacci words as codes of ternary words in some natural coding system and show that they can be decoded to square-free words avoiding the required patterns. Furthermore, we estimate the minimal local (critical) exponents of square-free words with such avoidance properties. \\ \bigskip\noindent \textbf{Keywords:} square-free ternary words, pattern avoidability, Fibonacci words. \end{abstract} \section{Introduction} Repetition-free words and morphisms are among the most important objects of study in combinatorics on words and formal language theory. At the beginning of the 20th century Axel Thue constructed an infinite square-free word over ternary alphabet~\cite{Th06} and an infinite binary cube-free (and, moreover, overlap-free) word~\cite{Th12}. Since Thue, the most popular constructions for infinite repetition-free words were based on repetition-free morphisms, intensively studied in many works; see, e.g., the book \cite{Lo83}, and also papers \cite{Cr82,Kar83,RiWl02}. Sometimes, more general substitutions were used instead of morphisms, for example in the Arshon words \cite{Ars37}. Constructing repetition-free words with additional restrictions forms a significant share of important and interesting tasks in the study of repetition-free words. In~\cite{Th12} Thue posed a question: which of the three-letter words over ternary alphabet are avoidable by square-free words? He showed that the word $abc$ and thus any word obtained from it by permuting the alphabet is unavoidable. Also he considered the pairs of words, where the first one is from the set $\{aba, bcb, cac\}$ and the other is from $\{bab, cbc, aca\}$, and proved that all these pairs are avoidable. %Many papers are devoted to avoidability of binary patterns in binary cube-free words; see, e.g.,~\cite{GoVa91, Och10, Ro92}. Related research was also done for other repetition-free words, like the binary cube-free words. A full description of binary patterns avoidable by these words was obtained in~\cite{MeShSa}. Another interesting restriction was offered in~\cite{RaSh05} where the authors constructed an infinite binary cube-free word with squares of length at most 4. In~\cite{BaCr11, BaCrRa}, it was shown that there exist infinite words over a $k$-letter alphabet, where $k\geq3$, containing only a finite number of distinct factors of exponent $RT(k)$, which is the repetition threshold from Dejean's conjecture \cite{Dej72} equal to the infimum of avoidable powers over the $k$-letter alphabet. In this paper, we continue the investigations of Thue and consider the avoidability of more general patterns in ternary square-free words. These patterns are words over an alphabet of variables $\{x,y,z\}$, where each variable stands for one letter from $\{a,b,c\}$ and different variables denote different letters. For example, the pattern $xyxzx$ represents the set of words $\{abaca, acaba, babcb, bcbab, cacbc, cbcac\}$; to prove that this pattern is avoidable, we need to build an infinite square-free word over $\{a,b,c\}$ containing no factors from this set. We call such patterns ``letter patterns''. It follows immediately from the results of Thue that square-free letter patterns of length 3 and 4 are unavoidable. We consider all square-free letter patterns of lengths 5 and 6 and clarify their avoidability status, proving the following \begin{theorem}\label{mpt} The following ternary square-free letter patterns are avoidable by ternary square-free words: (a) $xyxzx$, $xyzxy$; (b) $xyxzyz$ and all patterns of length 6 containing a pattern from (a). All other such patterns of length $\le 6$ are unavoidable by ternary square-free words. \end{theorem} To construct square-free words for avoidable letter patterns and to prove that the other ones are unavoidable we use an idea %in generating repetition-free words suggested by Pansiot \cite{Pan84c} who proposed, in relation with Dejean's conjecture, a binary encoding for $k$-ary words avoiding ``local'' repetitions. Pansiot used a morphism to generate an infinite binary word which ``decodes'' into a quaternary word avoiding all powers greater than $RT(4)=7/5$. The approach based on Pansiot's encoding was used in all later papers devoted to the proof of different cases of Dejean's conjecture. For example, Rao \cite{Rao11} built the appropriate binary codewords as morphic images of the Thue-Morse word (which is itself generated by a morphism). %This infinite square-free word is generated by a pair of substitutions and avoids not only squares but all powers greater than $7/4$~\cite{KlSu99}. Shur developed the idea of Pansiot's encoding for the case of ternary square-free words~\cite{Sh10jc}. Namely, in this case the Pansiot codeword can be represented by a walk in a weighted $K_{3,3}$ graph, where each vertex has edges of weights 1, 2, and 3. Due to symmetry, such a walk is just a ternary sequence of weights, called a \emph{codewalk}. In the cited paper, codewalks generated by means of morphisms were used to generate circular square-free words. It appears that letter patterns of lengths 5 and 6 have clear representations in terms of codewalks. The only three avoidable letter patterns correspond to codewalks containing just two weights of the three available. Also by means of codewalks it is easy to prove that the remaining letter patterns are unavoidable by square-free words. In each case of an avoidable pattern the famous Fibonacci word (also generated by a morphism) is used as the codewalk. After proving that the Fibonacci word decodes to a square-free word in all cases, we describe more precisely the fractional powers avoided by each of obtained square-free words. %Further, it appears that the codewalk of the ternary Arshon word admits a very simple description in terms of morphisms \cite{PeSh12}. So, an interesting question is to study the connection between the codewalks and the square-free words generated by them. % %An important feature of the codewalks is that they can contain squares and even bigger powers (of some words). So, a natural question is whether one can generate a square-free word with a codewalk using just two weights of the three available? In this paper, we answer this question in the affirmative for each pair of weights. The famous Fibonacci word (also generated by a morphism) is used as the codewalk in each case. \section {Preliminaries} \subsection {Notation and definitions} An \textit{alphabet} $\Sigma$ is a nonempty finite set, the elements of which are called \textit{letters}. We consider finite and infinite sequences of letters both called {\it words} over the binary alphabet $\{a,b\}$, the ternary alphabet $\{a,b,c\}$, and some auxiliary alphabets. The \textit{empty word} is denoted by $\lambda$. We write $|W|$ for the length of a word $W$. %? The letters of nonempty finite and infinite words are numbered from 1; thus, $W=W[1 .. |W|]$ for a finite word. We use standard definitions of factors, prefixes, and suffixes of a word. Words $U$ and $V$ are called \textit{conjugates} if there exist two words $X$ and $Y$ such that $U=XY$ and $V=YX$. We also call $V$ a {\it cyclic shift} of $U$. A positive integer $p\leq |W|$ is a \textit{period} of a word $W$ if $W[1..|W|{-}p]=W[1{+}p..|W|]$. If $p$ is the minimal period of $W$, we use a standard notation $W=U^k$, where $U = W[1..p]$ and $k = |W|/p$. In this case, we call $U$ the {\it root} of $W$ and $k$ the \textit{exponent} of $W$ (denoted by $\exp(W)$). Words of exponent 2 and 3 are called \emph{squares} and {\it cubes}, respectively. A square is {\it minimal} if it does not contain shorter squares as factors. The \textit{local exponent} of a word is the number $\lexp(W)=\sup\{\exp(V)\mid V\text{ is a factor of } W\}$. Local exponents of infinite words are also called \textit{critical exponents}. A word $W$ is $\beta$-free [$\beta^+\!$-free] if $\lexp(W)<\beta$ [respectively, $\lexp(W)\le \beta$]. The 2-free words are called \textit{square-free}. It is obvious that a word is square-free if and only if it contains no minimal squares as factors.%The language of square-free words over $\Sigma$ is denoted by $\SF$. %морфизм! %Consider the substitutions $\alpha_o$ (``odd'') and $\alpha_e$ (``even'') over the alphabet $\Sigma$: %\begin{equation} \label{arsub} %\alpha_o:\ a\to abc,b\to bca,c\to cab,\quad \alpha_e:\ a\to cba,b\to acb,c\to bac %\end{equation} %These substitutions are extended to the function $\alpha:\Sigma^*\to\Sigma^*$ in the following way. To get the image of a word $W$, substitutions \eqref{arsub} are applied to each letter $W[i]$; if $i$ is odd [even], then the odd [resp., the even] substitution is used. From the definition it follows that the word $\alpha^k(a)$ is a prefix of $\alpha^{k+1}(a)$ for any $k\ge0$. Hence, one can consider the ``limit'' right-infinite word %$$ %\A=\alpha^\infty(a)=abc\,acb\,cab\,cba\,cab\,acb\,cab\,cba\,bca\ldots, %$$ %which was introduced in \cite{Ars37} and is called the \textit{Arshon word}. We also consider the reversal $\overleftarrow{\A}$ of $\A$. The word $\A$ is square-free \cite{Ars37} and, moreover, $(7/4)^+\!$-free \cite{KlSu99}. The factors of $\A$ are called \emph{Arshon factors}. % %\begin{remark} \label{ars1} %Some Arshon factors occur in $\A$ in positions of different parity and thus have two different $\alpha$-images. We write $\alpha_o(W)$ [$\alpha_e(W)$] for the image of the factor $W$ if $W$ begins in $\A$ at an odd [resp., even] position. Obviously, the Arshon factor $\alpha_o(W)$ [$\alpha_e(W)$] begins in an odd [resp., even] position. Thus, $W$ has at most two different $\alpha^k$-images, denoted by $\alpha_o^k(W)$ and $\alpha_e^k(W)$, for any $k>0$. %\end{remark} %We call a language \emph{symmetric} if it is stable under all permutations of the alphabet. The following lemma is straightforward. %\begin{lemma} \label{ars} %The set of Arshon factors is symmetric. %\end{lemma} %The words $U$ and $V$ are \textit{conjugates} if exists two words $X$ and $Y$ such that $U=XY$ and $V=YX$. If we link up the ends of a word $U$, we will get a cyclic sequence of letters called a \textit{circular word} and denoted by $(U)$. A circular word represents a conjugacy class of ordinary words. By definition, the factors of $(U)$ are ordinary words of length $\leq |U|$ including $U$ and its conjugates. The word $V=U^2$ is called a {\it minimal square} if all its proper factors are square-free. Clearly, a word is square-free if and only if there are no minimal squares among its factors. The following proposition shows the role of circular words in the study of square-free words. % %\begin {proposition}[\!\cite{Sh10jc}] \label{minsq} %The word $U^2$ is a minimal square if and only if $(U)$ is square-free. %\end {proposition} \subsection {Fibonacci words} Consider the {\it Fibonacci morphism} $\phi$, defined over the binary alphabet by the equalities $\phi(a) = ab, \phi(b) = a$. The iteration of this morphism on the letter $b$ gives the {\it Fibonacci words}: $f_{-1} = b, f_0 = a, f_1 = ab, f_2 = aba, f_3 = abaab, f_4 = abaababa,$ and so on. Since $f_n$ is a prefix of $f_{n+1}$ for any $n \in \mathbb{N}$, one can consider the infinite word ${\sf f}=\lim_{n \rightarrow \infty}\{f_n\}$ which is the fixed point of $\phi$. We call $\sf f$ the {\it Fibonacci $\omega$-word} to distinguish it from finite Fibonacci words (notice that in~\cite{Lo02} the term ``Fibonacci word'' is used only for this infinite word). We will use the following properties of the Fibonacci words: \begin{enumerate} \item \label{f1} $\sf f$ is a {\it Sturmian} word, i.e. it has exactly $n+1$ different factors of length $n$~\cite{Lo02}. %\item \label{f2} Fibonacci words contain cubes, but no forth powers~\cite{Kar83}. \item \label{f2} $f_n = f_{n-1}f_{n-2}$ for all $n \in \mathbb{N}$. \item \label{f3} The length of the $n$th Fibonacci word is the $n$th Fibonacci number $\Phi_n$ for all $n \in \mathbb{N}$ (assuming $\Phi_0=1$, $\Phi_1=2$; follows from property~\ref{f2}). \item \label{f4} The Fibonacci $\omega$-word does not contain factors $aaa$ and $bb$ (words with such factors have no preimages under $\phi$). \item \label{f5} If a factor of the Fibonacci $\omega$-word has nontrivial periods, then its minimal period is a Fibonacci number~\cite{CuSa09}. \item \label{f6} $\lexp(\sf {f})=2 + \rho$, where $\rho$ is the golden ratio; this supremum is not reached, so the local exponent of any Fibonacci word is smaller than $2 + \rho$~\cite{MiPi92}. \item \label{f7} If $u^k$ is a factor of $\sf f$, where $u \neq \lambda, k > (2 + \rho)/2$, then there exists $n \geq 1$ such that $u$ is a conjugate of $f_n$ and, moreover, each occurence of $u^k$ is contained in a maximal one of $f_n^s$ for some $s \in [2, 2 + \rho)$~\cite{Pi97}. \item \label{f8} The length of a factor in $\sf f$ whose period is $\Phi_n$ is at most $\Phi_{n+1} + 2\Phi_n - 2$~\cite{MiPi92}. \end{enumerate} \subsection{Codewords and codewalks} \label{s:cwdk} Any ternary word $U$ of length $\geq 3$ containing no squares of letters (in particular, any ternary square-free word) can be encoded by a binary \textit{Pansiot codeword} $\cwd(U)$ of length $|U|-2$. \begin {equation*} \cwd(U)[i] = \begin{cases} 0 & \text{ if $U[i]=U[i{+}2]$,}\\ 1 & \text{ otherwise}; \end{cases} \end{equation*} for example, \begin{equation*} \begin{array}{rclllllllll} \phantom(U\phantom)&=&a&b&c&b&a&c&b&c&\ldots\ ,\\ \cwd(U)&=&1&0&1&1&1&0&&&\ldots\ . \end{array} \end {equation*} This type of encoding was proposed in \cite{Pan84c} for bigger alphabets and studied in \cite{Sh10jc} for the ternary alphabet. We recall some facts from~\cite{Sh10jc}. The codewords of square-free words are also called square-free. Let us consider them. They do not contain the factors $00$ and $1111$ encoding the squares of period 2 and 3, respectively. Zeroes in a codeword correspond to the ``jumps'' of one letter over another letter in the encoded word. There are six such jumps, represented by the factors $aba$, $bcb$, $cac$, $aca$, $bab$, and $cbc$. We call the first three jumps \textit{right} and the remaining jumps \textit{left}. A right jump in a square-free word is always followed by a left jump and vice versa. The next jump is obtained from the previous one by\\ - changing the central letter (e.\,g., $aba\leftrightarrow aca$) if the $0$'s are separated by $1$;\\ - changing the side letters (e.\,g., $aba\leftrightarrow cbc$) if the $0$'s are separated by $11$;\\ - switching the letters (e.\,g., $aba\leftrightarrow bab$) if the $0$'s are separated by $111$. \begin{figure}[htb] \vspace*{-3mm} \centerline{ \unitlength=1.1mm \begin{picture}(60,28)(0,1) \gasset{Nw=7,Nh=7,AHnb=0,ELdist=0.2,ELpos=70}%,Nframe=n \node(f1)(10,5){$aba$} \node(f2)(30,5){$bcb$} \node(f3)(50,5){$cac$} \node(c1)(10,25){$bab$} \node(c2)(30,25){$cbc$} \node(c3)(50,25){$aca$} \drawedge[linewidth=0.4](f1,c1){$_{3}$} \drawedge[ELpos=30](f1,c2){$_{2}$} \drawedge[ELpos=77,linewidth=0.4](f1,c3){$_{1}$} \drawedge[linewidth=0.4](f2,c1){$_{1}$} \drawedge[ELside=r](f2,c2){$_{3}$} \drawedge[ELside=r,linewidth=0.4](f2,c3){$_{2}$} \drawedge[ELside=r,ELpos=77](f3,c1){$_{2}$} \drawedge[ELside=r,ELpos=30](f3,c2){$_{1}$} \drawedge[ELside=r](f3,c3){$_{3}$} \end{picture} } \caption{The graph of jumps in ternary words. Bold edges mark the closed codewalk (1213).}\label{k33} \vspace*{-3mm} \end{figure} %%%%%%%%%%%%% In order to describe square-free codewords, the complete bipartite graph $K_{3,3}$ is used. Left [right] jumps correspond to the bottom [resp., top] part of the graph. The number of $1$'s between two jumps equals the weight of the edge connecting the corresponding vertices. Each square-free codeword not equal to $0$ corresponds to a walk represented as a sequence of edge weights (i.\,e., words over $\{{\sf 1,2,3}\}$) in the weighted graph shown in Fig.~\ref{k33}. We call such sequences {\it codewalks}. Note that Thue~\cite{Th12} proved that for any pair of vertices $(x,y)$, where $x$ is from the top part and $y$ is from the bottom part, there exists an infinite walk which does not contain $x$ and $y$ and correspons to a square-free word. In order to decode a word from a codewalk uniquely, one has to keep the first two letters of this word \emph{and the information about the leading and trailing 0's in the codeword}. \begin{example} A ternary word $abacbabcacbcabc$ has the codeword $0111011010111$ and the codewalk $\sf 3213$. Depending in the leading and trailing zeroes, this codewalk corresponds to three more codewords $111011010111$, $1110110101110$, and $01110110101110$. Starting with the same letters $ab$, the second of these codewords decodes as $abcabacbcacbaca$, which has little in common with the initial word. %$cbacbcabacabcac$. \end{example} Since we are interested in constructing codewalks (corresponding to square-free words), for convenience we assume that codewords corresponding to these codewalks always start with $0$. \begin{remark} If a codewalk $X$ decodes to a word $W$, then a suffix of $X$ decodes, in general, to an image of the corresponding suffix of $W$ under some permutation of the alphabet. %Note that if we decode some suffix of a codewalk we obtain a word equal to some suffix of initial word up to renaming of letters in $\{a,b,c\}$. \end{remark} Due to symmetry, the sequence of weights in $K_{3,3}$ determines whether the walk is closed independently of the initial vertex. Any closed walk is a combination of simple cycles (a closed walk of length two is considered as a simple cycle also). \begin{remark}~\cite{Sh10jc}\label{ms} There are no minimal squares with periods 5, 7, 9, 10 over a ternary alphabet. The roots of length $\ge 11$ in periodic words are coded by the codewalks of length $\ge 4$. \end{remark} \begin{remark}~\cite{Sh10jc}\label{pw} Any infinite codewalk of a square-free word does not contain $\sf 11$, $\sf 222$, $\sf 223$, $\sf 322$, $\sf 333$ as factors. \end{remark} The next lemma is crucial for constructing ternary square-free words from codewalks. \begin{lemma}[\!\cite{Sh10jc}] \label{lcw} A %closed codewalk having (a) no factors $\sf 11$, $\sf 222$, $\sf 223$, $\sf 322$, $\sf 333$, and (b)~no factors of the form $XYX$ such that $|Y|=2$, $|X|$ is even, and $(XY)$ is the label of a closed walk, decodes to a square-free word. \end{lemma} %We define a codewalk $\cwk(U)$ for an arbitrary ternary square-free word $U$ as follows. Take the codeword $\cwd(U)$, replace each block of 1's by its length and omit all 0's. For uniqueness, it is necessary to keep the information about the first and the last letters of $\cwd(U)$ (e.g., if $\cwd(U)[1]=1$, then the first block of 1's in $\cwd(U)$ can be a factor of a longer block). We will underline the first [last] letter of $\cwk(U)$ if $\cwd(U)$ begins [resp., ends] with 1. For example, %$$ %U=abcacbacaba,\quad \cwd(U)=110111010,\quad \cwk(U)=\underline{2}31. %$$ By \textit{square-free codewalks} we mean the codewalks decoding to square-free words. Note that square-free codewalks are ternary words with much weaker restrictions than square-freeness: squares in codewalks are permitted if their roots are not closed walks. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Letter patterns and codewalks}\label{s:lpc} In this section we start the proof of Theorem~\ref{mpt}. We show which of 5-letter and 6-letter patterns are unavoidable using the properties of codewalks and present an idea for constructing ternary square-free words avoiding the remaining such patterns. Note that all words represented by a letter pattern have the same codeword. First, consider all square-free 5-letter patterns and their codewords. %They are: $xyxzx$, $xyxzy$, $xyzxy$, $xyzxz$, and $xyzyx$. Th $$ \begin{array}{ccccc|cccccc|cccccc|cccccc|cccccc} x&y&x&z&x& &x&y&x&z&y& &x&y&z&x&y& &x&y&z&x&z& &x&y&z&y&x\\ 0&1&0& & & &0&1&1& & & &1&1&1& & & &1&1&0& & & &1&0&1& & \end{array} $$ By Remark~\ref{pw}, letter patterns $xyxzy$ and $xyzxz$ are unavoidable since $\sf{11}$ is prohibited in codewalks of square-free words. The pattern $xyzyx$ is also unavoidable since $00$ and $1111$ in codewords correspond to squares. The other two letter patterns of length 5 are avoidable if there exist codewalks of infinite square-free words using only two of the letters $\{{\sf1,2,3}\}$ ($\sf\{1,2\}$ for $xyzxy$ and $\sf\{2,3\}$ for $xyxzx$). Suppose that we have constructed such codewalks and proved the avoidability of $xyxzy$ and $xyxzx$ by square-free words. Then, we need to consider only those 6-letter patterns which do not contain avoidable 5-letter patterns as factors: $$ \begin{array}{ccccccc|cccccccc|ccccccc} x&y&x&z&y&z& & &x&y&z&x&z&y& & &x&y&z&y&x&z\\ 0&1&1&0& & & & & 1&1&0&1& & & & & 1&0&1&1& & \end{array} $$ By the same argument as for the 5-letter case, we conclude that the last two 6-letter patterns are unavoidable. The first one corresponds to $\sf 2$ in a codewalk, hence, if there exists a codewalk of an infinite square-free word using only the letters $\sf 1$ and $\sf 3$ then $xyxzyz$ is an avoidable letter pattern. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Summarizing the above considerations, we want to answer the following question: \emph{are there infinite square-free codewalks using only two of the letters} $\{{\sf1,2,3}\}$? It is easy to see that if such codewalks exist, they contain no cubes of one letter and no squares of the other letter according to Remark~\ref{pw}. (If the pair is $\{{\sf2,3}\}$, then the codewalk cannot contain the factor $\sf 22$ because it has no possible extensions leading to square-free words.) This property is exactly the property 4 of the Fibonacci words. What if we take the $\omega$-word ${\sf f}$ as a codewalk? %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section {Constructing square-free words from the Fibonacci words} Consider the codewalks obtained from Fibonacci words by three substitutions: %заменить на эквэйшены \begin{subequations}\label{subs} \begin{align} \sigma_{21}: a \rightarrow {\sf 2}, &\ b \rightarrow {\sf 1} \label{sub1}\\ \sigma_{31}: a \rightarrow {\sf 3}, &\ b \rightarrow {\sf 1}\label{sub2}\\ \sigma_{32}: a \rightarrow {\sf 3}, &\ b \rightarrow {\sf 2} \label{sub3} \end{align} \end{subequations} We call such codewalks {\it Fibonacci codewalks} and denote by $F_n$ [$\sf F$] the codewalk obtained from the word $f_n$ [resp., the $\omega$-word $\sf f$] under one of these substitutions. If we need to specify the substitution being applied we write $F_n^{ij}$ [$\sf F^{ij}$] for $\sigma_{ij}(f_n)$ [resp., $\sigma_{ij}({\sf f})$]. Let us have a look at ternary words $w^{21}, w^{31}, w^{32}$ decoded from Fibonacci codewalks ${\sf F^{21}}, {\sf F^{31}}, {\sf F^{32}}$ respectively. Suppose we always start decoding with $ab$. %$aba$. %\vspace{0.5cm} %\\ %$\sf f = abaababaabaababaababa\ldots$\\ %(1) $\sf F = 2122121221221212212121\ldots$\\ %$w = abacbcacbabcacbcabacabcbacabacbacbcacbabcbacabcbabcacbcabac\ldots$\\ %(2) $\sf F = 3133131331331313313131\ldots$\\ %$w = abacbabcbacbcabcbabcabacabcacbacabacbabcabacabcacbcabcbacbcacbacabacbabc\ldots$\\ %(3) $\sf F = 3233232332332323323232\ldots$\\ %$w=abacbabcacbacabcacabacbabcacbacabcacbabcabacbabcacbacabcbacbcabcbacabcacbabcabacb\ldots$ %\vspace{0.5cm} %\\ \begin{align*} &{\sf f }= abaababaabaab\ldots\\ (1)\ &\sf F^{21} = 2122121221221\ldots\\ &w^{21} = abacbcacbabcacbcabacabcbacabacbcabac\ldots\\ (2)\ &\sf F^{31} = 3133131331331\ldots\\ &w^{31} = abacbabcbacbcabcbabcabacabcacbacabacbabcabac\ldots\\ (3)\ &\sf F^{32} = 3233232332332323323232\ldots\\ &w^{32} = abacbabcacbacabcacbabcabacbcabcbacbcabacbabcabacb\ldots \end{align*} Combining the properties of Fibonacci words with Lemma~\ref{lcw} we will show that Fibonacci codewalks correspond to square-free words. The following lemma and the considerations from Section~\ref{s:lpc} together imply Theorem~\ref{mpt}. %\begin{remark}\label{rf} %Using the property~\ref{f2} we obtain the next sequence of equalities: %$$ %\begin{array}{l} %f_n = f_{n-1}f_{n-2} = \\ %f_{n-2}f_{n-3}f_{n-2} = \\ %f_{n-3}f_{n-4}f_{n-3}f_{n-3}f_{n-4} = \\ %f_{n-3}f_{n-4}f_{n-4}f_{n-5}f_{n-4}\ldots = \\ %f_{n-3}f_{n-4}f_{n-4}f_{n-5}f_{n-5}f_{n-6}\ldots =\\ %f_{n-3}f_{n-4}f_{n-4}f_{n-5}f_{n-6}f_{n-7}\ldots =\\ %f_{n-3}f_{n-4}f_{n-4}f_{n-4}f_{n-7} \ldots %\end{array} %$$ %Hence, for each $n$ a cube $f_nf_nf_n$ occurs in $\sf f$ and this cube is an image of a cube $f_{n-1}f_{n-1}f_{n-1}$. Note that Fibonacci words alternately end with $ab$ and $ba$; so the period $|f_n|$ can not be extended to the left. % %Now we prove the main result of this paper. \begin{lemma}\label{mt} Fibonacci codewalks decode to square-free words. \end{lemma} \begin{proof} In this proof, we show that Fibonacci codewalks ${\sf F^{ij}}$ satisfy the conditions (a) and (b) of Lemma~\ref{lcw} and hence they are decoded into square-free words. Using property~\ref{f4} of Fibonacci words we can easily see that Fibonacci codewalks do not contain forbidden factors from condition (a) of Lemma~\ref{lcw}. %11, 222, 223, 322, 333 Then we need to check that Fibonacci codewalks do not contain factors of the form $XYX$, where $XY$ labels a closed walk and $|Y|=2$. Let us consider periodic factors of Fibonacci $\omega$-word. The argument in the case where the period is a Fibonacci number is quite different from the argument in the other case; so we study these cases separately. {\it Case 1: Periods not equal to Fibonacci numbers}. %A cube $f_nf_nf_n$ occurs in Fibonacci $\omega$-word for any $n$( see Remark~\ref{rf}). Note that all cyclic shifts of $f_n$ are distinct. A folklore statement says that if a word $U$ is equal to its cyclic shift then $U=Z^k$ for some integer $k > 1$. Assume that $f_n = u^k$ for some word $u$. Then $f_{n+3}$ contains a factor of exponent $2k$, where $k \geq 4$, a contradiction with property~\ref{f6}. ** better add to the list of properties the well-known property that the shortest period of $f_n$ is $\Phi_{n-1} (>\Phi_n/2)$ ** % %Fibonacci $\omega$-word is a Sturmian word, hence among its $n+1$ factors of length $n$, where $n$ is Fibonacci number, there are $f_n$ and all its cyclic shifts and one more word $u$, furthermore Fibonacci $\omega$-word does not contain factor $uu$ ** why? **. Due to property~\ref{f7} we know that $\sf f$ does not contain periodic factors with exponent greater than $(2 + \rho)/2$ whose root is not a Fibonacci word. For $p$ big enough, $(2p - 2) / p > (2 + \rho)/2$, so we have no forbidden factors $XYX$, where $|XY|=p$. Let us check short periods $p$ such that $p$ is even, $(2p - 2) / p \le (2 + \rho)/2$ and $p$ is not a Fibonacci number. Such values of $p$ are 4, 6, and 10. Factors in $\sf f$ of these lengths corresponding to closed codewalks are $baab$, $abaaba$, $baabaa$, $aabaab$, $abaababaab$, $baababaaba$, $aababaabab$, $ababaababa$, $babaababaa$ (for all three encodings of $\sf f$ into codewalks). Let us check the words $XYX$ in each of these cases. It is obvious that $baabba$ is not a factor of $\sf f$. Consider the factor $abaaba$ and its cyclic shifts. If $XY=abaaba$ then $XYX = abaabaabaa$. But this is $\phi(ababab)a$ and $ababab=\phi(aaa)$, contradicting property~\ref{f4}. We conclude that such a factor does not exist in $f$. A similar analysis is applied to the other length 6 closed codewalks. Suppose $XY=abaababaab$. Then $abaababaab = (abaab)^2 = f_3^2$. Then $XYX=(abaab)^3aba$. This has period $5=\Phi_3$ and length 18 which is greater than ($|f_4| + 2|f_3| - 2=16$, contradicting property~\ref{f8}). The other listed factors of length 10 are conjugates of $f_3^2$, so the same observation is true for them. {\it Case 2: Periods equal to Fibonacci numbers}. We will show that the codewalk generated by $f_n$ is not closed for any $n$. Without loss of generality we will use substitution~\eqref{sub1}. Due to the symmetry in $K_{3,3}$, the same proof works in the two other cases. Consider a sequence $\{S_n\}$ of shortest codewalks (over $\{1,2\}$) such that $F_nS_n$ is a closed codewalk (see Fig.~\ref{k33}). We want to show that all codewalks $S_n$ are nonempty. Since $F_nS_{n-2}S_{n-1}=F_{n-1}F_{n-2}S_{n-2}S_{n-1}$ is a closed codewalk, the codewalk $S_n$ is obtained from $S_{n-2}S_{n-1}$ by deleting all maximal cycles.\\[1mm] $F_0 = {\sf2} \Rightarrow S_0 = {\sf2}$, \\ $F_1 = {\sf21} \Rightarrow S_1 = {\sf12}$, \\ $S_2 = {\sf212}$,\\ $S_3 = {\sf\cancel{1221}\,2} = {\sf2}$,\\ $S_4 = {\sf21\,\cancel{22}} = {\sf21}$,\\ $S_5 = {\sf\cancel{22}\,1 }= {\sf1}$,\\ $S_6 = {\sf2\,\cancel{11}} = {\sf2} = S_0$,\\ $S_7 = {\sf12} = S_1$,\\ $S_8 = {\sf212} = S_2$, $\ldots$. We see that $S_n$ is a periodic sequence with period 6 and all words $S_n$ are nonempty, implying that the codewalk generated by any Fibonacci word is not closed. Now note that any conjugate of a closed codewalk is closed (effectively, two such closed walks coincide up to the origin). Hence we conclude that the codewalks generated by all conjugates of Fibonacci words are not closed. Note also that if $F_nS_n$ is a closed walk then $F_nF_nS_nS_n$ is closed too, and $S_nS_n$ is closed if and only if $F_nF_n$ is closed. Looking at the sequence $S_n$, we conclude that $S_nS_n$ is closed for $n=6k, 2 + 6k, 3 + 6k, 5 + 6k, k \in \mathbb{N}_0$, where the lengths of the words $S_n$ are odd. Therefore, $F_nF_n$ generates a closed walk if and only if the length of $F_n$ is odd. %Taking into account the reasoning about cyclic shifts we conclude that a factor $F_nF_n$ of $\sf F$ can be a closed walk but does not contain factors from lemma~\ref{lcw}(b). It implies from the structure of the sequence $S_n$ that $F_nF_n$ is label of a closed walk if and only if the length of $F_n$ is odd. Assume that $\sf f$ contains a factor $XYX$ from Lemma~\ref{lcw}(b), where $XY$ is a cyclic shift of $f_nf_n$ for some $n$. Then the word $XYX$ has the period $\Phi_n$ and the length $<(2+\rho)\Phi_n$ by property~\ref{f6}. Then the length of $XYX$ is less than $(2|XY|-2)$ for all $n$ big enough. It is easy to check that $n=5$, and so $|XY|=2\Phi_5=26$, is sufficient. The smaller cases, which are $n=2$ and $n=3$, lead to the periods 6 and 10, considered above. %As we saw earlier, such factor starts with $f_nf_nf_n$. For $n = 5$ $|f_n| = 13$ and $|XYX| = 13 \cdot 4 - 2 = 50$, $\lexp(XYX) = 50/13 = 3\frac{11}{13} > 2 + \rho$, a contradiction with property~\ref{f6}. For smaller $n$ we have already checked the absence of such factors directly in the reasoning about periods 4, 6 and 10. %, where $XY = f_nf_n$ ($YX = f_nf_n$) for some $n$, and $XYX = f_nf_nf_nz (XYX = zf_nf_nf_n)$, where $z$ is $f_n$ without last two letters (first letters). It is obvious that suffixes of length 3 in all Fibonacci words are $aab$ or $aba$, and prefixes are equal to $aba$. Then the last (first) letter of $z$ is $a$. We know that $\sf f$ does not contain fourth powers. So after (before) $z$ in $\sf f$ must be $aa$ or $bb$, a contradiction with property (!). Thus, the lemma is proved. \end{proof} %Combining Theorem~\ref{mt} with the argument from section~\ref{s:lpc} we obtain the main result of this paper. %\begin{theorem} %The letter patterns $xyxzx$, $xyzxy$, and $xyxzyz$ are separately avoidable in ternary square-free words. %\end{theorem} \section{Exponents of square-free words avoiding 5 and 6-letter patterns} In this section we estimate the minimal exponents of ternary square-free words avoiding letter patterns $xyxzx$, $xyzxy$, and $xyxzyz$. By finding critical exponents of the constructed words $w^{ij}$ and obtaining some lower bounds, we prove the following \begin{theorem}\label{exp} The minimal critical exponent of a ternary square-free word avoiding a letter pattern of length $\le 6$ is:\\ (1) 15/8 for the pattern $xyxzx$; (2) 11/6 for the pattern $xyzxy$; and (3) at most $ 1+\rho/2$ for the pattern $xyxzyz$, where $\rho$ is the golden ratio. \end{theorem} \begin{remark}\label{rf} Using property~\ref{f2} we obtain the next sequence of equalities: $$ \begin{array}{l} f_n = f_{n-1}f_{n-2} = \\ f_{n-2}f_{n-3}f_{n-2} = \\ f_{n-3}f_{n-4}f_{n-3}f_{n-3}f_{n-4} = \\ f_{n-3}f_{n-4}f_{n-4}f_{n-5}f_{n-4} = \\ f_{n-3}f_{n-4}f_{n-4}f_{n-5}f_{n-5}f_{n-6} =\\ f_{n-3}f_{n-4}f_{n-4}f_{n-5}f_{n-6}f_{n-7} =\\ f_{n-3}f_{n-4}f_{n-4}f_{n-4}f_{n-7} \ldots \end{array} $$ Hence, for each $n \geq 2$ a cube $f_nf_nf_n$ occurs in $\sf f$ and for $n\geq 3$ this cube is a $\phi$-image of a cube $f_{n-1}f_{n-1}f_{n-1}$. Note that Fibonacci words alternately end with $ab$ and $ba$; so the period $|f_n|$ cannot be extended to the left. \end{remark} \begin{lemma}\label{we} One has $\lexp(w^{21})=11/6$, $\lexp(w^{31})=1+\rho/2$, $\lexp(w^{32})=15/8$. \end{lemma} \begin{proof} To compute the critical exponents of $w^{21}, w^{31}, w^{32}$ we need to consider two types of factors in $F$ decoded into periodic words:\\ (1) the factors of the form $XYX$, where $|XY| \geq 6$ and $XY$ is a label of closed walk (the case $|XY|=4$ is impossible, see the proof of Theorem~\ref{mt}; as we saw earlier, the maximal such factors of $\sf F$ have the form $F_nF_nF_nZ$, where $Z$ is a prefix of $F_n$);\\ (2) the factors decoded into words with periods less than 11 (see Remark~\ref{ms}). For convenience, we assume that codeword corresponding to any given codewalk begins with 0 and ends with 1. For example, the codewalk $\sf (121)^3$ corresponds to the codeword $(0101101)^3$. Then the length of the codeword always equals the length of the codewalk plus the sum of its digits. Recall that a codeword of length $n$ is decoded to a ternary word of length $n{+}2$. 1. Firstly, let us estimate exponents of words generated in $w^{ij}$ by the factors of type (1). The minimal period of the word $u$ decoded from $F_nF_nF_nZ$, where $F_nF_n$ is a closed walk, equals the length of the codeword corresponding to $F_nF_n$, which is $p = s + l$, where $s$ is the sum of digits in $F_nF_n$ and $l = |F_nF_n|$. The length of the word $u$ is the sum of digits of $F_nF_nF_nZ$ plus $|F_nF_nF_nZ|+2$. Further, the periodic factor in $w^{ij}$ with the period generated by $F_nF_n$ is several symbols longer that the word $u$ decoded from $F_nF_nF_nZ$. Consider ${\sf F}^{21}$. Assume that $F_nF_nF_nZ$ is preceded by 1. Since this 1 breaks the period $|F_n|$ (see Remark~\ref{rf}), this period would extend if we replace this 1 by 2. Hence, in terms of codewords, the period can be extended to the left by 011; since we have 01 instead, the period extends to the left just by one symbol in the codeword, and then, by one symbol in $w^{21}$. Note that exchanging the roles of 1 and 2 does not affect this result. Now consider the right extension: if the next symbol after $Z$ in the codewalk is 1 [2], then the codeword continues with 010 [resp., 011]. Hence, the period in the codeword extends by exactly two symbols to the right. In total, the periodic factor in $w^{21}$ with the period generated by $F_nF_n$ has the length equal to sum of digits of $F_nF_nF_nZ$ plus $|F_nF_nF_nZ|+5$. Exactly the same argument for the other two words give the same constant five for $w^{31}$ and the constant seven for $w^{32}$. Using property~\ref{f8}, we obtain $|F_nF_nF_nZ| \leq \Phi_{n+1} + 2\Phi_n - 2 = \Phi_n + \Phi_{n-1} + 2\Phi_n -2 = 3\Phi_n + \Phi_{n-1} - 2$, i.e., $Z$ is a prefix of $F_n$ of length $\le \Phi_{n-1} - 2$. The number of letters $a$ in $f_n$ is $\Phi_{n-1}$ and the number of letters $b$ is $\Phi_{n-2}$. Let $\alpha$ and $\beta$ denote images of $a$ and $b$ respectively under the substitution $\sigma_{ij}$. Remembering that the last two letters of any $f_n$ is $ab$ or $ba$, we can establish an upper bound for the local exponent of a periodic word $w$ generated in $w^{ij}$ by $F_nF_nF_nZ$: {\small \begin{eqnarray*} |w| \leq 3(\alpha\Phi_{n-1} + \beta\Phi_{n-2} + \Phi_n) + \alpha(\Phi_{n-2} - 1 ) + \beta(\Phi_{n-3} - 1 ) + (\Phi_{n-1} - 2) + m, \\ \text{ where } m = 5 \text{ for } w^{21}, w^{31}, m =7 \text{ for } w^{32},\\ \lexp(w) \leq \frac{3(\alpha\Phi_{n-1} + \beta\Phi_{n-2} + \Phi_n) + \alpha(\Phi_{n-2} - 1 ) + \beta(\Phi_{n-3} - 1 ) + (\Phi_{n-1} - 2) + m} {2(\alpha\Phi_{n-1} + \beta\Phi_{n-2} + \Phi_n)}\\ = \frac 32 +\frac{\alpha\Phi_{n-2} + \beta\Phi_{n-3} + \Phi_{n-1} - \alpha-\beta- 2 + m}{2(\alpha\Phi_{n-1} + \beta\Phi_{n-2} + \Phi_n)}\,. \end{eqnarray*}} For $\alpha = 2, \beta = 1$ one has $$ \lexp(w) \leq \frac 32 +\frac{2\Phi_{n-2} + \Phi_{n-3} + \Phi_{n-1}}{2(2\Phi_{n-1} + \Phi_{n-2} + \Phi_n)} = \frac 32 +\frac{\Phi_{n+1}}{2\Phi_{n+2}} = 1 + \frac{\Phi_{n+3}}{2\Phi_{n+2}}\,. $$ This bound tends to $1+\rho/2$ as $n$ approaches infinity and its maximum $29/16$ is reached when $n = 2$. For $\alpha = 3, \beta = 1$: $$ \lexp(w) \leq \frac 32 +\frac{3\Phi_{n-2} + \Phi_{n-3} + \Phi_{n-1}-1}{2(3\Phi_{n-1} + \Phi_{n-2} + \Phi_n)} = \frac 32 +\frac{2\Phi_n-1}{4\Phi_{n+1}} = 1 + \frac{\Phi_{n+2}-1/2}{2\Phi_{n+1}}\,. $$ This bound also tends to $1+\rho/2$ as $n$ approaches infinity. Using the explicit formula $$ \Phi_n= \frac 1{\sqrt{5}}\Big(\rho^n+(-1)^{n+1}\rho^{-n}\Big) $$ for Fibonacci numbers, it is easy to check that this bound is less than $1+\rho/2$ for all $n\ge 2$. Thus, this value can be approached arbitrarily close, but is never reached. For $\alpha = 3, \beta = 2$: $$ \lexp(w) \leq \frac 32 +\frac{3\Phi_{n-2} + 2\Phi_{n-3} + \Phi_{n-1}}{2(3\Phi_{n-1} + 2\Phi_{n-2} + \Phi_n)} = \frac 32 +\frac{\Phi_{n+1}+\Phi_{n-1}}{2(\Phi_{n+2}+\Phi_n)} = 1 + \frac{\Phi_{n+3}+\Phi_{n+1}}{2(\Phi_{n+2}+\Phi_n)}\,. $$ Again, the limit of this bound as $n\to \infty$ is $1+\rho/2$. The fraction behaves, up to the factor $1/2$, quite similar to the ratio between the $(n{+}1)$st and $n$th Fibonacci numbers: converges to $\rho$ and is alternately higher and lower than $\rho$. Its maximum $9/11$, giving us the upper bound $20/11$, is reached for $n=2$. 2. Now let us check short periodic factors directly. Due to Remark~\ref{ms}, it is sufficient to check the periods 6 and 8 only. \begin{enumerate} \item The Fibonacci codewalk $\sf F$ obtained by substitution~\eqref{sub1} contains the factor $\sf 1221$ decoded to the word $a\,bacabc\,bacab\,a$ of local exponent $11/6 > 29/16$. $w^{21}$ has no factors with period 8, because codewalks of such factors contain $\sf 33$. Hence, the local exponent of $w^{21}$ is $11/6$. \item The Fibonacci codewalk $\sf F$ obtained by substitution~\eqref{sub2} does not contain factors $\sf 1221$ and $\sf 2332$ decoded to words of local exponents greater than $1 + \rho/2$ with periods 6 and 8 respectively, hence, the local exponent of $w^{31}$ is $1+\rho/2$. Note that, unlike the two other cases, this value is unreachable. \item The Fibonacci codewalk $\sf F$ obtained by substitution~\eqref{sub3} contains the factor $\sf 2332$ decoded to word $a\,bacbcabc\,bacbcab\,a$ of local exponent equal to $15/8 > 20/11$. Hence, local exponent of $w^{32}$ is $15/8$. \end{enumerate} \end{proof} \begin{proof}[Proof of Theorem~\ref{exp}] (1) Every infinite ternary square-free word $w$ avoiding letter pattern $xyxzx$ have a factor with codewalk $\sf 2332$ due to Lemma~\ref{lcw}, hence $\lexp(w)\geq 15/8$, as we see in the proof of Lemma~\ref{we}. The word $w^{32}$ is the example proving that this value is precise.\\ (2) Replacing $\sf 2332$ with $\sf 1221$, $w^{32}$ with $w^{21}$ and $15/8$ with $11/6$ in the previous case we obtain the required result.\\ (3) The word $w^{31}$ avoids $xyxzyz$ and $\lexp(w^{31})\leq 1+\rho/2$. \end{proof} \section{Discussion} The exploration of letter pattern avoidance by ternary square-free words can be extended to larger lengths of patterns. It is easy to check that the only 7-letter pattern which does not contain avoidable letter patterns of smaller lengths as factors is $xyzxzyx$. Proving its avoidance will finalize the classification of letter patterns avoidable by ternary square-free words. This pattern has codeword $11011$. The codewalk of an infinite ternary word avoiding this pattern does not contain ${\sf22, 23, 32}$, and ${\sf 33}$ as factors, hence, after each ${\sf 2}$ and ${\sf 3}$ there must be a ${\sf 1}$. It is not clear whether such a codewalk can be constructed; but again, what we need is a binary sequence over the alphabet $\{{\sf 12, 13}\}$, so the approach similar to that used in this paper could work. %We can try to construct a square-free codewalk with such property in the following way. Again, we use the Fibonacci $\omega$-word and blocks of codewalks $b_2={\sf 1212}$ and $b_3={\sf 1313}$. We apply a special substitution $\sigma$ to each letter of $\sf f$: %$$ %\begin{array}{lclcrl} %\sigma({\sf f}[i]) & = & b_3 &\text{, if } & {\sf f}[i]=a, & i\text{ is odd},\\ %\sigma({\sf f}[i]) & = & b_3b_3 &\text{, if } & {\sf f}[i]=b, & i\text{ is odd},\\ %\sigma({\sf f}[i]) & = & b_2 &\text{, if } & {\sf f}[i]=a, & i\text{ is even},\\ %\sigma({\sf f}[i]) & = & b_2b_2 &\text{, if } & {\sf f}[i]=b, & i\text{ is even}. %\end{array} %$$ %$w^{21}, w^{31}, w^{32}$ have different local exponents and we consider them separately. %1. The word $w^{12}$\\ %Fibonacci codewalk $\sf F$ contains a factor $1221$ decoded to word $a\,bacabc\,bacab\,a$ of local exponent equal to $11/6$. Let us show that $\lexp(w^{12} = 11/6$, i.e. all the other factors of $\sf F$ are decoded to words of the same or lesser exponent. From the proof of Theorem~\ref{mt} we already know that periodic factors of bigger periods in $w^{12}$ are caused by periodic factors of the form $F_nF_nF_n$ in $\sf F$ \newcommand{\noopsort}[1]{} \newcommand{\singleletter}[1]{#1} \begin{thebibliography}{1} \providecommand{\url}[1]{\texttt{#1}} \providecommand{\urlprefix}{URL } \bibitem{Ars37} S. E. Arshon. Proof of the existence of asymmetric infinite sequences. \textit{Mat. Sbornik} 2: 769--779, 1937, in Russian, with French abstract. \bibitem{BaCr11} G. Badkobeh, M. Crochemore. Finite-repetition threshold for infinite ternary words. \textit{Proc. 8th Int. Conf. WORDS 2011, EPTCS} 63: 37--43, 2011. \bibitem{BaCrRa} G. Badkobeh, M. Crochemore, M. Rao: Finite-repetition threshold for large alphabets. \textit{RAIRO Inform. Th\'eor. Appl.} 48: 419-430, 2014. \bibitem{Cr82} M. Crochemore. Sharp characterizations of squarefree morphisms. \textit{Theor. Comp. Sci.} 18: 221--226, 1982. \bibitem{CuSa09} J. D. Currie, K. Saari. Least periods of factors of infinite words. \textit{RAIRO Inform. Th\'eor. Appl.} 43: 165--178, 2009. \bibitem{Dej72} F. Dejean. Sur un th\'eor\`eme de Thue. \textit{J. Combin. Theory. Ser. A} 13: 90--99, 1972. \bibitem{Kar83} J. Karhum\"aki. On cube-free $\omega$-words generated by binary morphisms. \textit{Discr. App. Math.} 5: 279--297, 1983. \bibitem{Lo83} M. Lothaire. Combinatorics on Words. Addison-Wesley, 1983. \bibitem{Lo02} M. Lothaire. Algebraic Combinatorics on Words. Cambridge University Press, 2002. \bibitem{MeShSa} R. Merca\c{s}, P. Ochem, A. Samsonov, A. Shur. Binary patterns in binary cube-free words: avoidability and growth. \textit{RAIRO Inform. Th\'eor. Appl.} 48: 369--389, 2014. \bibitem{MiPi92} F. Mignosi, G. Pirillo. Repetitions in the {Fibonacci} infinite word. \textit{RAIRO Inform. Th\'eor. App.} 26: 199--204, 1992. \bibitem{Pan84c} J. J. Pansiot. A propos d'une conjecture de {F. Dejean} sur les {r\'ep\'etitions} dans les mots. \textit{Discrete Appl. Math.} 7: 297--311, 1984. \bibitem{Pi97} G. Pirillo. Fibonacci numbers and words. \textit{Discrete Mathematics} 173: 197--207, 1997. \bibitem{RaSh05} N. Rampersad, J. Shallit, M. Wang. Avoiding large squares in infinite binary words. \textit{Theor. Comp. Sci.} 339: 19--34, 2005. \bibitem{Rao11} M. Rao. Last Cases of Dejean's Conjecture. \textit{Theor.Comp. Sci.} 412: 3010--3018, 2011. \bibitem{RiWl02} G. Richomme, F. Wlazinski. Some results on k-power-free morphisms. \textit{Theor. Comp. Sci.} 273: 119--142, 2002. \bibitem{Sh10jc} A. M. Shur. On ternary square-free circular words.\textit{ Electronic J. Combinatorics} 17(\# R140), 2010. \bibitem {Th06} A. Thue. \"Uber unendliche Zeichenreihen. \textit{Kra. Vidensk. Selsk. Skrifter. I. Mat.-Nat. Kl., Christiana}: 1--22, 1906. \bibitem {Th12} A. Thue. \"Uber die gegenseitige Lage gleicher Teile gewisser Zeichentreihen. \textit{Norske Vid. Selsk. Skr. I. Mat.-Nat. Kl., Christiana}: 1--67, 1912. \end{thebibliography} \end{document}