\documentclass[12pt]{article} \usepackage{e-jc} \usepackage{amsthm,amsmath,amssymb} \bibliographystyle{plainurl} \usepackage{url} \usepackage{enumerate} \usepackage{subcaption} \usepackage[utf8]{inputenc} \usepackage[ruled,vlined]{algorithm2e} \usepackage{xspace} \usepackage{xcolor} \usepackage{graphicx} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \usepackage{xargs} \usepackage[colorinlistoftodos,prependcaption,textsize=tiny]{todonotes} \def\abs#1{\left| #1 \right|} \def\paren#1{\left( #1 \right)} \def\acc#1{\left\{ #1 \right\}} \def\floor#1{\left\lfloor #1 \right\rfloor} \def\ceil#1{\left\lceil #1 \right\rceil} \def\cro#1{\left[ #1 \right]} \def\angle#1{\left\langle #1 \right\rangle} \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} \renewcommand{\le}{\leqslant} \renewcommand{\ge}{\geqslant} \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \title{Avoidability of formulas with two variables} \author{Pascal Ochem\footnote{LIRMM, CNRS, Universit\'e de Montpellier, France. ochem@lirmm.fr} and Matthieu Rosenfeld\footnote{LIP, ENS de Lyon, CNRS, UCBL, Universit\'e de Lyon, France. matthieu.rosenfeld@ens-lyon.fr}} \date{\dateline{October, 2017}{XX}\\ \small Mathematics Subject Classifications: 68R15} \setcounter{secnumdepth}{4} \begin{document} \maketitle \setcounter{footnote}{0} \begin{abstract} In combinatorics on words, a word $w$ over an alphabet $\Sigma$ is said to avoid a pattern $p$ over an alphabet $\Delta$ of variables if there is no factor $f$ of $w$ such that $f=h(p)$ where $h: \Delta^*\to\Sigma^*$ is a non-erasing morphism. A pattern $p$ is said to be $k$-avoidable if there exists an infinite word over a $k$-letter alphabet that avoids $p$. We consider the patterns such that at most two variables appear at least twice, or equivalently, the formulas with at most two variables. For each such formula, we determine whether it is $2$-avoidable, and if it is $2$-avoidable, we determine whether it is avoided by exponentially many binary words. \footnote{A previous version of this paper, without Theorem~\ref{second}, has been presented at DLT~2016.\\ %\textbf{Acknowledgements}: This work was partially supported by the ANR project CoCoGro (ANR-16-CE40-0005).} \bigskip\noindent \textbf{Keywords:} Word; Pattern avoidance. \end{abstract} \section{Introduction}\label{sec:intro} A \emph{pattern} $p$ is a non-empty finite word over an alphabet $\Delta=\acc{A,B,C,\dots}$ of capital letters called \emph{variables}. An \emph{occurrence} of $p$ in a word $w$ is a non-erasing morphism $h:\Delta^*\to\Sigma^*$ such that $h(p)$ is a factor of $w$. Let $\Sigma_k=\acc{0,1,\ldots,k-1}$ denote the $k$-letter alphabet. The \emph{avoidability index} $\lambda(p)$ of a pattern $p$ is the size of the smallest integer $k$ such that there exists an infinite word in $\Sigma_k^*$ containing no occurrence of $p$. Bean, Ehrenfeucht, and McNulty~\cite{BEM79} and Zimin~\cite{Zimin} characterized unavoidable patterns, i.e., such that $\lambda(p)=\infty$. We say that a pattern $p$ is \emph{$t$-avoidable} if $\lambda(p)\le t$. For more informations on pattern avoidability, we refer to Chapter 3 of Lothaire's book~\cite{Lothaire2002}. A variable that appears only once in a pattern is said to be \emph{isolated}. Following Cassaigne~\cite{Cassaigne1994}, we associate to a pattern $p$ the \emph{formula} $f$ obtained by replacing every isolated variable in $p$ by a dot. The factors between the dots are called \emph{fragments}. An \emph{occurrence} of $f$ in a word $w$ is a non-erasing morphism $h:\Delta^*\to\Sigma^*$ such that the $h$-image of every fragment of $f$ is a factor of $w$. As for patterns, the avoidability index $\lambda(f)$ of a formula $f$ is the size of the smallest alphabet allowing an infinite word containing no occurrence of $f$. Clearly, every word avoiding $f$ also avoids $p$, so $\lambda(p)\le\lambda(f)$. Recall that an infinite word is \emph{recurrent} if every finite factor appears infinitely many times. If there exists an infinite word over $\Sigma$ avoiding $p$, then there exists an infinite recurrent word over $\Sigma$ avoiding $p$. This recurrent word also avoids $f$, so that $\lambda(p)=\lambda(f)$. Without loss of generality, a formula is such that no variable is isolated and no fragment is a factor of another fragment. Cassaigne~\cite{Cassaigne1994} began and Ochem~\cite{Ochem2004} finished the determination of the avoidability index of every pattern with at most 3 variables. A \emph{doubled} pattern contains every variable at least twice. Thus, a doubled pattern is a formula with exactly one fragment. Every doubled pattern is 3-avoidable~\cite{O16}. A formula is said to be \emph{binary} if it has at most 2 variables. In this paper, we determine the avoidability index of every binary formula. We say that a formula $f$ is \emph{divisible} by a formula $f'$ if $f$ does not avoid $f'$, that is, there is a non-erasing morphism $h$ such that the image of any fragment of $f'$ by $h$ is a factor of a fragment of $f$. If $f$ is divisible by $f'$, then every word avoiding $f'$ also avoids $f$ and thus $\lambda(f)\le\lambda(f')$. Moreover, the reverse $f^R$ of a formula $f$ satisfies $\lambda(f^R)=\lambda(f)$. For example, the fact that $ABA.AABB$ is $2$-avoidable implies that $ABAABB$ and $BAB.AABB$ are $2$-avoidable. See Cassaigne~\cite{Cassaigne1994} and Clark~\cite{Clark} for more information on formulas and divisibility. For convenience, we say that an avoidable formula $f$ is \emph{exponential} (resp. \emph{polynomial}) if the number of words of length $n$ avoiding $f$ over $\lambda(f)$ letters is exponential (resp. polynomial) in~$n$. First, we check that every avoidable binary formula is 3-avoidable. Since $\lambda(AA)=3$, every formula containing a square is 3-avoidable. Then, the only square-free avoidable binary formula is $ABA.BAB$ with avoidability index 3~\cite{Cassaigne1994,circ}. Thus, we have to distinguish between avoidable binary formulas with avoidability index 2 and 3. A binary formula is minimally $2$-avoidable if it is $2$-avoidable and is not divisible by any other $2$-avoidable binary formula. A binary formula $f$ is maximally $2$-unavoidable if it is $2$-unavoidable and every other binary formula that is divisible by $f$ is $2$-avoidable. \begin{theorem}\label{main} Up to symmetry, the maximally $2$-unavoidable binary formulas are: {\small \begin{itemize} \item $AAB.ABA.ABB.BBA.BAB.BAA$ \item $AAB.ABBA$ \item $AAB.BBAB$ \item $AAB.BBAA$ \item $AAB.BABB$ \item $AAB.BABAA$ \item $ABA.ABBA$ \item $AABA.BAAB$ \end{itemize} } Up to symmetry, the minimally $2$-avoidable binary formulas are: \begin{itemize} {\small \item $AA.ABA.ABBA$ (polynomial) \item $ABA.AABB$ (polynomial) \item $AABA.ABB.BBA$ (polynomial) \item $AA.ABA.BABB$ (exponential) \item $AA.ABB.BBAB$ (exponential) \item $AA.ABAB.BB$ (exponential) \item $AA.ABBA.BAB$ (exponential) \item $AAB.ABB.BBAA$ (exponential) \item $AAB.ABBA.BAA$ (exponential) \item $AABB.ABBA$ (exponential) \item $ABAB.BABA$ (exponential) \item $AABA.BABA$ (exponential) \item $AAA$ (exponential) \item $ABA.BAAB.BAB$ (exponential) \item $AABA.ABAA.BAB$ (exponential) \item $AABA.ABAA.BAAB$ (exponential) \item $ABAAB$ (exponential) } \end{itemize} \end{theorem} Given a binary formula $f$, we can use Theorem~\ref{main} to find $\lambda(f)$. Now, we also consider the problem whether an avoidable binary formula is polynomial or exponential. If $\lambda(f)=3$, then either $f$ contains a square and is thus exponential, or $f=ABA.BAB$. We will see in Section~\ref{sec:aba.bab} that $ABA.BAB$ is exponential too. Thus, we consider only the case $\lambda(f)=2$. If $f$ is divisible by an exponential $2$-avoidable formula given in Theorem~\ref{main}, then $f$ is known to be exponential. This leaves open the case such that $f$ is only divisible by polynomial $2$-avoidable formulas. The next result settles every open case. \begin{theorem}\label{second}{\ } The following formulas are polynomial: {\small \begin{itemize} \item $BBA.ABA.AABB$ \item $AABA.AABB$ \end{itemize} } The following formulas are exponential: \begin{itemize} {\small \item $BAB.ABA.AABB$ \item $AAB.ABA.ABBA$ \item $BAA.ABA.AABB$ \item $BBA.AABA.AABB$ } \end{itemize} \end{theorem} \subsection{Structure of the proofs} First, we check by computer that Theorem~\ref{main} is exhaustive, that is, for every avoidable binary formula $f$, either $f$ or $f^R$ divides at least one formula in the first list and thus $f$ is $2$-unavoidable, or $f$ or $f^R$ is divisible by at least one formula in the second list and thus $f$ is $2$-avoidable. Every binary pattern of length $6$ (or its reverse) is divisible by at least one formula in the second list. So we only need to consider formulas such that the length of every fragment is at most $5$. Then, to obtain the $2$-unavoidability of the formulas in the first part of Theorem~\ref{main}, we use a standard backtracking algorithm. Figure~\ref{tabularunavoidable} gives the maximal length and number of binary words avoiding each maximally $2$-unavoidable formula. \begin{figure}[htbp] { \small \begin{tabular}{|c|c|c|} \hline & Maximal length of a & Number of binary\\ Formula & binary word avoiding & words avoiding\\ & this formula & this formula\\ \hline $AAB.BBAA$& 22 & 1428\\ \hline $AAB.ABA.ABB.BBA.BAB.BAA$& 23 & 810\\ \hline $AAB.BBAB$& 23 & 1662\\ \hline $AABA.BAAB$& 26 & 2124\\ \hline $AAB.ABBA$& 30 & 1684\\ \hline $AAB.BABAA$&42 & 71002\\ \hline $AAB.BABB$& 69 & 9252\\ \hline $ABA.ABBA$ & 90 & 31572 \\ \hline \end{tabular} } \caption{The number and maximal length of binary words avoiding the maximally $2$-unavoidable formulas.} \label{tabularunavoidable} \end{figure} There remain to show that the formulas in the second part of Theorem~\ref{main} are $2$-avoidable. These formulas, together with the formulas in Theorem~\ref{second}, characterize the frontier between polynomial and exponential $2$-avoidable binary formulas. The proof for polynomial formulas is in Section~\ref{sec:poly}. It uses a technical lemma given in Section~\ref{sec:lemma}. The proof for exponential formulas is in Section~\ref{sec:exp}. Similarly, a computer check shows that for every $2$-avoidable binary formula $f$, either $f$ or $f^R$ corresponds to one of the $5$ polynomial formulas in Lemma~\ref{lem:poly}, or $f$ or $f^R$ is divisible by at least one exponential formula appearing in Section~\ref{sec:exp}. \section{The useful lemma}\label{sec:lemma} Let us define the following words: \begin{itemize} \item$b_2$ is the fixed point of $\texttt{0}\mapsto\texttt{01}$, $\texttt{1}\mapsto\texttt{10}$. \item$b_3$ is the fixed point of $\texttt{0}\mapsto\texttt{012}$, $\texttt{1}\mapsto\texttt{02}$, $\texttt{2}\mapsto\texttt{1}$. \item$b_4$ is the fixed point of $\texttt{0}\mapsto\texttt{01}$, $\texttt{1}\mapsto\texttt{03}$, $\texttt{2}\mapsto\texttt{21}$, $\texttt{3}\mapsto\texttt{23}$. \item$b_5$ is the fixed point of $\texttt{0}\mapsto\texttt{01}$, $\texttt{1}\mapsto\texttt{23}$, $\texttt{2}\mapsto\texttt{4}$, $\texttt{3}\mapsto\texttt{21}$, $\texttt{4}\mapsto\texttt{0}$. \end{itemize} Let $w$ and $w'$ be infinite (right infinite or bi-infinite) words. We say that $w$ and $w'$ are equivalent if they have the same set of finite factors. We write $w\sim w'$ if $w$ and $w'$ are equivalent. Given an alphabet $\Sigma$ and a set $S$ of forbidden structures, we say that a finite set $W$ of infinite words over $\Sigma$ \emph{essentially avoids} $S$ if every word in $W$ avoids $S$ and every bi-infinite word over $\Sigma$ avoiding $S$ is equivalent to one of the words in $W$. If $W$ contains only one word $w$, we denote the set $W$ by $w$ instead of $\acc{w}$. A famous result of Thue can then be stated as follows: \begin{theorem}[\cite{Berstel:1995,Thue06}] \label{thm:thue} $b_3$ essentially avoids \texttt{010}, \texttt{212}, and squares. \end{theorem} The results in the next section involve $b_3$. We have tried without success to prove them by using Theorem~\ref{thm:thue}. We need the following stronger property of $b_3$: \begin{lemma} \label{lm} $b_3$ essentially avoids \texttt{010}, \texttt{212}, $XX$ with $1\le|X|\le3$, and $\texttt{2}YY$ with $|Y|\ge4$. \end{lemma} \begin{proof} We start by checking by computer that $b_3$ has the same set of factors of length exactly $100$ as every bi-infinite ternary word avoiding \texttt{010}, \texttt{212}, $XX$ with $1\le|X|\le3$, and $\texttt{2}YY$ with $|Y|\ge4$. We will use the set $F=\acc{\texttt{00},\texttt{11},\texttt{22},\texttt{010},\texttt{212},\texttt{0202},\texttt{2020},\texttt{1021},\texttt{1201}}$ of ternary words of length at most $4$ that are not factors of $b_3$. To finish the proof, we use Theorem~\ref{thm:thue} and we suppose for contradiction that $w$ is a bi-infinite ternary word that contains a large square $MM$ and avoids both $F$ and large factors of the form $\texttt{2}YY$. \begin{itemize} \item Case $M=\texttt{0}N$. Then $w$ contains $MM=\texttt{0}N\texttt{0}N$. Since $\texttt{00}\in F$ and $\texttt{2}YY$ is forbidden, $w$ contains $\texttt{10}N\texttt{0}N$. Since $\acc{\texttt{11},\texttt{010}}\subset F$, $w$ contains $\texttt{210}N\texttt{0}N$. If $N=P\texttt{1}$, then $w$ contains $\texttt{210}P\texttt{10}P\texttt{1}$, which contains $\texttt{2}YY$ with $Y=10P$. So $N=P\texttt{2}$ and $w$ contains $\texttt{210}P\texttt{20}P\texttt{2}$. If $P=Q\texttt{1}$, then $w$ contains $\texttt{210}Q\texttt{120}Q\texttt{12}$. Since $\acc{\texttt{11},\texttt{212}}\subset F$, the factor $Q\texttt{12}$ implies that $Q=R\texttt{0}$ and $w$ contains $\texttt{210}R\texttt{0120}R\texttt{012}$. Moreover, since $\acc{\texttt{00},\texttt{1201}}\subset F$, the factor $\texttt{120}R$ implies that $R=\texttt{2}T$ and $w$ contains $\texttt{2102}T\texttt{01202}T\texttt{012}$. Then there is no possible prefix letter for $S$: \texttt{0} gives \texttt{2020}, \texttt{1} gives \texttt{1021}, and \texttt{2} gives \texttt{22}. This rules out the case $P=Q\texttt{1}$. So $P=Q\texttt{0}$ and $w$ contains $\texttt{210}Q\texttt{020}Q\texttt{02}$. The factor $Q\texttt{020}Q$ implies that $Q=1R1$, so that $w$ contains $\texttt{2101}R\texttt{10201}R\texttt{102}$. Since $\acc{\texttt{11},\texttt{010}}\subset F$, the factor $\texttt{01}R$ implies that $R=\texttt{2}T$, so that $w$ contains $\texttt{21012}T\texttt{102012}T\texttt{102}$. The only possible right extension with respect to $F$ of \texttt{102} is \texttt{102012}. So $w$ contains $\texttt{21012}T\texttt{102012}T\texttt{102012}$, which contains $\texttt{2}YY$ with $Y=T\texttt{102012}$. \item Case $M=\texttt{1}N$. Then $w$ contains $MM=\texttt{1}N\texttt{1}N$. In order to avoid $\texttt{11}$ and $\texttt{2}YY$, $w$ must contain $\texttt{01}N\texttt{1}N$. If $N=P\texttt{0}$, then $w$ contains $\texttt{01}P\texttt{01}P\texttt{0}$. So $w$ contains the large square $\texttt{01}P\texttt{01}P$ and this case is covered by the previous case. So $N=P\texttt{2}$ and $w$ contains $\texttt{01}P\texttt{21}P\texttt{2}$. Then there is no possible prefix letter for $P$: \texttt{0} gives \texttt{010}, \texttt{1} gives \texttt{11}, and \texttt{2} gives \texttt{212}. \item Case $M=\texttt{2}N$. Then $w$ contains $MM=2N2N$. If $N=P\texttt{1}$, then $w$ contains $\texttt{2}P\texttt{12}P\texttt{1}$. This factor cannot extend to $\texttt{2}P\texttt{12}P\texttt{12}$, since this is $\texttt{2}YY$ with $Y=P\texttt{12}$. So $w$ contains $\texttt{2}P\texttt{12}P\texttt{10}$. Then there is no possible suffix letter for $P$: \texttt{0} gives \texttt{010}, \texttt{1} gives \texttt{11}, and \texttt{2} gives \texttt{212}. This rules out the case $N=P\texttt{1}$. So $N=P\texttt{0}$ and $w$ contains $\texttt{2}P\texttt{02}P\texttt{0}$. This factor cannot extend to $\texttt{02}P\texttt{02}P\texttt{0}$, since this contains the large square $\texttt{02}P\texttt{02}P$ and this case is covered by the first case. Thus $w$ contains $\texttt{12}P\texttt{02}P\texttt{0}$. If $P=Q\texttt{1}$, then $w$ contains $\texttt{12}Q\texttt{102}Q\texttt{10}$. Since $\acc{\texttt{22},\texttt{1021}}\subset F$, the factor $\texttt{102}Q$ implies that $Q=\texttt{0}R$, so that $w$ contains $\texttt{120}R\texttt{1020}R\texttt{10}$. Then there is no possible prefix letter for $R$: \texttt{0} gives \texttt{00}, \texttt{1} gives \texttt{1201}, and \texttt{2} gives \texttt{0202}. This rules out the case $P=Q\texttt{1}$. So $P=Q\texttt{2}$ and $w$ contains $\texttt{12}Q\texttt{202}Q\texttt{20}$. The factor $Q\texttt{202}$ implies that $Q=R1$ and $w$ contains $\texttt{12}R\texttt{1202}R\texttt{120}$. Since $\acc{\texttt{00},\texttt{1201}}\subset F$, $w$ contains $\texttt{12}R\texttt{1202}R\texttt{1202}$, which contains $\texttt{2}YY$ with $Y=R\texttt{1202}$. \end{itemize} \end{proof} \section{Polynomial formulas}\label{sec:poly} Let us detail the binary words avoiding the polynomial formulas in Theorems~\ref{main} and~\ref{second}. Lemma~\ref{lem:poly} will show that they are images of $b_3$ by the morphisms $g_x$, $g_y$, $g_z$, and $g_t$ defined as follows. \noindent \begin{minipage}{0.21\linewidth} $$\begin{array}{l} g_x(\texttt{0})=\texttt{01110},\\ g_x(\texttt{1})=\texttt{0110},\\ g_x(\texttt{2})=\texttt{0}.\\ \end{array}$$ \end{minipage} \begin{minipage}{0.21\linewidth} $$\begin{array}{l} g_y(\texttt{0})=\texttt{0111},\\ g_y(\texttt{1})=\texttt{01},\\ g_y(\texttt{2})=\texttt{00}.\\ \end{array}$$ \end{minipage} \begin{minipage}{0.21\linewidth} $$\begin{array}{l} g_z(\texttt{0})=\texttt{0001},\\ g_z(\texttt{1})=\texttt{001},\\ g_z(\texttt{2})=\texttt{11}.\\ \end{array}$$ \end{minipage} \begin{minipage}{0.37\linewidth} $$\begin{array}{l} g_t(\texttt{0})=\texttt{01011011010},\\ g_t(\texttt{1})=\texttt{01011010},\\ g_t(\texttt{2})=\texttt{010}.\\ \end{array}$$ \end{minipage} \\ Let $\overline{w}$ denote the word obtained from the binary word $w$ by exchanging \texttt{0} and \texttt{1}. Obviously, if $w$ avoids a given formula, then so does $\overline{w}$. An infinite or b-infinite binary word $w$ is \emph{self-complementary} if $w\sim\overline{w}$. The words $g_x(b_3)$, $g_y(b_3)$, and $g_t(b_3)$ are self-complementary. Since the frequency of \texttt{0} in $g_z(b_3)$ is $\tfrac59$, $g_z(b_3)$ is not self-complementary. Then $g_{\overline{z}}$ is obtained from $g_z$ by exchanging \texttt{0} and \texttt{1}, so that $g_{\overline{z}}(b_3)=\overline{g_z(b_3)}$. The aim of this section is to prove the following result. \begin{lemma}\label{lem:poly}{\ } \begin{itemize} \item $\acc{g_x(b_3), g_y(b_3), g_z(b_3), g_{\overline{z}}(b_3)}$ essentially avoids $AA.ABA.ABBA$. \item $g_x(b_3)$ essentially avoids $AABA.ABB.BBA$. \item Let $f$ be either $ABA.AABB$, $BBA.ABA.AABB$, or $AABA.AABB$.\\ Then $\acc{g_x(b_3), g_t(b_3)}$ essentially avoids $f$. \end{itemize} \end{lemma} Let us first state interesting properties of the morphisms and the formulas in Lemma~\ref{lem:poly}. \begin{lemma}\label{lem:occ} For every $p,s\in\Sigma_3$, $Y\in\Sigma_3^*$ with $|Y|\ge4$, and $g\in\acc{g_x,g_y,g_z,g_{\overline{z}},g_t}$, the word $g(p2YYs)$ contains an occurrence of $AABA.AABBA$. \end{lemma} \begin{proof}{\ } \begin{itemize} \item Since \texttt{0} is a prefix and a suffix of the $g_x$-image of every letter, $g_x(p\texttt{2}YYs)=V\texttt{000}U\texttt{00}U\texttt{00}W$ contains an occurrence of $AABA.AABBA$ with $A=\texttt{0}$ and $B=\texttt{0}U\texttt{0}$. \item Since \texttt{0} is a prefix of the $g_y$-image of every letter, $g_y(\texttt{2}YYs)=\texttt{000}U\texttt{0}U\texttt{0}V$ contains an occurrence of $AABA.AABBA$ with $A=\texttt{0}$ and $B=\texttt{0}U$. \item Since \texttt{1} is a suffix of the $g_z$-image of every letter, $g_z(p\texttt{2}YY)=V\texttt{111}U\texttt{1}U\texttt{1}$ contains an occurrence of $AABA.AABBA$ with $A=\texttt{1}$ and $B=\texttt{1}U$. \item Since $g_{\overline{z}}(p\texttt{2}YY)=\overline{g_z(p\texttt{2}YY)}$, $g_{\overline{z}}(p\texttt{2}YY)$ contains an occurrence of $AABA.AABBA$. \item Since \texttt{010} is a prefix and a suffix of the $g_t$-image of every letter, $g_t(p\texttt{2}YYs)=V\texttt{010010010}U\texttt{010010}U\texttt{010010}W$ contains an occurrence of $AABA.AABBA$ with $A=\texttt{010}$ and $B=\texttt{010}U\texttt{010}$. \end{itemize} \end{proof} The following observation explains why $AABA.AABBA$ is considered in Lemma~\ref{lem:occ}. \begin{observation}\label{rem} $AABA.AABBA$ is divisible by every formula in Lemma~\ref{lem:poly}. \end{observation} We are now ready to prove Lemma~\ref{lem:poly}. To prove the avoidability, we have implemented Cassaigne's algorithm that decides, under mild assumptions, whether a morphic word avoids a formula~\cite{Cassaigne1994}. We have to explain how the long enough binary words avoiding a formula can be split into 4 or 2 distinct incompatible types. A similar phenomenon has been described for $AABB.ABBA$~\cite{aabbc}. First, consider any infinite binary word $w$ avoiding $AA.ABA.ABBA$. A computer check shows by backtracking that $w$ must contain the factor \texttt{01110001110}. In particular, $w$ contains \texttt{00}. Thus, $w$ cannot contain both \texttt{010} and \texttt{0110}, since it would produce an occurrence of $AA.ABA.ABBA$. Moreover, a computer check shows by backtracking that $w$ cannot avoid both \texttt{010} and \texttt{0110}. So, $w$ must contain either \texttt{010} or \texttt{0110} (this is an exclusive or). By symmetry, $w$ must contain either \texttt{101} or \texttt{1001}. There are thus at most $4$ possibilities for $w$, depending on which subset of $\acc{\texttt{010},\texttt{0110},\texttt{101},\texttt{1001}}$ appears among the factors of $w$, see Figure~\ref{fig4}. \begin{figure}[htbp] \centering \includegraphics[width=4.8cm]{type4} \caption{The four infinite binary words avoiding $AA.ABA.ABBA$.} \label{fig4} \end{figure} Also, consider any infinite binary word $w$ avoiding $f$, where $f$ is either $ABA.AABB$, $BBA.ABA.AABB$, or $AABA.AABB$. Notice that the formulas $BBA.ABA.AABB$ and $AABA.AABB$ are divisible by $ABA.AABB$. We check by backtracking that $w$ cannot avoid both \texttt{0010} and \texttt{00110}. A word containing both \texttt{0010} and \texttt{00110} contains an occurrence of $AABA.AABBA$, and by Observation~\ref{rem}, it also contains an occurrence of $f$. So $w$ does not contain both \texttt{0010} and \texttt{00110}. Thus, there are two possibilities for $w$ depending on whether it contains \texttt{0010} or \texttt{00110}. Now our tasks of the form "prove that a set of morphic words essentially avoids one formula" are reduced to (more) tasks of the form "prove that one morphic word essentially avoids one formula and a finite set of factors". Since all the proofs of such reduced tasks are very similar, we only detail the proof that $g_y(b_3)$ essentially avoids $AA.ABA.ABBA$, \texttt{0110}, and \texttt{1001}. We check that the set of prolongable binary words of length $100$ avoiding $AA.ABA.ABBA$, \texttt{0110}, and \texttt{1001} is exactly the set of factors of length $100$ of $g_y(b_3)$. Using Cassaigne's notion of circular morphism~\cite{Cassaigne1994}, this is sufficient to prove that every bi-infinite binary word of this type is the $g_y$-image of some bi-infinite ternary word $w_3$. It also ensures that $w_3$ and $b_3$ have the same set of small factors. Suppose for contradiction that $w_3\not\sim b_3$. By Lemma~\ref{lm}, $w_3$ contains a factor $\texttt{2}YY$ with $|Y|\ge4$. Since $w_3$ is bi-infinite, $w_3$ even contains a factor $p\texttt{2}YYs$ with $p,s\in\Sigma_3$. By Lemma~\ref{lem:occ}, $g_y(w_3)$ contains an occurrence of $AABA.AABBA$. Then by Observation~\ref{rem}, $g_y(w_3)$ contains an occurrence of $AA.ABA.ABBA$. This contradiction shows that $w_3\sim b_3$. So $g_y(b_3)$ essentially avoids $AA.ABA.ABBA$, \texttt{0110}, and \texttt{1001}. \section{Exponential formulas}\label{sec:exp} Given a morphism $g:\Sigma^*_3\to\Sigma^*_2$, an sqf-$g$-image is the image by $g$ of a (finite or infinite) ternary square-free word. With an abuse of language, we say that $g$ avoids a set of formulas if every sqf-$g$-image avoids every formula in the set. For every $2$-avoidable exponential formula $f$ in Theorems~\ref{main} and~\ref{second}, we give below a uniform morphism $g$ that avoids $f$. If possible, we simultaneously avoid the reverse formula $f^R$ of $f$. We also avoid large squares. Let $SQ_t$ denote the pattern corresponding to squares of period at least $t$, that is, $SQ_1=AA$, $SQ_2=ABAB$, $SQ_3=ABCABC$, and so on. The morphism $g$ avoids $SQ_t$ with $t$ as small as possible. Since $\lambda(SQ_2)=3$, a binary word avoiding $SQ_3$ is necessarily best possible in terms of length of avoided squares. \begin{itemize} \item $f=AA.ABA.BABB$. This $22$-uniform morphism avoids $\acc{f,f^R,SQ_6}$: {\small $$ \begin{array}{c} \texttt{0}\mapsto\texttt{0001101101110011100011}\\ \texttt{1}\mapsto\texttt{0001101101110001100011}\\ \texttt{2}\mapsto\texttt{0001101101100011100111}\\ \end{array} $$ } This $44$-uniform morphism avoids $\acc{f,SQ_5}$: {\small $$ \begin{array}{c} \texttt{0}\mapsto\texttt{00010010011000111001001100010011100100100111}\\ \texttt{1}\mapsto\texttt{00010010011000100111001001100011100100100111}\\ \texttt{2}\mapsto\texttt{00010010011000100111001001001100011100100111}\\ \end{array} $$ } Notice that $\acc{f,f^R,SQ_5}$ is $2$-unavoidable and $\acc{f,SQ_4}$ is $2$-unavoidable. \item $f=AA.ABB.BBAB$. This $60$-uniform morphism avoids $\acc{f,f^R,SQ_{11}}$: {\small $$ \begin{array}{c} \texttt{0}\mapsto\texttt{000110011100011001110011000111000110011100011100110001110011}\\ \texttt{1}\mapsto\texttt{000110011100011001110001110011000111000110011100110001110011}\\ \texttt{2}\mapsto\texttt{000110011100011001110001100111000111001100011100110001110011}\\ \end{array} $$ } Notice that $\acc{f,SQ_{10}}$ is $2$-unavoidable. \item $f=AA.ABAB.BB$ is self-reverse. This $11$-uniform morphism avoids $\acc{f,SQ_4}$: {\small $$ \begin{array}{c} \texttt{0}\mapsto\texttt{00100110111}\\ \texttt{1}\mapsto\texttt{00100110001}\\ \texttt{2}\mapsto\texttt{00100011011}\\ \end{array} $$ } Notice that $\acc{f,SQ_3}$ is $2$-unavoidable. \item $f=AA.ABBA.BAB$ is self-reverse. This $30$-uniform morphism avoids $\acc{f,SQ_6}$: {\small $$ \begin{array}{c} \texttt{0}\mapsto\texttt{000110001110011000110011100111}\\ \texttt{1}\mapsto\texttt{000110001100111001100011100111}\\ \texttt{2}\mapsto\texttt{000110001100011001110011100111}\\ \end{array} $$ } Notice that $\acc{f,SQ_5}$ is $2$-unavoidable. \item $f=AAB.ABB.BBAA$ is self-reverse. This $30$-uniform morphism avoids $\acc{f,SQ_5}$: {\small $$ \begin{array}{c} \texttt{0}\mapsto\texttt{000100101110100010110111011101}\\ \texttt{1}\mapsto\texttt{000100101101110100010111011101}\\ \texttt{2}\mapsto\texttt{000100010001011101110111010001}\\ \end{array} $$ } Notice that $\acc{f,SQ_4}$ is $2$-unavoidable. \item $f=AAB.ABBA.BAA$ is self-reverse. This $38$-uniform morphism avoids $\acc{f,SQ_5}$: {\small $$ \begin{array}{c} \texttt{0}\mapsto\texttt{00010001000101110111010001011100011101}\\ \texttt{1}\mapsto\texttt{00010001000101110100011100010111011101}\\ \texttt{2}\mapsto\texttt{00010001000101110001110100010111011101}\\ \end{array} $$ } Notice that $\acc{f,SQ_4}$ is $2$-unavoidable. \item $f=AABB.ABBA$. This $193$-uniform morphism avoids $\acc{f,SQ_{16}}$: {\small $$ \begin{array}{ll} \texttt{0}\mapsto &\texttt{0001000101101110110001011011100010110111011100010}\\ &\texttt{1100010001011011101100010110111011100010110111011}\\ &\texttt{0001011011100010110111011100010110001000101101110}\\ &\texttt{0010110111011100010110111011000101101110001011}\\ \texttt{1}\mapsto&\texttt{0001000101101110110001011011100010110111011100010}\\ &\texttt{1100010001011011100010110111011100010110111011000}\\ &\texttt{1011011100010110111011100010110001000101101110110}\\ &\texttt{0010110111011100010110111011000101101110001011}\\ \texttt{2}\mapsto&\texttt{0001000101101110001011011101110001011000100010110}\\ &\texttt{1110110001011011101110001011011101100010110111000}\\ &\texttt{1011011101110001011000100010110111011000101101110}\\ &\texttt{0010110111011100010110111011000101101110001011}\\ \end{array} $$ } Notice that $\acc{f,f^R}$ is $2$-unavoidable and $\acc{f,SQ_{15}}$ is $2$-unavoidable. Previous papers~\cite{Ochem2004,aabbc} have considered a $102$-uniform morphism to avoid $\acc{f,SQ_{27}}$. \item $f=ABAB.BABA$ is self-reverse. This $50$-uniform morphism avoids $\acc{f,SQ_3}$, see~\cite{Ochem2004}: {\small $$ \begin{array}{c} \texttt{0}\mapsto\texttt{00011001011000111001011001110001011100101100010111}\\ \texttt{1}\mapsto\texttt{00011001011000101110010110011100010110001110010111}\\ \texttt{2}\mapsto\texttt{00011001011000101110010110001110010111000101100111}\\ \end{array} $$ } Notice that a binary word avoiding $\acc{f,SQ_3}$ contains only the squares \texttt{00}, \texttt{11}, and \texttt{0101} (or \texttt{00}, \texttt{11}, and \texttt{1010}). \item $f=AABA.BABA$: A case analysis of the small factors shows that a recurrent binary word avoids $\acc{f,f^R,SQ_3}$ if and only if it contains only the squares \texttt{00}, \texttt{11}, and \texttt{0101} (or \texttt{00}, \texttt{11}, and \texttt{1010}). Thus, the previous $50$-uniform morphism that avoids $\acc{ABAB.BABA,SQ_3}$ also avoids $\acc{f,f^R,SQ_3}$. \item $f=AAA$ is self-reverse. This $32$-uniform morphism avoids $\acc{f,SQ_4}$: {\small $$ \begin{array}{c} \texttt{0}\mapsto\texttt{00101001101101001011001001101011}\\ \texttt{1}\mapsto\texttt{00101001101100101101001001101011}\\ \texttt{2}\mapsto\texttt{00100101101001001101101001011011}\\ \end{array} $$ } Notice that $\acc{f,SQ_3}$ is $2$-unavoidable. \item $f=ABA.BAAB.BAB$ is self-reverse. This $10$-uniform morphism avoids $\acc{f,SQ_3}$: {\small $$ \begin{array}{c} \texttt{0}\mapsto\texttt{0001110101}\\ \texttt{1}\mapsto\texttt{0001011101}\\ \texttt{2}\mapsto\texttt{0001010111}\\ \end{array} $$ } \item $f=AABA.ABAA.BAB$ is self-reverse. This $57$-uniform morphism avoids $\acc{f,SQ_6}$: {\small $$ \begin{array}{c} \texttt{0}\mapsto\texttt{000101011100010110010101100010111001011000101011100101011}\\ \texttt{1}\mapsto\texttt{000101011100010110010101100010101110010110001011100101011}\\ \texttt{2}\mapsto\texttt{000101011100010110010101100010101110010101100010111001011}\\ \end{array} $$ } Notice that $\acc{f,SQ_5}$ is $2$-unavoidable. \item $f=AABA.ABAA.BAAB$ is self-reverse. This $30$-uniform morphism avoids $\acc{f,SQ_3}$: {\small $$ \begin{array}{c} \texttt{0}\mapsto\texttt{000101110001110101000101011101}\\ \texttt{1}\mapsto\texttt{000101110001110100010101110101}\\ \texttt{2}\mapsto\texttt{000101110001010111010100011101}\\ \end{array} $$ } \item $f=ABAAB$. This $10$-uniform morphism avoids $\acc{f,f^R,SQ_3}$, see~\cite{Ochem2004}: {\small $$ \begin{array}{c} \texttt{0}\mapsto\texttt{0001110101}\\ \texttt{1}\mapsto\texttt{0000111101}\\ \texttt{2}\mapsto\texttt{0000101111}\\ \end{array} $$ } \item $f=BAB.ABA.AABB$ is self-reverse. This $16$-uniform morphism avoids $\acc{f,SQ_5}$: {\small $$ \begin{array}{c} \texttt{0}\mapsto\texttt{0101110111011101}\\ \texttt{1}\mapsto\texttt{0100010111010001}\\ \texttt{2}\mapsto\texttt{0001010111010100}\\ \end{array} $$ } Notice that $\acc{f,SQ_4}$ is $2$-unavoidable. \item $f=AAB.ABA.ABBA$ is avoided with its reverse. This $84$-uniform morphism avoids $\acc{f,f^R,SQ_5}$: {\small $$ \begin{array}{ll} \texttt{0}\mapsto&\texttt{000100010111000111010001000101110111010001}\\ &\texttt{011100011101000101110111010001110001011101}\\ \texttt{1}\mapsto&\texttt{000100010111000111010001000101110100011100}\\ &\texttt{010111011101000101110001110100010111011101}\\ \texttt{2}\mapsto&\texttt{000100010111000111010001000101110100011100}\\ &\texttt{010111010001000101110001110100010111011101}\\ \end{array} $$ } Notice that $\acc{f,SQ_4}$ is $2$-unavoidable. \item $f=BAA.ABA.AABB$. This $304$-uniform morphism avoids $\acc{f,SQ_7}$: {\small $$ \begin{array}{ll} \texttt{0}\mapsto&\texttt{0001100011001110001110011000110011100111001100011000110011100}\\ &\texttt{1100011100011001110011100110001100111000111001100011000110011}\\ &\texttt{1001100011100011001110011100110001100011001110001110011000110}\\ &\texttt{0111001110011000111000110011100110001100011001110011100110001}\\ &\texttt{100111000111001100011000110011100111001100011100011001110011}\\ \texttt{1}\mapsto&\texttt{0001100011001110001110011000110011100111001100011000110011100}\\ &\texttt{1100011100011001110011100110001100111000111001100011000110011}\\ &\texttt{1001100011100011001110011100110001100011001110001110011000110}\\ &\texttt{0111001110011000110001100111001100011100011001110011100110001}\\ &\texttt{100111000111001100011000110011100111001100011100011001110011}\\ \texttt{2}\mapsto&\texttt{0001100011001110001110011000110011100111001100011000110011100}\\ &\texttt{1100011100011001110011100110001100011001110001110011000110011}\\ &\texttt{1001110011000111000110011100110001100011001110011100110001100}\\ &\texttt{1110001110011000110001100111001100011100011001110011100110001}\\ &\texttt{100011001110001110011000110011100111001100011100011001110011}\\ \end{array} $$ } Using the morphism $g_w$ below and the technique in~\cite{BO15}, we can show that $g_w(b_3)$ essentially avoids $\acc{f,SQ_6}$: {\small $$ \begin{array}{l} g_w(\texttt{0})=\texttt{011100111001110001100111001100011000110}\\ g_w(\texttt{1})=\texttt{011100111001100011000110}\\ g_w(\texttt{2})=\texttt{001110011000110}\\ \end{array} $$ } Notice that $\acc{f,f^R}$ is $2$-unavoidable and $\acc{f,SQ_5}$ is $2$-unavoidable. \item $f=BBA.AABA.AABB$. This $160$-uniform morphism avoids $\acc{f,f^R,SQ_{21}}$: {\small $$ \begin{array}{ll} \texttt{0}\mapsto&\texttt{000101100101110001011100101100010111000101100101110010}\\ &\texttt{110001011100101100010110010111001011000101110001011001}\\ &\texttt{0111000101110010110001011001011100101100010111001011}\\ \texttt{1}\mapsto&\texttt{000101100101110001011100101100010111000101100101110010}\\ &\texttt{110001011100101100010110010111000101100101110010110001}\\ &\texttt{0111000101110010110001011001011100101100010111001011}\\ \texttt{2}\mapsto&\texttt{000101100101110001011001011100101100010111000101100101}\\ &\texttt{110001011100101100010110010111001011000101110001011100}\\ &\texttt{1011000101100101110001011001011100101100010111001011}\\ \end{array} $$ } This $202$-uniform morphism avoids $\acc{f,SQ_5}$: {\small $$ \begin{array}{ll} \texttt{0}\mapsto&\texttt{000110100111011010001101010001110110100110110101000}\\ &\texttt{111011010001101010001110110101000110100111011010011}\\ &\texttt{011010100011010011101101010001110110100011010100011}\\ &\texttt{1011010100011010011101101010001110110100110110101}\\ \texttt{1}\mapsto&\texttt{000110100111011010001101010001110110100110110101000}\\ &\texttt{110100111011010100011101101000110101000111011010100}\\ &\texttt{011010011101101010001110110100110110101000110100111}\\ &\texttt{0110100110110101000111011010001101010001110110101}\\ \texttt{2}\mapsto&\texttt{000110100111011010001101010001110110100110110101000}\\ &\texttt{110100111011010100011101101000110101000111011010100}\\ &\texttt{011010011101101001101101010001110110100011010100011}\\ &\texttt{1011010100011010011101101010001110110100110110101}\\ \end{array} $$ } Notice that $\acc{f,f^R,SQ_{20}}$ is $2$-unavoidable and $\acc{f,SQ_4}$ is $2$-unavoidable. \end{itemize} We start by checking that every morphism is synchronizing, that is, for every letters $a,b,c\in\Sigma_3$, the factor $g(a)$ only appears as a prefix or a suffix in $g(bc)$. For every $q$-uniform morphism $g$, the sqf-$g$-images are claimed to avoid $SQ_t$ with $2t