\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
%\usepackage{graphicx}
\usepackage{amscd}
\usepackage[dvips]{graphicx}
\usepackage[all]{xy}
\usepackage{epsfig}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf
On the Unavoidability of $k$-Abelian Squares in \\
\vskip .1in
Pure Morphic Words
}
\vskip 1cm
\large
Mari Huova and Juhani Karhum\"aki\footnote{
Supported by the Academy of Finland under grant 121419.}
\\
Department of Mathematics and Statistics \\
TUCS \\
University of Turku \\ 20014 Turku \\
Finland \\
\href{mailto:mari.huova@utu.fi}{\tt mari.huova@utu.fi}\\
\href{mailto:karhumak@utu.fi}{\tt karhumak@utu.fi}
\end{center}
\vskip .2 in
\begin{abstract}
We consider a recently defined notion of \textit{$k$-abelian
equivalence} of words by concentrating on avoidability problems. The
equivalence class of a word depends on the number of occurrences of
different factors of length $k$ for a fixed natural number $k$ and the
prefix of the word. We show that over a ternary alphabet, $k$-abelian
squares cannot be avoided in pure morphic words for any natural number
$k$. Nevertheless, computational experiments support the conjecture
that even $3$-abelian squares can be avoided over a ternary alphabet.
This illustrates that the simple but widely used method to produce
infinite words by iterating a single morphism is not powerful enough
with $k$-abelian avoidability questions.
\end{abstract}
\section{Introduction}
The theory of avoidability is one of the oldest and most studied topics
in combinatorics on words. The first results were obtained by Axel Thue
already at the beginning of the 20th century \cite{Thue1,Thue2}. He
showed, among other things, the existence of an infinite binary word
that does not contain any factor three times consecutively, i.e.,
that avoids cubes (\seqnum{A010060}).
Similarly, Thue showed that squares can be
avoided in infinite ternary words.
Since the late 1960's \textit{abelian}, i.e., commutative variants of
the above problems were studied. The first nontrivial
results were obtained by Evdokimov \cite{Evdok}, who showed that
commutative squares can be avoided in infinite words over a 25-letter
alphabet. The size of the alphabet was reduced to five by Pleasant
\cite{Pleas}, until the optimal value, four, was found by Ker\"anen
\cite{Ker}. Dekking \cite{Dek} had already
managed to prove that the optimal value for the size of the alphabet on
which abelian cubes are avoidable is three.
In this paper we concentrate on a new variant of the square-freeness by
defining repetitions via equivalence relations which lie properly in
between equality and abelian equality. For this relation we use the
notion of \textit{$k$-abelian equivalence}, where $k\geq 1$ is a
natural number. We have computational results that support the
conjecture of the existence of an infinite ternary 3-abelian
square-free word. On the other hand, we will show that an infinite
ternary $k$-abelian square-free word cannot be obtained by iterating a
morphism for any $k \geq 1$. This illustrates the intricacy of our
concept, and hints that a simple iteration of a morphism alone
might not be a
useful method in search for avoidability results on $k$-abelian
repetitions. Whether the use of a combination of morphisms, e.g.,
more general morphic words, might work here remains unknown.
As is clarified
in the next section there exist other cases where the avoidability can
be established, but not in pure morphic words.
\section{Preliminaries}
For basic terminology of words, as well as avoidability,
we refer to \cite{Lo1,CK}.
The basic notion in this paper, \textit{$k$-abelian equivalence} of
words, is defined as follows.
\begin{definition}\label{pref}
Let $k \geq 1$ be a natural number and $\Sigma$ an alphabet. We say that words $u$ and $v$ in $\Sigma^{+}$ are \textit{$k$-abelian equivalent}, in symbols $u \equiv_{a,k} v$, if
\begin{enumerate}
\item $\textrm{pref}_{k-1} \left( u \right) = \textrm{pref}_{k-1} \left( v \right)$ and $\textrm{suf}_{k-1} \left( u \right) = \textrm{suf}_{k-1} \left( v \right)$,
\item for all $w \in \Sigma^{k}$, the number of occurrences of $w$ in $u$ and $v$ coincide, i.e., $|u |_{w} = |v |_{w}$, and
\item different words of length at most $k-1$ are inequivalent.
\end{enumerate}
\end{definition}
Here $\textrm{pref}_{k-1}$ (resp., $\textrm{suf}_{k-1}$) is used to denote the prefix (resp., suffix) of length $k-1$. It is easy to see that $\equiv_{a,k}$ is an equivalence relation and the first condition makes the notion a sharpening of abelian equality and even a congruence. In fact, it is enough to require the words to have either a common prefix of length $k-1$ or a common suffix of length $k-1$.
Another definition for $k$-abelian equivalent words with length at least $k$ is the following:
\begin{definition} \label{factors}
Let $k \geq 1$ be a natural number and $\Sigma$ an alphabet. Words $u$ and $v$ in $\Sigma^{+}$ are $k$-abelian equivalent if for all $w \in \Sigma^{k-1} \cup \Sigma^{k}$, the number of occurrences of $w$ in $u$ and $v$ coincide, i.e., $|u |_{w} = |v |_{w}$.
\end{definition}
It is easy to see that the definitions \ref{pref} and \ref{factors}
yields the same equivalence. The condition of Definition \ref{factors}
follows directly from Definition \ref{pref}. In addition, $|u |_{w} =
|v |_{w}$ for all $w \in \Sigma^{k}$ is required in both definitions.
To prove the rest we may assume to the contrary that for words $u,v \in
\Sigma^{+}$ the condition of second definition holds but
$\textrm{pref}_{k-1} \left( u \right) = x \neq \textrm{pref}_{k-1}
\left( v \right)$. Let $|u |_{x} = r$ so $|v |_{x} = r$ and $\sum_{a
\in \Sigma}(|u |_{ax}) = r-1$. Now from $\textrm{pref}_{k-1} \left( v
\right) \neq x$ and $|v |_{x} = r$ follows that $\sum_{a \in \Sigma}(|u
|_{ax}) = r$ giving a contradiction.
Now, notions like \textit{$k$-abelian repetitions} are naturally
defined. For instance, $w = uv$ is a \textit{$k$-abelian square} if and
only if $u \equiv_{a,k} v$. We have the following simple observation:
\begin{lemma} \emph{\cite{HK}} \label{smaller}
If an infinite word $w$ contains a $k$-abelian $m$-power then $w$ contains a $k'$-abelian $m$-power for each $1 \leq k' \leq k$.
\end{lemma}
For some earlier results about $k$-abelian equivalence we refer to
\cite{HKSS, HKS, KSZ}. We have shown with Saarela and Saari \cite{HKSS}
that the longest ternary word avoiding 2-abelian squares has 537
letters. In addition, we have the following result \cite{HK}
concerning such prefix-preserving morphisms over an alphabet $\Sigma$
that they map each letter to a word of length at least two:
\begin{theorem} \emph{\cite{HK}} \label{repetition}
Let $h$ be a morphism over $\Sigma$ such that $\min\left\{ |h(a)| : a \in \Sigma \right\} > 1$. Then the following two conditions are equivalent:
\begin{enumerate}
\item The infinite word $h^{\infty }(a)$ contains a $k$-abelian $m$-power for some $k \geq 2$.
\item The infinite word $h^{\infty }(a)$ contains a $k$-abelian $m$-power for each $k \geq 1$.
\end{enumerate}
\end{theorem}
\emph{A prefix-preserving} (or \emph{prolongable}) \emph{morphism} is a
morphism $h: \Sigma^{*} \rightarrow \Sigma^{*}$ for which there exists
a letter $a \in \Sigma$ and a word $\alpha \in \Sigma^{*}$ such that
$h(a) = a \alpha$ and $h^{n}(\alpha) \neq \epsilon$ for every $n \geq
0$. We call an infinite word \emph{a pure morphic word} if it is
obtained by iterating a prefix-preserving morphism. \emph{A morphic
word} is obtained from a pure morphic word by taking an image of it by
a morphism or equivalently under a coding, see \cite{AS}.
We remark that Theorem \ref{repetition} also holds in the case where the
prefix-preserving morphism $h$ over $\Sigma$ has the following property:
\begin{equation} \label{image}
\forall a\in\Sigma \; \exists n > 0 : |h^{n}(a)| > 1.
\end{equation}
Theorem \ref{repetition} can be extended in this way because if (\ref{image}) holds we can choose $n' > 0$ such that $\min\left\{ |h^{n'}(a)| : a \in \Sigma \right\} > 1$ and we can consider the morphism $\hat{h} = h^{n'}$. If $a \in \Sigma$ is a letter for which $h$ is prolongable then $\hat{h}^{\infty }(a) = h^{\infty }(a)$. Let us denote by $H$ the set of prefix-preserving morphisms having the property (\ref{image}).
Thue already showed that there exists an infinite pure morphic
square-free word over ternary alphabet, see \cite{Thue2}. The question
whether pure morphic words can avoid $k$-abelian squares over ternary
alphabets is reasonable because we have a strong evidence that an
infinite ternary 3-abelian square-free word might exist.
\begin{example}
By producing in a lexicographic order longer and longer 3-abelian
square-free ternary words we have obtained words containing more than
100,000 letters. The number of ordinary ternary square-free words of
length $n$ is listed as a sequence (\seqnum{A006156}) and in our case
the numbers of 3-abelian square-free words over a ternary alphabet
seems to grow exponentially, at least for small values of $n$, see
figure \ref{pic}. These computer based analyzes suggest that there
might exist an infinite 3-abelian square-free word over a ternary
alphabet.
\end{example}
\begin{figure}[h]
\begin{center}
\epsfig{file=number80.eps}
\caption{The numbers of 3-abelian square-free words of length $n$.}\label{pic}
\end{center}
\end{figure}
In contrary, each infinite word over a three-letter alphabet contains 2-abelian squares, see \cite{HKSS}, so it follows from Theorem \ref{repetition} that, for each $h \in H$ over a ternary alphabet, $h^{\infty }(a)$ contains a $k$-abelian square for all $k \geq 1$. In this paper we will show that, a bit surprisingly, we cannot obtain an infinite ternary $k$-abelian square-free word, for any $k \geq 1$, by simply iterating any prefix-preserving morphism.
Although, iterated morphisms constitute a common tool in avoidability questions, in the ordinary word case there also exist patterns that can be avoided in binary words, but not in words produced by only iterating a morphism. Cassaigne gave a classification of binary patterns according to avoidability in binary words, in binary pure morphic words and in ternary pure morphic words, \cite{Ca}. The patterns $\alpha^{2}\beta^{2}\alpha, \; \alpha\beta\alpha^{2}\beta$ and $\alpha\beta\alpha^{2}\beta\alpha$ are such that they can be avoided over a binary alphabet, but not in infinite binary pure morphic words. Similarly, it seems that 3-abelian squares can be avoided over a ternary alphabet but not in infinite ternary pure morphic words. A related well known example is given by the famous (cube-free) Kolakoski word (\seqnum{A000002}): it is not pure morphic \cite{CKL},
but it is unknown whether it is morphic. Indeed, it is not known
whether its subword complexity is quadratic, as would be in the case of
a morphic word. On the other hand Currie has conjectured (see \cite{Cu}
and \cite[Problem 3.1.5, p.\ 132]{Lo2}), that if a pattern $p$ is
avoidable on alphabet $A$, there exist an alphabet $B$, two morphisms
$f: B^{*} \rightarrow A^{*}$ and $g: B^{*} \rightarrow B^{*} $ and a
letter $a \in B$ such that the infinite word $f(g^{\infty}(a))$ avoids
$p$, that is, $p$ is avoidable in morphic words. Based on our results
and intuition we do not dare to make a related conjecture for
$k$-abelian repetitions, even in the case where the pattern is an
integer power.
Rather little is known about avoiding $k$-abelian repetitions in
general or even in morphic words. Results in \cite{HKS} and \cite{MS}
are examples of the case where the $k$-abelian cube-freeness over a
binary alphabet is obtained in morphic words. The results cover the
cases $k \geq 5$.
\section{Unavoidability of 3-abelian squares in pure morphic words}
In this section we consider $k$-abelian square-freeness and nonerasing morphisms that do not belong to the set $H$. We start by stating few lemmas and conclude our avoidability result for the case $k=3$ from these lemmas. Let $h$ be such a prefix-preserving morphism over $\Sigma = \left\{a,b,c\right\}$ that is prolongable for $a$ and let $h^{\infty }(a) = w$. If $w$ is $k$-abelian square-free then at least one letter has to map to a letter as a consequence of Theorem \ref{repetition}. On the other hand, Lemma \ref{onlyone} shows that at most one letter may map to a letter. We continue by remarking that an infinite ternary $k$-abelian square-free word, in fact a word avoiding ordinary word squares, has to contain each possible factor of length two except $aa, bb$ and $cc$.
\begin{lemma} \label{factor}
Each word of length $\geq 14$ over an alphabet $\left\{a,b,c\right\}$ contains a square if some of the factors $ab, \; ac, \; ba, \; bc, \; ca \textrm{ or } cb$ do not belong to the set of the factors of $w$, i.e., to the set $F(w)$.
\end{lemma}
\begin{proof}
Assume that $ab \notin F(w)$. The other cases are symmetric. It is easy to check that $bcbacbcacbaca$ is the longest word avoiding $ab$ and squares.
\end{proof}
By using Lemma \ref{factor} we may prove the following:
\begin{lemma} \label{onlyone}
Consider the morphism
\begin{equation*}
h: \begin{cases}
a \mapsto a\alpha \\
b \mapsto \beta \\
c \mapsto \gamma
\end{cases}, \textrm{ where } \alpha \in \Sigma^{+} \textrm{ and } \beta, \gamma \in \Sigma.
\end{equation*}
Now $h^{\infty }(a) = w$ contains a square.
\end{lemma}
\begin{proof}
If $h(b) = a$ then $h(ba) = aa\alpha$ and by Lemma \ref{factor} $ba$ as well as $h(ba)$ are factors of $w$. Similarly, the case $h(c) = a$ gives a square.
If $h(b) = b = h(c)$ then the image of the factor $bc$ gives a square $h(bc) = bb$ and by Lemma \ref{factor} $bc, h(bc) \in F(w)$. The case $h(b) = c = h(c)$ is similar.
Now there are two cases left. First, if $h(b) = c$ and $h(c) = b$ then $h^{2}(b) = b$ and $h^{2}(c) = c$ so without loss of generality it is enough to consider the case $h(b) = b$ and $h(c) = c$. If $a^{-1}h(a) \in \left\{b,c\right\}^{+}$ then $a^{-1}h^{\infty}(a) \in \left\{b,c\right\}^{\omega}$ and the binary infinite word cannot be square-free. Thus we have to check if $h(a) = a\alpha_{1} a \alpha_{2}$, where $\alpha_{1} \in \left\{b,c\right\}^{+}$ and $\alpha_{2} \in \left\{a,b,c\right\}^{*}$. Now
$$a \stackrel{h}{\mapsto} a\alpha_{1} a \alpha_{2} \stackrel{h}{\mapsto} a\alpha_{1} a \alpha_{2} \alpha_{1} a\alpha_{1} a \alpha_{2} h(\alpha_{2}),$$
because $h(\alpha_{1}) = \alpha_{1}$ and thus $h^{2}(a)$ contains a square $\alpha_{1} a\alpha_{1} a$. This completes the proof.
\end{proof}
Thus, if there exists a morphism $h$ over a three-letter alphabet
$\Sigma$ that generates an infinite $k$-abelian square-free word it
maps exactly one letter to a letter and, in fact, it has to map the
letter to itself. Otherwise $|h^{2}(a)| > 1$ for all $a \in \Sigma$.
Without loss of generality, we may assume that $h(b) = b$. By Lemma
\ref{factor} we may consider the images of all the factors of length
two except $aa, bb$ and $cc$ to further restrict the form of the
morphism.
\begin{lemma} \label{two}
If $h$ is a prefix-preserving morphism over the alphabet $\Sigma = \left\{a,b,c\right\}$ that generates an infinite $k$-abelian square-free word, it has to be one of the following forms to avoid usual word squares:
\begin{displaymath}
\left. \begin{array}{llll}
h: \left\{ \begin{array}{l}
a \mapsto a\alpha a \\
b \mapsto b \\
c \mapsto c\gamma c\\
\end{array} \right.
&
\textrm{or}
&
h: \left\{ \begin{array}{l}
a \mapsto a\alpha c \\
b \mapsto b \\
c \mapsto a\gamma c\\
\end{array} \right. ,
&
\textrm{where } \alpha, \gamma \in \Sigma^{+}.
\end{array} \right.
\end{displaymath}
\end{lemma}
\begin{proof}
We already have that
\begin{equation*}
h: \begin{cases}
a \mapsto a\alpha' \\
b \mapsto b \\
c \mapsto \gamma'
\end{cases}, \textrm{ where } \alpha', \gamma' \in \Sigma^{+} \textrm{ and } |\gamma'| \geq 2.
\end{equation*}
Thus $h(ab) = a\alpha' b$, from which it follows that $b$ cannot be a suffix of $\alpha'$. From $h(cb) = \gamma' b$ and $h(ca) = \gamma' a \alpha'$ it follows that $c$ has to be a suffix of $\gamma'$. In addition, $b$ cannot be a prefix of $\gamma'$ because $h(bc) = b \gamma'$. Now we have that $h(a) = a\alpha a$ or $h(a) = a\alpha c$ and $h(c) = a\gamma c$ or $h(c) = c\gamma c$, where $\alpha, \gamma \in \Sigma^{*}$. By considering $h(ac)$ we conclude that
\begin{displaymath}
\left. \begin{array}{llll}
h: \left\{ \begin{array}{l}
a \mapsto a\alpha a \\
b \mapsto b \\
c \mapsto c\gamma c\\
\end{array} \right.
&
\textrm{or}
&
h: \left\{ \begin{array}{l}
a \mapsto a\alpha c \\
b \mapsto b \\
c \mapsto a\gamma c\\
\end{array} \right. ,
&
\textrm{where } \alpha, \gamma \in \Sigma^{*}.
\end{array} \right.
\end{displaymath}
If $\alpha = \epsilon$ (and similarly for $\gamma$) then $h(a) = aa$ or $h(a) = ac$, and both cases lead to a square. In the latter case, $ca \mapsto a\gamma cac \mapsto ach(\gamma)a \gamma c ac a \gamma c$. Thus neither $\alpha$ nor $\gamma$ can be the empty word, which completes the proof.
\end{proof}
Next we restrict our consderation to $k$-abelian square-freeness with $k = 3$.
\begin{lemma} \label{2to3}
Consider the morphism
\begin{displaymath}
h: \left\{ \begin{array}{l}
a \mapsto a\alpha c \\
b \mapsto b \\
c \mapsto a\gamma c\\
\end{array} \right. , \textrm{ where } \alpha, \gamma \in \Sigma^{+}.
\end{displaymath}
Now $h^{\infty}(a)$ has 3-abelian square.
\end{lemma}
\begin{proof}
Let $h^{\infty}(a) = w$, and let us assume that it is square-free. As mentioned, each infinite ternary word contains a 2-abelian square. In particular,
$u_{1}u_{2} \in F(w)$ where $u_{1}$ and $u_{2}$ are 2-abelian equivalent. We have that $u_{1} \neq u_{2}$ and thus $|u_{1}| > 3$. Each factor of length three of the word $h(u_{1})$ (resp., for $h(u_{2})$) is a factor of $h(x_{1}x_{2}x_{3})$, where $x_{1}x_{2}x_{3}$ is a factor of $u_{1}$ and $x_{1}, x_{2}, x_{3} \in \Sigma$. In fact, the only case where the image of two consecutive letters is not enough is the case where $x_{2} = b$ and we take the factor $\textrm{suf}_{1}(h(x_{1})) h(x_{2}) \textrm{pref}_{1}(h(x_{3})) = cba$. Thus the factors of length three of the word $h(u_{1})$ are determined by the factors of length two of the word $u_{1}$ and the number of factors $x_{1}bx_{3}$ in $u_{1}$ where $x_{1}, x_{3} \in \left\{ a,c \right\}$. Because $u_{1}$ and $u_{2}$ are 2-abelian equivalent, the words $h(u_{1})$ and $h(u_{2})$ have the same occurrences of the factors of length three.
In addition, if $\textrm{pref}_{1}(u_{1}) = b$ then $\textrm{pref}_{2}(h(u_{1})) = ba$ because $bb$ cannot be a prefix of $u_{1}$ and in other cases $|h(\textrm{pref}_{1}(u_{1}))| \geq 3$. Because $\textrm{pref}_{1}(u_{1}) = \textrm{pref}_{1}(u_{2})$ we have that $\textrm{pref}_{2}(h(u_{1})) = \textrm{pref}_{2}(h(u_{2}))$. Correspondingly, $\textrm{suf}_{2}(h(u_{1})) = \textrm{suf}_{2}(h(u_{2}))$. Now $h(u_{1}u_{2}) \in F(w)$ and $h(u_{1})$ and $h(u_{2})$ are 3-abelian equivalent.
\end{proof}
From the previous lemmas we have that if there exists a prefix-preserving morphism over a three-letter alphabet generating an infinite 3-abelian square-free word, it has to be of the following form:
\begin{displaymath}
h: \left\{ \begin{array}{l}
a \mapsto a\alpha a \\
b \mapsto b \\
c \mapsto c\gamma c\\
\end{array} \right. , \textrm{ where } \alpha, \gamma \in \Sigma^{+}.
\end{displaymath}
With the following three lemmas we will show that the morphism above
always leads to a word containing 3-abelian square. For the lemmas
\ref{both}, \ref{other} and \ref{either} let us denote $h^{\infty}(a) =
w$.
\begin{lemma}\label{both}
If $aba, cbc \in F(w)$ then $w$ contains a square.
\end{lemma}
\begin{proof}
Here $h(aba) = a \alpha aba \alpha a$ and $h(cbc) = c \gamma cbc \gamma c$. This means that the only nontrivial case is $h(a) = a \alpha' ca$ and $h(c) = ca \gamma' c$ where $\alpha', \gamma' \in \Sigma^{*}$. Now $h(ac) = a \alpha' ca ca \gamma' c$ gives a square $caca$.
\end{proof}
Thus we may restrict the word $w$ not to contain the factor $aba$ or $cbc$. These cases are symmetric and it is enough to discuss the other one.
\begin{lemma}\label{other}
If $aba \in F(w)$ and $cbc \notin F(w)$ then $w$ contains a square.
\end{lemma}
\begin{proof}
Now $h(aba) = a \alpha aba \alpha a$. By avoiding trivial squares this gives $h(a) = aca$ or $h(a) = ac \alpha_{1} ca$ where $\alpha_{1} \in \Sigma^{+}$. If $h(a) = aca$ then $h(ac) = acac\gamma c$ gives a square $acac$. Thus $h(ac) = ac \alpha_{1} ca c\gamma c$ and we may conclude that $h(a) = ac \alpha_{2} bca$ and $h(c) = cb\gamma_{1}c$ where $\alpha_{2}, \gamma_{1} \in \Sigma^{*}$. The cases $h(a) = acbca $ and $h(c) = cbc$ are not possible because $cbc \notin F(w)$. Further, $h(ca)$ gives $h(a) = acb \alpha_{3} bca$ and $h(c) = cb\gamma_{2}bc$ where $\alpha_{3}, \gamma_{2} \in \Sigma^{+}$. The assumption $cbc \notin F(w)$ also gives that $h(a) = acba \alpha_{4} bca$ where $\alpha_{4} \in \Sigma^{*}$. Now $cba \in F(h(a)) \subset F(w)$ and $h(cba) = cb \gamma_{2} bc b acba \alpha_{4} bca$ which contains the square $cbacba$.
\end{proof}
Now we know that $w$ cannot have either $aba$ or $cbc$ as a factor.
\begin{lemma}\label{either}
If $aba, cbc \notin F(w)$ then $w$ contains a 3-abelian square.
\end{lemma}
\begin{proof}
By \cite{Thue1, Thue2, Bers}, the only infinite pure morphic square-free word over a ternary alphabet avoiding $aba$ and $cbc$ is obtained by iterating a morphism
\begin{displaymath}
g: \left\{ \begin{array}{l}
a \mapsto abc \\
b \mapsto ac \\
c \mapsto b\\
\end{array} \right. .
\end{displaymath}
Now $g \in H$ and thus $g^{\infty}(a)$ contains a 3-abelian square. In fact, already $g^{5}(a)$ contains a 3-abelian square: $g^{5}(a) = ab\underbrace{cacbabcbacab}_{} \underbrace{cacbacabcbab}_{} \ldots \ .$
\end{proof}
Now consider
an erasing morphism (the one with $c \mapsto \epsilon$ behaves similarly)
\begin{displaymath}
e: \left\{ \begin{array}{l}
a \mapsto a\alpha \\
b \mapsto \epsilon \\
c \mapsto \gamma\\
\end{array} \right. .
\end{displaymath}
The word $e^{\infty}(a)$ cannot contain $aba$ as well as $cbc$ because $e(aba)= a\alpha a\alpha$ and $e(cbc)= \gamma \gamma$. Thus this case returns to the proof of Lemma \ref{either} and, in fact, the same argument can be used for general $k$-abelian case, too.
Now we are ready to state the first part of the main result.
\begin{theorem}\label{3-abelian}
Every ternary infinite pure morphic word contains a 3-abelian square.
\end{theorem}
\begin{proof}
The proof is clear from the lemmas above. With Lemmas \ref{onlyone},
\ref{two}, and \ref{2to3} we have restricted the form of the morphism
that could produce an infinite ternary 3-abelian square-free word and
with Lemmas \ref{both}, \ref{other}, and \ref{either} we have shown that
the word obtained by iterating that type of morphism always contains a
3-abelian square.
\end{proof}
\section{Unavoidability of $k$-abelian squares in pure morphic words}
In this section we extend the result of Theorem \ref{3-abelian} from
3-abelian squares to arbitrary $k$-abelian squares. We start with a
lemma.
\begin{lemma} \label{induction}
If a ternary infinite pure morphic word contains a $(k-1)$-abelian square for $k > 3$, then it contains a $k$-abelian square.
\end{lemma}
\begin{proof}
Consider a ternary prefix-preserving morphism $h$ and assume that $w =
h^{\infty}(a)$ contains a $(k-1)$-abelian square, i.e., there exist
$(k-1)$-abelian equivalent words $u_{1}$ and $u_{2}$ such that
$u_{1}u_{2} \in F(w)$. Assume, contrary to what we want to prove,
that $w$ is $k$-abelian
square-free. From Lemma \ref{two} it follows that we may assume
$|h(a)|, |h(c)| \geq 3$ and $h(b) = b$.
Now every factor of length $k$ in the word $h(u_{1})$ (resp., $h(u_{2})$) is a factor of $h(v_{1})$ (resp., $h(v_{2})$) where $v_{1} \in F(u_{1})$ and $|v_{1}| \leq \left\lfloor \frac{k-3}{2} \right\rfloor +3$. This is because if the word contains factors of which at most every other has length one and all the others have length at least three we can reach at most $\left\lfloor \frac{k-3}{2} \right\rfloor +3$ factors with a subword of length $k$. For example, with a subsword of length 11 we can reach at most 7 factors as depicted below.
$$\ldots -*--\underbrace{-*---*---*-}_{}--*- \ldots$$
Thus the factors of $h(u_{1})$ (resp., $h(u_{2})$) of length $k$ are determined by factors of $u_{1}$ (resp., $u_{2}$) of length at most $k-1$ because $k-1 \geq \left\lfloor \frac{k-3}{2} \right\rfloor +3$ for $k>3$. We know that $u_{1}$ and $u_{2}$ are $(k-1)$-abelian equivalent thus $h(u_{1})$ and $h(u_{2})$ have the same number of occurrences of different factors of length $k$.
In addition, $\textrm{pref}_{k-2}(u_{1}) = \textrm{pref}_{k-2}(u_{2})$ implying $\textrm{pref}_{k-1}(h(u_{1})) = \textrm{pref}_{k-1}(h(u_{2}))$. The suffixes of length $k-1$ of the words $h(u_{1})$ and $h(u_{2})$ coincide, too. This shows that $h(u_{1})$ and $h(u_{2})$ are $k$-abelian equivalent and clearly $h(u_{1})h(u_{2}) \in F(w)$.
\end{proof}
Now we are ready to state the second part of the main result generalizing Theorem \ref{3-abelian}.
\begin{theorem}\label{k-abelian}
Every ternary infinite pure morphic word contains a $k$-abelian square for any $k \geq 1$.
\end{theorem}
\begin{proof}
Theorem \ref{3-abelian} states the result for $k=3$ and by lemma
\ref{smaller} claim holds also for $1\leq k \leq 3$. Now we can use
Lemma \ref{induction} for the case $k=4$ and inductively prove the
claim for $k \geq 4$. \end{proof}
\section{Conclusion}
We know from Thue that an infinite square-free word over a ternary alphabet can be obtained by iterating a morphism. In this paper we have shown that infinite pure morphic words over ternary alphabets do not avoid $k$-abelian squares for any $k \geq 1$. Thus if an infinite ternary $k$-abelian square-free word exists for some $k \geq 1$,
an iterated morphism is not the way to produce it. This differs from the situation of ordinary square-freeness and abelian square-freeness and emphasizes the intricate nature of the $k$-abelian equivalence with respect to morphism iteration.
As mentioned, we have been able to obtain ternary 3-abelian square-free words longer than 100,000 letters by a computer. This suggests that there might exist an infinite 3-abelian square-free word over a ternary alphabet, but it remains open how to produce it. For example, it is not known whether a morphic word could give an infinite 3-abelian square-free word.\footnote{The first author has recently found a morphic word over a ternary alphabet avoiding $k$-abelian squares, but requiring $k$ to be rather large.}
\section{Acknowledgements}
The authors would like to thank Pascal Ochem for beneficial discussions
and constructive comments for preparing this paper.
\begin{thebibliography}{99}
\bibitem{AS} J.-P. Allouche and J. Shallit, \textit{Automatic Sequences: Theory, Applications, Generalizations}, Cambridge University Press, 2003.
\bibitem{Bers} J. Berstel, Axel Thue's papers on repetitions in words:
a translation, \textit{Publications du Laboratoire de Combinatoire et
d'Informatique Math\'ematique, Universit\'e du Qu\'ebec \`a
Montr\'eal} \textbf{20} (1995).
\bibitem{Ca} J. Cassaigne, Unavoidable binary patterns, \textit{Acta
Informatica} \textbf{30} (1993), 385--395.
\bibitem{CK} C. Choffrut and J. Karhum\"aki, Combinatorics of words, in
G. Rozenberg and A. Salomaa, eds., \textit{Handbook of Formal
Languages}, Vol.\ 1, Springer, 1997, pp.\ 329--438.
\bibitem{CKL} K. Culik, J. Karhum\"aki and A. Lepist\"o, Alternating
iteration of morphisms and the Kolakoski sequence, in G. Rozenberg and
A. Salomaa, eds., \textit{Lindenmayer Systems}, Springer, 1992, pp.\ 93--106.
\bibitem{Cu} J. D. Currie, Open problems in pattern avoidance,
\textit{Amer. Math. Monthly} \textbf{100} (1993), 790--793.
\bibitem{Dek} F. M. Dekking, Strongly non-repetitive sequences and
progression-free sets, \textit{J. Combin. Theory Ser.} A \textbf{27}
(1979), 181--185.
\bibitem{Evdok} A. A. Evdokimov, Strongly asymmetric sequences
generated by a finite number of symbols, \textit{Dokl. Akad. Nauk SSSR}
\textbf{179} (1968), 1268--1271. English translation in \textit{Soviet
Math. Dokl.} \textbf{9} (1968), 536--539.
\bibitem{HK} M. Huova and J. Karhum\"aki, On $k$-abelian avoidability,
in conference proceedings of \textit{RuFiDiM 2011}, \textit{Notes of
Scientific Seminars of the St. Petersburg department of the Steklov
Mathematical Institute, Russian Academy of Sciences}, 2012, pp.\
170--182. Available electronically at
\url{http://www.pdmi.ras.ru/znsl/2012/v402.html}.
\bibitem{HKS} M. Huova, J. Karhum\"aki and A. Saarela, Problems in
between words and abelian words: $k$-abelian avoidability, in G.
Rozenberg and A. Salomaa, eds., \textit{Formal and Natural Computing
Honoring the 80th Birthday of Andrzej Ehrenfeucht}, Theor. Comput. Sci.
\textbf{454} (2012), 172--177.
\bibitem{HKSS} M. Huova, J. Karhum\"aki, A. Saarela and K. Saari, Local
squares, periodicity and finite automata, in C. S. Calude, G. Rozenberg
and A. Salomaa, eds., \textit{Rainbow of Computer Science}, Lect. Notes
in Comp. Sci., Vol.\ 6570, Springer, 2011, pp.\ 90--101.
\bibitem{KSZ} J. Karhum\"aki, A. Saarela and L. Zamboni, Generalized
abelian equivalence, manuscript to be published.
\bibitem{Ker} V. Ker\"anen, Abelian squares are avoidable on 4 letters,
in W. Kuich, ed., \textit{Proc. ICALP 1992}, Lect. Notes in Comp. Sci.,
Vol.\ 623, Springer, 1992, pp.\ 41--52.
\bibitem{Lo1} M. Lothaire, \textit{Combinatorics on Words},
Addison-Wesley, 1983.
\bibitem{Lo2} M. Lothaire, \textit{Algebraic Combinatorics on Words},
Cambridge University Press, 2002.
\bibitem{MS} R. Mercas and A. Saarela, $5$-abelian cubes are avoidable
on binary alphabets, in {\it Proc. 14th Mons Days of
Theoretical Computer Science}, 2012.
\bibitem{Pleas} P. A. B. Pleasant, Non-repetitive sequences,
\textit{Proc. Cambridge Philos. Soc.} \textbf{68} (1970), 267--274.
\bibitem{Thue1} A. Thue, \"Uber unendliche Zeichenreihen,
\textit{Norske vid. Selsk. Skr. Mat. Nat. Kl.} \textbf{7} (1906),
1--22.
\bibitem{Thue2} A. Thue, \"Uber die gegenseitige Lage gleicher Teile
gewisser Zeichenreihen, \textit{Norske vid. Selsk. Skr. Mat. Nat. Kl.}
\textbf{1} (1912), 1--67.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 68R15.
\noindent \textit{Key words:} combinatorics on words,
$k$-abelian equivalence, avoidability.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A000002},
\seqnum{A006156}, and
\seqnum{A010060}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received July 1 2012;
revised version received, October 11 2012.
Published in {\it Journal of Integer Sequences}, March 2 2013.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}