<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\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{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://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\usepackage[latin1]{inputenc}\usepackage[english]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{latexsym}
%\usepackage[dvips]{graphicx}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{rem}[theorem]{Remark}
\newenvironment{remark}{\begin{rem}\rm}{\end{rem}}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{eg}[theorem]{Example}
\newenvironment{example}{\begin{eg}\rm}{\end{eg}}
\newtheorem{conj}[theorem]{Conjecture}
\newenvironment{conjecture}{\begin{conj}\rm}{\end{conj}}
\newtheorem{prob}[theorem]{Problem}
\newenvironment{problem}{\begin{prob}\rm}{\end{prob}}

%\newtheorem{theorem}{Theorem}[section]
%\newtheorem{proposition}{Proposition}[section]
%\newtheorem{corollary}{Corollary}[section]
%\newtheorem{lemma}{Lemma}[section] 

\newcommand{\pf}{\noindent {\bf Proof: }}

\begin{document}

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

\begin{center}
\vskip 1cm{\LARGE\bf 
The Number of Ternary Words Avoiding \\
\vskip .1in
Abelian Cubes Grows Exponentially}
\vskip 1cm
\large
Ali Aberkane \&amp; James D. Currie\footnote{This author's research was supported by an NSERC operating grant.}\\
Department of Mathematics and Statistics\\
University of Winnipeg \\
Winnipeg, Manitoba R3B 2E9\\
Canada\\
\href{mailto:aberkane@iml.univ-mrs.fr}{\tt aberkane@iml.univ-mrs.fr} \\
\href{mailto:currie@uwinnipeg.ca}{\tt currie@uwinnipeg.ca} \\
\ \\
Narad Rampersad\\
School of Computer Science\\
University of Waterloo\\
Waterloo, Ontario N2L 3G1\\
Canada\\
\href{mailto:nrampersad@math.uwaterloo.ca}{\tt nrampersad@math.uwaterloo.ca} 
\end{center}

\vskip .2 in

\begin{abstract}
\noindent We show that the number of ternary words of length $n$
avoiding abelian cubes
grows faster than $r^n$, where $r = 2^{1/24}$.\vspace{.1in}\\
\end{abstract}



\section{Introduction}
The study of words avoiding repetitions is an area of
combinatorics on words reaching back to at least the turn of the
century and the work of Thue. A word of the form $xx$, $x$ some
non-empty word, is called a {\it square}. A word of the form
$xxx$, $x$ some non-empty word, is called a {\it cube}. A word
containing no squares (cubes) is called {\it square-free} ({\it
cube-free}).

The longest square-free words over the 2-letter alphabet $\{a,
b\}$ are $aba$ and $bab$. Nevertheless, in 1906 Thue showed that
over a 3-letter alphabet, there are arbitrarily long square-free
words \cite{thueI}. Thue also showed that there are arbitrarily
long cube-free words over a 2-letter alphabet.

How many square-free words over $\{a, b, c\}$ are there? An exact
answer remains elusive. Let $c(n)$ be the number of ternary
square-free words of length $n$. In 1997  \cite{noonan} it was
still of interest even to calculate $c(46)$. A recent article
\cite{grimm} gives values to $c(110)$. Exponential upper and lower
bounds on $c(n)$ have been steadily improved in a series of
articles by various authors
\cite{brinkhuis,brandenburg,baake,ekhad,grimm,xinyusun}. The
current best lower bound, given in \cite{xinyusun}, is $c(n)\ge
110^{n/42} = (1.118419\ldots)^n$. According to Grimm \cite{grimm},
an exponential upper bound has base $8416550317984^\frac{1}{108} =
1.317277\ldots$

In algebraic problems, commutativity is usually a simplifying
assumption. However, for word repetitions, the commutative
problems have been hard to crack. An {\it abelian square} is a
word $x_1x_2$ where $x_2$ can be obtained from $x_1$ by
rearranging letters. The study of abelian squares was initiated by
Erdos \cite{erdos}, who asked whether an infinite sequence over a
finite alphabet existed which was square-free in an abelian sense;
no two adjacent blocks were to be permutations of one another. Not
only $1234\hspace{.05in}1234$ is forbidden in such a sequence, but
also $1234\hspace{.05in}2134$, since 1234 and 2134 are
permutations of each other. A sequence avoiding squares in this
abelian sense was discovered by Evdokimov \cite{evdokimov}, but he
used an alphabet of 25 letters. The alphabet size was reduced to 5
letters by Pleasants \cite{pleasants}, and not until 1992, to a 4-letter
alphabet by Ker\"{a}nen \cite{keranen}. One checks that on
a 3-letter alphabet there are only finite strings which are
square-free in this abelian sense, so that Ker\"{a}nen's result is
optimal. Dekking \cite{dekking} showed that the smallest alphabet
on which cubes were avoidable in this abelian sense had 3 symbols,
while 2 symbols were necessary and sufficient to avoid fourth
powers in the abelian sense.

Carpi \cite{carpicount1,carpicount2} showed that the number of
words over $\{0, 1, 2, 3\}$ avoiding abelian squares grows
exponentially with length. Recently one of the authors
\cite{currie} showed that the number of binary words avoiding
abelian fourth powers grows exponentially with length. In the
following article we ``finish off" the abelian growth problems by
solving the following problem from \cite{avoidanceproblems}:
\begin{problem}
Show that the number of abelian cube-free ternary words grows
exponentially with length.
\end{problem}

The number of ternary words avoiding abelian cubes for
$n = 0,1, \ldots 13$ is
$$
1, 3, 9, 24, 66, 180, 468, 1206, 3150, 7998, 20124, 50520, 124044, 303906
$$
and is sequence \seqnum{A096168} in the Encyclopedia of Integer Sequences.

\section{Preliminaries}
We say that $x\sim y$ for words $x$ and $y$ if the number of
occurrences each letter is identical in $x$ and in $y$. For
example, $123342\sim 321342$. We say that word $w$ {\it encounters
an abelian cube} if $w$ has a subword $x_1x_2x_3$ with $x_i\sim
x_{i+1}$, $i = 1,2$, $x_1\ne \epsilon$.

We use ${\mathbb Z}$ to denote the set of integers, and $R^n$ to
denote the set of $1\times n$ matrices (i.e., row vectors) with
entries in ring $R$.

A {\it multi-valued substitution} is a function
$h:\Sigma^*\rightarrow {\cal P}(T^*)$ where ${\cal P}(T^*)$ is the
set of subsets of $T^*$. Let $v\in \Sigma^*$, $v = v_1v_2v_3\ldots
v_k$, $v_i\in\Sigma$, $i =1, 2, \ldots , k$. We say that word $w$
is an image of word $v$ under multi-valued substitution $h$ if we
can write $w = w_1w_2w_3\ldots w_k$ where $w_i\in h(v_i)$, $i = 1,
2, 3, \ldots, k$. We write $w\in h(v)$. In the case that $\Sigma =
T$, we call $h$ a {\it multi-valued substitution on $\Sigma$}.

 Fix a natural number
$m$, and let $\Sigma$ be the alphabet $\{0,1,
 \ldots, m-1\}$. If $w$ is a word , we define
$f(w)=[|w|_0,|w|_1,\ldots,|w|_{m-1}]$. In other words, $f(w)$ is a
row vector which counts the occurrences of $0,1,
 \ldots, m-1$ in $w$, and for $w,v\in \Sigma^*$ we have $w\sim v$ exactly when $f(w)=f(v)$.
Suppose that $h$ is a multi-valued substitution on $\Sigma$ such
that for each $i\in\Sigma$ we have $f(u)=f(v)$ whenever $u,v\in
h(i)$. In this case we say that $h$ is {\it single-valued up to
permutation}. Let the {\it incidence matrix} $M$ of $h$ be the
$m\times m$ matrix with $i$th row $f(v)$, any $v\in h(i)$. We
observe that if $w$ is an image of $v$ under $h$, then $f(w) =
f(v)M$.

Now fix $m = 3$ and $\Sigma = \Sigma$. Consider the multi-valued
substitution $h$ on $\Sigma$ given by
\begin{eqnarray*}
h(0) &amp;=&amp; \{001002\}\\
h(1) &amp;=&amp;\{110112\}\\
h(2) &amp;=&amp;\{002212, 122002\}
\end{eqnarray*}

The corresponding matrix $M$ is thus
\[ \left[
\begin{array}{ccc}
4&amp;1&amp;1\\
1&amp;4&amp;1\\
2&amp;1&amp;3
\end{array}
\right]\]

\begin{remark}
Let $v\in {\mathbb Z}^3$. It is an exercise in linear algebra to
check that $uM=v$ has a solution $u\in{\mathbb Z}^3$ if and only
if
\[v \left[
\begin{array}{c}
1\\
13\\
19
\end{array}
\right] \in {36 \mathbb Z}^1.\]
\end{remark}

Let $L=\{w:uwv\in h^n(0)\mbox{ for some positive integer }n,\mbox{
some words }u,v \}$. Thus $L$ is the set of words contained in
some image of 0 under iterations of $h$. Set $L$ is closed under
$h$, and each word of $L$ is a subword of a word of $h(L)$. If
$w\in L$ then for some letters $a,b\in\Sigma$ we have $awb\in L$.
We will prove
\begin{theorem}[Main Theorem]
Set $L$ contains no abelian cubes.
\end{theorem}

\begin{remark}
It is not the case that $h$ is abelian cube-free. That is, words
of $h(u)$ may contain abelian cubes, even $u$ does not. For
example, $$001002110112001002110112\in h(0101), \mbox{ but }0101$$
contains no abelian cubes, while
$0010\hspace{.05in}021101120010021\hspace{.05in}10112$ contains an
abelian cube, since $02110\sim 11200\sim 10021$.
\end{remark}

\section{Templates and Parents}
A {\it template} is a 6-tuple $[a,b,c,d,v_1,v_2]$ where
$a,b,c,d\in\{\epsilon,0,1,2\}$ and $v_1,v_2\in {\mathbb Z}^3$. We
say that a word $w$ {\it realizes} template $[a,b,c,d,v_1,v_2]$ if
we can write $w=aX_1bX_2cX_3d$ where $f(X_2)-f(X_1)=v_1$,
$f(X_3)-f(X_2)=v_2$.

\begin{remark}\label{parse}
Suppose that $X\in L$, $|X|\ge 5$. We can write
$X=a^{\prime\prime}Yb'$ where
\begin{itemize}
\item{for some $Z\in L$, $Y\in h(Z)$}
\item{for some $A,B \in \{0,1,2,\epsilon\}$, there exist words
$a',b^{\prime\prime}$ such that $a'a^{\prime\prime}\in h(A)$,
$b'b^{\prime\prime}\in h(B)$.}\end{itemize}
\end{remark}

Let $t_1=[a,b,c,d,v_1,v_2]$ and $t_2=[A,B,C,D,w_1,w_2]$ be
templates. We say that $t_2$ is a {\it parent} of $t_1$ if
$A,D\ne\epsilon$, and for some words
$a',a^{\prime\prime},b',b^{\prime\prime},c',c^{\prime\prime},d',d^{\prime\prime}$
we have $a'aa^{\prime\prime}\in h(A)$, $b'bb^{\prime\prime}\in
h(B)$,  $c'cc^{\prime\prime}\in h(C)$,  $d'dd^{\prime\prime}\in
h(D)$,  while
\begin{eqnarray*}
v_1 - f(b^{\prime\prime}c') + f(a^{\prime\prime}b') &amp;=&amp; w_1M\\
v_2 - f(c^{\prime\prime}d') + f(b^{\prime\prime}c') &amp;=&amp; w_2M.
\end{eqnarray*}

Given a template $t_1$,  we may calculate all its parents. The set
of candidates for $A,B,C,D$ and hence for
$a',a^{\prime\prime},b',b^{\prime\prime},c',c^{\prime\prime},d',d^{\prime\prime}$
is finite, and may be searched exhaustively. Since $M$ is
invertible, a choice of values for
$a',a^{\prime\prime},b',b^{\prime\prime},c',c^{\prime\prime},d',d^{\prime\prime}$,
together with given values $v_1$ and $v_2$,  determines $w_1$ and
$w_2$. Note that not all computed values for $w_1$,  $w_2$ are in
${\mathbb Z}^3$,  some templates have no parents. For example, an
exhaustive search shows that $[2,1,0,1,[0,0,0],[0,0,0]]$ has no
parents.

\begin{lemma}
Let $t_1=[a,b,c,d,v_1,v_2]$ and $t_2=[A,B,C,D,w_1,w_2]$ be
templates, with $t_2$ a parent of $t_1$. Suppose that some word
$u_2\in L$ realizes $t_2$. Then some subword $u_1$ of a word of
$h(u_2)$ realizes $t_1$. The word $u_1$ is in $L$.
\end{lemma}
\pf Of course if $u_1$ is a subword of a word of $h(u_2)$,  and
$u_2$ is in $L$,  then $u_1$ is in $L$.

Write $u_2=AZ_1BZ_2CZ_3DZ_4$ where $f(Z_2)-f(Z_1)=w_1$,
$f(Z_3)-f(Z_2)=w_2$. Since $t_2$ is a parent of $t_1$,  find words
$a',a^{\prime\prime},b',b^{\prime\prime},c',c^{\prime\prime},d',d^{\prime\prime}$
so that $a'aa^{\prime\prime}\in h(A)$,  $b'bb^{\prime\prime}\in
h(B)$, $c'cc^{\prime\prime}\in h(C)$, $d'dd^{\prime\prime}\in
h(D)$,  and
\begin{eqnarray*}
v_1 - f(b^{\prime\prime}c') + f(a^{\prime\prime}b') &amp;=&amp; w_1M\\
v_2 - f(c^{\prime\prime}d') + f(b^{\prime\prime}c') &amp;=&amp; w_2M.
\end{eqnarray*}

Choose any words $Y_1,Y_2,Y_3$ with $Y_i\in h(Z_i)$. This means
that
$$a'aa^{\prime\prime}Y_1b'bb^{\prime\prime}Y_2c'cc^{\prime\prime}Y_3d'dd^{\prime\prime}\in
h(AZ_1BZ_2CZ_3D).$$ Let
$u_1=aa^{\prime\prime}Y_1b'bb^{\prime\prime}Y_2c'cc^{\prime\prime}Y_3d'd$.
Then $u_1$ realizes $t_1$,  which is verified by letting
$X_1=a^{\prime\prime}Y_1b'$,  $X_2=b^{\prime\prime}Y_1c'$,
$X_3=c^{\prime\prime}Y_1d'$. We see that $u_1 = aX_1bX_2cX_3d$,
and
\begin{eqnarray*}
f(X_2)-f(X_1)&amp;=&amp;f(b^{\prime\prime}Y_1c')-f(a^{\prime\prime}Y_1b')\\
             &amp;=&amp;f(b^{\prime\prime}c')-f(a^{\prime\prime}b')+f(Y_2)-f(Y_1)\\
             &amp;=&amp;f(b^{\prime\prime}c')-f(a^{\prime\prime}b')+f(Z_2)M-f(Z_1)M\\
             &amp;=&amp;f(b^{\prime\prime}c')-f(a^{\prime\prime}b')+(f(Z_2)-f(Z_1))M\\
             &amp;=&amp;f(b^{\prime\prime}c')-f(a^{\prime\prime}b')+w_1M\\
             &amp;=&amp;v_1.
\end{eqnarray*}

Similarly, $f(X_3)-f(X_2)=v_2$. Thus $u_1$ realizes $t_1$,  as
desired .$\Box$\vspace{.1in}

\begin{lemma}\label{parentInL}
Let $t_1=[a,b,c,d,v_1,v_2]$ be a template. Suppose that some word
$u_1\in L$ realizes $t_1$, with $|u_1|&gt; 17$. Suppose further that
\[[-1]\le v_1\left[
\begin{array}{c}
1\\
1\\
1
\end{array}
\right],v_2\left[
\begin{array}{c}
1\\
1\\
1
\end{array}
\right],(v_1+v_2)\left[
\begin{array}{c}
1\\
1\\
1
\end{array}
\right]\le[1].\] Then there is a template
$t_2=[A,B,C,D,w_1,w_2],A,B\ne \epsilon$ which is a parent of
$t_1$,  and a word $u_2\in L$ which realizes $t_2$.
\end{lemma}
\pf Clearly, $u_2$ will be shorter than $u_1$.

Write $u_1= aX_1bX_2cX_3d$ where $f(X_2)-f(X_1)=v_1$,
$f(X_3)-f(X_2)=v_2$. The condition on $v_1,v_2$ and $v_1+v_2$
implies that $|X_1|-1\le|X_2|,|X_3|\le|X_1|+1$. Thus
\begin{eqnarray*}
17&amp;\le&amp;|u_1|\\
&amp;=&amp;|aX_1bX_2cX_3d|\\
&amp;=&amp;|a|+|X_1|+|b|+|X_2|+|c|+|X_3|+|d|\\
&amp;\le&amp; 3|X_1|+2,i=1,2,3.\\
\end{eqnarray*}
We deduce that $|X_1|\ge 5$. Similarly,  $|X_2|,|X_3|\ge 5$.
Rewriting $X_1=a^{\prime\prime}Y_1b'$,  etc, we find there must be
a word $a'u_1d^{\prime\prime}\in h(L)$ with

\begin{eqnarray*}
a'u_1d^{\prime\prime}&amp;=&amp;a'aX_1bX_2cX_3dd^{\prime\prime}\\
&amp;=&amp;a'aa^{\prime\prime}Y_1b'bb^{\prime\prime}Y_2c'cc^{\prime\prime}Y_3d'dd^{\prime\prime}\\
&amp;\in&amp;h(u_2)
\end{eqnarray*}
for some word $$u_2=AZ_1BZ_2CZ_3D \in L$$ satisfying
\begin{eqnarray*}
Y_i&amp;\in&amp; h(Z_i),\mbox{ }i=1,2,3\\
A,B,C,D &amp;\in&amp; \{\epsilon,0,1,2\}\\
b'bb^{\prime\prime}&amp;\in&amp; h(B)\\
c'cc^{\prime\prime}&amp;\in&amp;h(C)
\end{eqnarray*}\vspace*{-.3in}
$$aa^{\prime\prime} \mbox{ is a suffix of an element of }h(A)\vspace*{-.05in}$$
$$d'd\mbox{ is a prefix
of an element of }h(D).$$

If a solution $u_2$ of these conditions has $A=\epsilon$,  then by
force, $aa^{\prime\prime}=\epsilon$. Since $\epsilon$ is also a
suffix of $h(0)$,  another solution $\hat{u}_2$ exists, differing
from $u_2$ only by changing $A$ to $0$. We may therefore assume
that $A\ne \epsilon$. Similarly, assume $D\ne\epsilon$. Given a
solution $u_2$ of our conditions, let
$w_1=f(Z_2)-f(Z_1),w_2=f(Z_3)-f(Z_2)$. As in the previous lemma,
\begin{eqnarray*}
v_1 - f(b^{\prime\prime}c') + f(a^{\prime\prime}b') &amp;=&amp; w_1M\\
v_2 - f(c^{\prime\prime}d') + f(b^{\prime\prime}c') &amp;=&amp; w_2M.
\end{eqnarray*} It follows that $t_2=[A,B,C,D,w_1,w_2]$ is a
parent of $t_1$,  realized by a word $u_2\in L. \Box$
\vspace{.1in}

A template $t=[a,b,c,d,v_1,v_2]$ {\it implies a cube} if either
\[f(a)-f(b) = v_1\mbox{ and }f(b)-f(c) = v_2
\mbox{ \bf OR }f(b)-f(c) = v_1\mbox{ and }f(c)-f(d) = v_2.\]
Suppose that $u$ realizes $t=[a,b,c,d,v_1,v_2]$,  and $t$ implies
a cube. Write $u = aX_1bX_2cX_3d$ where $v_1=f(X_2)-f(X_1)$,
$v_2=f(X_3)-f(X_2)$. We suppose that $f(a)-f(b) = v_1\mbox{ and
}f(b)-f(c) = v_2$. (The other case is similar.) In this case, $u$
contains the abelian cube $aX_1bX_2cX_3$. We have
$f(aX_1)-f(bX_2)=f(a)-f(b)-(f(X_2)-f(X_1))=v_1-v_1=[0,0,0]$. Thus
$aX_1\sim bX_2$. Similarly, $bX_2\sim cX_3$,  $aX_1bX_2cX_3$ is an
abelian cube, as claimed.

 A set $T$ of templates is {\it closed} if whenever
$t_1\in T$ and $t_2$ is a parent of $t_1$,  then $t_2\in L$ if
$t_2$ does not imply a cube.

Let $t_c=[\epsilon,\epsilon,\epsilon,\epsilon,[0,0,0],[0,0,0]]$.
An abelian cube realizes $t_c$. To show that $L$ is abelian
cube-free, we start by finding a closed set $T_c$ of templates
containing $t_c$,  and checking that whenever $t=[a,b,c,d,v_1,v_2]
\in T_c$,  then

\[[-1]\le v_1\left[
\begin{array}{c}
1\\
1\\
1
\end{array}
\right],v_2\left[
\begin{array}{c}
1\\
1\\
1
\end{array}
\right],(v_1+v_2)\left[
\begin{array}{c}
1\\
1\\
1
\end{array}
\right]\le[1].\]

Suppose now that $u_1$ is the shortest word of $L$ realizing a
template $t_1$ of $T_c$. If $|u_1|\ge 17$,  by
Lemma~\ref{parentInL}, a parent $t_2$ of $t_1$ is realized by a
word $u_2\in L$ which is shorter than $u_1$. The minimality of
$|u_1|$ implies that $t_2\notin T_c$. Since $T_c$ is closed, this
means that $t_2$ implies a cube. It follows that $u_2$ realizes
$t_c\in T_c$. This is a contradiction. Thus $|u_1|&lt;17.$

We then generate the set of all words of $L$ of length 16. A
finite search shows that none of these words realizes a template
in $T_c$. It follows that no word $u_1$ can exist, so that $L$ is
abelian cube-free.

\section{Computations}
Given a template $t$,  the MAPLE procedure {\tt parents} in
Appendix 1 generates all of $t$'s parents which do not imply a
cube. Given a set {\tt seed} of templates, the procedure {\tt
grow} generates the set {\tt closure}, the smallest closed set
containing {\tt seed}. A Pentium 4 running MAPLE 7 at 2.53 GHz ran
{\tt grow} on
$t_c=[\epsilon,\epsilon,\epsilon,\epsilon,[0,0,0],[0,0,0]]$ in 4.6
seconds. We find that $|T_c|=103.$ The output $T_c$ is also
observed to have the property that if $t=[a,b,c,d,v_1,v_2] \in
T_c$,  then

\[[-1]\le v_1\left[
\begin{array}{c}
1\\
1\\
1
\end{array}
\right],v_2\left[
\begin{array}{c}
1\\
1\\
1
\end{array}
\right],(v_1+v_2)\left[
\begin{array}{c}
1\\
1\\
1
\end{array}
\right]\le[1].\]

(We thus observe {\it a posteori} both that $T_c$ is finite, and
that its various $v_1, v_2$ have this desirable property.) Another
observation is that the only $t\in T_c$ for which any of $a,b,c,d$
is $\epsilon$ is $t=t_c$.

Since images of letters under $h$ have length 6, we see that any
word $w$ of $L$ with $|w|=16$ is a subword of $h(a_1a_2a_3a_4)$
for some word $a_1a_2a_3a_4\in L$ with the $a_1,a_2,a_3,a_4$
letters. We see in turn, that $a_1a_2a_3a_4$ will be a subword of
$h(\{00,01,02,10,11,12,20,21,22\})$,  and thus of
$h(112001002122)$,  since each of $00,01,02,10,11,12,20,21,22$ is
a subword of $112001002122$. Word $112001002122$ is itself a
subword of a word in $h(102)$.

We obtain the set all of words of length 16 in $L$ as follows:
\begin{enumerate}
\item{Apply $h$ to $\{112001002122\}$ to obtain a set {\tt
imageSet}}
\item{Collect all subwords of length 4 from the words of {\tt imageSet}
to give a set {\tt length4Words}. We find that {\tt length4Words},
and hence $L$,  contains exactly 27 words of length 4.}
\item{Apply $h$ to {\tt length4Words} to obtain {\tt imageSet4}. There are 80 words in this set.}
\item{Build {\tt testSet} by collecting all subwords of length 16 from the words of the
resulting {\tt imageSet4}. We thus find that there are 278 words
of length 16 in $L$.}
\end{enumerate}

For each template $t$ in $T_c$ and each word $w$ of length 16 in
$L$,  viz., for each $w\in$ {\tt testSet}, we verify that no
subword of $w$ realizes $t$. This is done in two stages:
\begin{enumerate}
\item{For  $w\in$ {\tt testSet} and $t\in T_c-\{t_c\}$,  we verify
that no subword of $w$ realizes $t$ using procedure {\tt occurs}.}
(The procedure {\tt occurs} takes advantage of the fact that if
$[a,b,c,d,v_1,v_2]\in T_c-\{t_c\}$,  then $a,b,c,d\ne \epsilon$.)
\item{For $w\in$ {\tt testSet}, we verify
that no subword of $w$ realizes $t_c$ using procedure {\tt
cubeOccurs}.}
\end{enumerate}
The total time for these verifications is 60.4 seconds. The
computations establish the Main Theorem.

\section{Exponential Growth}
Let $w$ be the prefix of a word of $h^\omega(0)$ such that
$|w|=n$. We can write $w\in h(v)p$ where $v$ is a prefix of a word
of $h^\omega(0)$,  and $|p|\le 5.$ By our Main Theorem, every word
in $h(v)p$ avoids abelian cubes. Since each image of a letter
under $h$ contains a $2$,  $|v|_2\ge (|v|-5)/6$. Since $h(2)$
contains 2 words, we see that $h(v)$,  and hence $h(v)p$ contains
at least $2^{(|v|-5)/6}$ words. Also, $n=|w|=|h(v)p|\le 6|v|+5.$
Then $2^{(|v|-5)/6}\ge 2^{((n-5)/6-5)/6}=2^{-35/36}2^{n/36}$. It
follows that $h(v)p$ contains at least $cr^n$ abelian cube-free
words of length $n$,  where $c = 2^{-35/36}$ and $r = 2^{1/36}$.

The base $2^{1/36}$ may be sharpened. By a slight variation on
Theorem~8.4.6 in \cite{allouche}, letter frequencies in
$h^\omega(0)$ can be obtained from the normalized eigenvector of
the incidence matrix $M$ corresponding to the dominant eigenvalue.
(By Perron-Frobenius theory, this eigenvalue has multiplicity 1
and its corresponding eigenvector is non-negative.)  We find that
for $M$ the dominant eigenvalue is 6 and the corresponding
normalized eigenvector is [5/12,1/3,1/4]. This means that the
asymptotic frequency of 2's is 1/4. Using $|v|_2 \sim |v|/4$ in
the previous paragraph would show the number of abelian cube-free
words of length $n$ over $\{0,1,2\}$ to be $\Omega(2^{n/24})$,
rather than $\Omega(2^{n/36})$.

\begin{theorem}[Second Main Theorem]
The number of abelian cube-free words of length $n$ over
$\{0,1,2\}$ is $\Omega(2^{n/24})$.
\end{theorem}

\section{Acknowledgments}

Special thanks to T.~I.~Visentin for a suggestion
which significantly speeded up the MAPLE code.
Thanks also to the anonymous referee.

\section*{Appendix: Code} A MAPLE worksheet with all code referred to
in this paper is available from
\begin{verbatim}www.uwinnipeg.ca/~currie/AbelianCubes.mws\end{verbatim} Here are the most important
pieces:

The following MAPLE code sets up an array {\tt split} which is
used by {\tt parents}:

\begin{verbatim}For a letter a, split[a]={[f(a'),f(a"),alpha]:h(alpha)=a'aa"}.
Here 3 stands for the empty/missing letter \epsilon. We let
split[3]={[f(a'),f(a"),alpha]:h(alpha)=a'a"}. We represent these
sets by lists.}
\end{verbatim}
\begin{verbatim} &gt;split[0]:=[[[0,0,0],[3,1,1],0],[[1,0,0],[2,1,1],0],
[[2,1,0],[1,0,1],0],[[3,1,0],[0,0,1],0],[[0,2,0],[0,2,1],1],
[[0,0,0],[1,1,3],2],[[1,0,0],[0,1,3],2],[[0,1,2],[1,0,1],2],
[[1,1,2],[0,0,1],2]];
&gt;split[1]:=[[[2,0,0],[2,0,1],0],[[0,0,0],[1,3,1],1],
[[0,1,0],[1,2,1],1],[[1,2,0],[0,1,1],1],[[1,3,0],[0,0,1],1],
[[2,0,2],[0,0,1],2],[[0,0,0],[2,0,3],2]];
&gt;split[2]:=[[[2,0,1],[0,1,1],2],[[4,1,0],[0,0,0],0],
[[1,4,0],[0,0,0],1],[[2,0,0],[0,1,2],2],[[2,1,2],[0,0,0],2],
[[0,1,0],[2,0,2],2],[[0,1,1],[2,0,1],2]];}
&gt;split[3]:=[[[0,0,0],[0,0,0],3],[[1,2,0],[0,2,1],1],
[[0,0,0],[0,0,0],3],[[0,0,0],[4,1,1],0],[[1,0,0],[3,1,1],0],
[[2,0,0],[2,1,1],0],[[2,1,0],[2,0,1],0],[[3,1,0],[1,0,1],0],
[[4,1,0],[0,0,1],0],[[0,0,0],[1,4,1],1],[[0,1,0],[1,3,1],1],
[[0,2,0],[1,2,1],1],[[1,3,0],[0,1,1],1],[[1,4,0],[0,0,1],1],
[[0,0,0],[2,1,3],2],[[1,0,0],[1,1,3],2],[[2,0,0],[0,1,3],2],
[[2,0,1],[0,1,2],2],[[2,0,2],[0,1,1],2],[[2,1,2],[0,0,1],2],
[[0,1,0],[2,0,3],2],[[0,1,1],[2,0,2],2],[[0,1,2],[2,0,1],2],
[[1,1,2],[1,0,1],2]];\end{verbatim}

Given a template $t$,  the MAPLE procedure {\tt parents} generates
all of $t$'s parents which do not imply a cube.

\begin{verbatim}
&gt; parents:=proc(template)

Given a template t1 = [a, b, c, d, v1, v2], the following
procedure finds the set of all parents of t. We rewrite u1 =
aX1bX2Cx3d  as u1=aa"Y1b'bb"Y2c'cc"Y3d'd in all possible ways. (We
use the symbol '3' for the empty/missing letter \epsilon, so if b
= 3, then aX1bX2cX3d = aX1X2cX3d, for example.) For a given way of
rewriting u1, we should have
       v1-f(b"c') + f(a"b') = f(Y2)-f(Y1),
       v2-f(c"d') + f(b"c') = f(Y3) -f(Y2)
To find potential parents, we let a', a" range over possible
``splits"  of h(a), etc, and test whether each of v1 - f(b"c') +
f(a"b') and v2 - f(c"d') + f(b"c') is an integer combination of
parikh vectors of h(0), h(1), h(2). In this case we solve
(wi)M=f(Y(i+1))-f(Yi). The parent is then t2 = [A,B,C,D,w1,w2]
where h(A)=a'aa", etc. The values of A, B, C, D are available as
the third component of the ``split" array. We suppress parents
which imply cubes.

&gt; a:=template[1];b:=template[2];c:=template[3];
&gt; d:=template[4];v1:=template[5];v2:=template[6];
&gt; parentSet:={};
&gt; for A in split[a] do for B in split[b] do for C in split[c] do
&gt; for D in split[d] do
&gt;    if not((A[3]=3) or (D[3]=3)) then
&gt;&gt;      As:=A[2];Bp:=B[1];Bs:=B[2];Cp:=C[1];Cs:=C[2];Dp:=D[1];
&gt;       if (
&gt; ((v1[1]+As[1]+Bp[1]-Bs[1]-Cp[1]+13*(v1[2]+As[2]+Bp[2]-Bs[2]-Cp[2])
&gt; +19*(v1[3]+As[3]+Bp[3]-Bs[3]-Cp[3]) )mod 36 = 0) and
&gt; ((v2[1]+Bs[1]+Cp[1]-Cs[1]-Dp[1]+13*(v2[2]+Bs[2]+Cp[2]-Cs[2]-Dp[2])
&gt; +19*(v2[3]+Bs[3]+Cp[3]-Cs[3]-Dp[3]) )mod 36 = 0)   ) then

To speed up this procedure, some linear algebra is done ``long
hand".  The above condition is that v1[1,13,19]^T ,v1[1,13,19]^T
are in 36Z^3.  The following computation is wi = ( f(Y(i+1))-f(Yi)
)M^{-1}:

&gt; w1:=[11/36*(v1[1]+As[1]+Bp[1]-Bs[1]-Cp[1])-1/36*(v1[2]+
&gt; As[2]+Bp[2]-Bs[2]-Cp[2])-7/36*(v1[3]+As[3]+Bp[3]-Bs[3]-
&gt; Cp[3]),-1/18*(v1[1]+As[1]+Bp[1]-Bs[1]-Cp[1])+5/18*(v1[2]+
&gt; As[2]+Bp[2]-Bs[2]-Cp[2])-1/18*(v1[3]+As[3]+Bp[3]-Bs[3]-
&gt; Cp[3]),-1/12*(v1[1]+As[1]+Bp[1]-Bs[1]-Cp[1])-1/12*(v1[2]+
&gt; As[2]+Bp[2]-Bs[2]-Cp[2])+5/12*(v1[3]+As[3]+Bp[3]-Bs[3]-
&gt; Cp[3])];
&gt; w2:=[11/36*(v2[1]+Bs[1]+Cp[1]-Cs[1]-Dp[1])-1/36*(v2[2]+
&gt; Bs[2]+Cp[2]-Cs[2]-Dp[2])-7/36*(v2[3]+Bs[3]+Cp[3]-Cs[3]-
&gt; Dp[3]),-1/18*(v2[1]+Bs[1]+Cp[1]-Cs[1]-Dp[1])+5/18*(v2[2]+
&gt; Bs[2]+Cp[2]-Cs[2]-Dp[2])-1/18*(v2[3]+Bs[3]+Cp[3]-Cs[3]-
&gt; Dp[3]),-1/12*(v2[1]+Bs[1]+Cp[1]-Cs[1]-Dp[1])-1/12*(v2[2]+
&gt; Bs[2]+Cp[2]-Cs[2]-Dp[2])+5/12*(v2[3]+Bs[3]+Cp[3]-Cs[3]-
&gt; Dp[3])];

 We will ignore parents which imply cubes

&gt;             check1:=[0,0,0]; check1[A[3]+1]:=1;
&gt;             check2:=[0,0,0]; if not(B[3]=3) then
&gt;                check2[B[3]+1]:=1 fi;
&gt;             check3:=[0,0,0]; if not(C[3]=3) then
&gt;                check3[C[3]+1]:=1 fi;
&gt;             check4:=[0,0,0]; check4[D[3]+1]:=1;
&gt;             diff1:=check1-check2;

Here 'diff1' is f(A) - f(B), for deciding if t2 implies a cube

&gt;             diff2:=check2-check3;
&gt;             diff3:=check3-check4;
&gt;             cube:=((w1=diff1)and(w2=diff2)) or
&gt;              ((w1=diff2)and(w2=diff3));
&gt;             if not(cube) then
&gt;                parentSet:=parentSet union
&gt;                 {[A[3],B[3],C[3],D[3],w1,w2]};
&gt;             fi;
&gt;       fi;
&gt;    fi;
&gt; od;od;od;od;
&gt; return(parentSet);
&gt; end;
\end{verbatim}

Given a set {\tt seed} of templates, the procedure {\tt grow}
generates the set {\tt closure}, the smallest closed set
containing {\tt seed}:

\begin{verbatim}&gt; grow:=proc(T)
&gt; seed:=T; closure:={};
&gt; while not(seed={}) do
&gt;    for t in seed do
&gt;       closure:=closure union {t};
&gt;       candidatesForNewParents:=parents(t);
&gt;       seed:=(seed union candidatesForNewParents) minus
&gt;        closure;
&gt;    od
&gt; od;
&gt; return(closure);
&gt; end;
\end{verbatim}

For $t\in T_c-\{t_c\}$,  and $w\in$ {\tt testSet}, we verify that
no subword of $w$ realizes $t$ using procedure {\tt occurs}:

\begin{verbatim}
&gt; occurs:=proc(template,aWord)
Notice that in the set Tc returned by procedure ``grow", there are
no templates other than tc for which a,b,c or d are 3. In this
procedure, we will therefore assume a,b,c,d are letters. A
separate check for tc (which uses empty letters) is in another
procedure. The current procedure takes [a,b,c,d,v1,v2] and a word
and looks for an occurrence of the pattern aX1bX2cX3d in the word.
Again, the ``totals" of v1, v2 and v1+v2 have absolute values at
most 1. We search using ``for loops" on length(X1), length(X2),
length(X3). We have |aWord| &gt;= 4 + |X1| +|X2| +|X3|
&gt;= 4 + 3|X1| -2, so that |X1| &lt;= (|aWord| - 2)/3.
&gt; a:=template[1];b:=template[2];c:=template[3];d:=template[4];
&gt; v1:=template[5];v2:=template[6];L:=length(aWord);
&gt; for L1 from 0 to (L-2)/3 do
&gt;  for L2 from max(0,L1-1) to L1+1 do
&gt;   for L3 from max(0,L1-1,L2-1) to min(L1+1,L2+1) do
&gt;    for iStart from 1 to L-(L1+L2+L3+3) do
&gt;     if (
&gt; (numString(a)=substring(aWord,iStart..iStart))
&gt; and (numString(b)=substring(aWord,iStart+L1+1..iStart+L1+1))
&gt; and (numString(c)=substring(aWord,iStart+L1+L2+2..iStart+L1+L2+2))
&gt; and (numString(d)=substring(aWord,iStart+L1+L2+L3+3..iStart+L1+L2
&gt;     +L3+3)))
&gt;     then
&gt;      X1:=substring(aWord,iStart+1..iStart+L1);
&gt;      X2:=substring(aWord,iStart+L1+2..iStart+L1+L2+1);
&gt;      X3:=substring(aWord,iStart+L1+L2+3..iStart+L1+L2+L3+2);
&gt;      if ((f(X2)-f(X1)=v1) and (f(X3)-f(X2)=v2)) then
&gt;       return(true)
&gt;      fi
&gt;     fi
&gt;    od
&gt;   od
&gt;  od
&gt; od;
&gt; return(false)
&gt; end;
\end{verbatim}

For $w\in$ {\tt testSet}, we verify that no subword of $w$
realizes $t_c$ using procedure {\tt cubeOccurs}:

\begin{verbatim}
&gt; cubeOccurs:=proc(aWord)
&gt; L:=length(aWord);
&gt; for L1 from 1 to L/3 do
&gt;    for iStart from 1 to L-3*L1+1 do
&gt;       X1:=substring(aWord,iStart..iStart+L1-1);
&gt;       X2:=substring(aWord,iStart+L1..iStart+2*L1-1);
&gt;       X3:=substring(aWord,iStart+2*L1..iStart+3*L1-1);
&gt;       if ((f(X1)=f(X2)) and (f(X3)=f(X2))) then
&gt;          return(true)
&gt;       fi
&gt;    od
&gt; od;
&gt; return(false)
&gt; end;
\end{verbatim}

\begin{thebibliography}{99}
\bibitem{allouche}
J.-P. Allouche \&amp; J.O. Shallit, {\it Automatic Sequences: Theory,
Applications, Generalizations}, Cambridge University Press, 2003.
\bibitem{baake}
M. Baake, V. Elser and U. Grimm, The entropy of square-free words,
{\it Math. Comput. Modelling} {\bf 26} (1997), 13--26.
\bibitem{brandenburg} F. J. Brandenburg, Uniformly growing $k$-th
power-free homomorphisms, {\it Theoret. Comput. Sci.} {\bf 23}
(1983), 69--82.
\bibitem{brinkhuis} J. Brinkhuis, Non-repetitive sequences on three symbols, {\it Quart.
J. Math. Oxford} {\bf (2) 34} (1983), 145--149.
\bibitem{carpicount1} A. Carpi, On the number of Abelian
square-free words on four letters, {\it Disc. Appl. Math}, {\bf
81} (1998) 155--167.
\bibitem{carpicount2}A. Carpi, On Abelian
squares and substitutions, {\it Theoret.\ Comp.\ Sci.}, {\bf 218}
(1999) 61--81.
\bibitem{currie}J. D. Currie, The number of binary words avoiding abelian fourth powers grows
exponentially, {\it Theoret.\ Comp.\ Sci.} To appear.
\bibitem{avoidanceproblems}J. D. Currie, Pattern avoidance: themes and
variations, {\it Theoret.\ Comp.\ Sci.}. To appear.
\bibitem{dekking} F. M. Dekking. Strongly non-repetitive sequences and
progression-free sets, {\it J. Comb. Theory Ser. A} {\bf 27}
(1979), 181-185.
\bibitem{ekhad}S. B. Ekhad and D. Zeilberger, There are more than
$2^{(n/17)}$ $n$-letter ternary square-free words, {\it J. Integer
Seq.} {\bf 1} (1998) 98.1.9.
\bibitem{erdos}  P. Erd\"{o}s, Some unsolved problems,
{\it Magyar Tud. Akad. Mat. Kutat\'o. Int. K\"ozl.} {\bf 6}
(1961), 221--254.
\bibitem{evdokimov}  A. A. Evdomikov, Strongly asymmetric sequences generated
by a finite number of symbols, {\it Dokl. Akad. Nauk. SSSR} {\bf
179} (1968), 1268--1271; {\it Soviet Math. Dokl.} {\bf 9} (1968),
536--539.
\bibitem{grimm} U. Grimm, Improved
bounds on the number of ternary square-free words, {\it J. Integer
Seq.} {\bf 4} (2001) 01.2.7.
\bibitem{keranen} V. Ker\"{a}nen, Abelian squares are
avoidable on 4 letters, {\it Automata, Languages and Programming:
Lecture notes in Computer Science} {\bf 623} (1992)
Springer-Verlag, 41--52.
\bibitem{noonan} J. Noonan \&amp; D. Zeilberger, The Goulden-Jackson cluster method: extensions, applications and
implementations, {\it J. Difference Eq. Appl.} {\bf 5} (1999),
355--377.
\bibitem{pleasants} P. A. B. Pleasants, Non-repetitive sequences,
{\it Proc. Cambridge Philos. Soc.} {\bf 68} (1970) 267--274.
\bibitem{thueI}  A. Thue,
\"{U}ber unendliche Zeichenreihen, {\it Norske Vid. Selsk. Skr. I.
Mat. Nat. Kl. Christiana} {\bf 7} (1906) 1--22.
\bibitem{thueII}  A. Thue, \"{U}ber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, {\it Norske Vid. Selsk. Skr.
I. Mat. Nat. Kl. Christiana} No. 1 (1912) 1--67.
\bibitem{xinyusun}X. Sun, New lower-bound on the number of ternary square-free
words,  {\it J. Integer Seq.} {\bf 6} (2003) 03.3.2.
\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05A20; Secondary 68R15.

\noindent \emph{Keywords: } Combinatorics on words, abelian repetitions,
enumeration.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received April 7 2004;
revised version received June 16 2004.
Published in {\it Journal of Integer Sequences}, June 19 2004.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                


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