\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 \& 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) &=& \{001002\}\\ h(1) &=&\{110112\}\\ h(2) &=&\{002212, 122002\} \end{eqnarray*} The corresponding matrix $M$ is thus \[ \left[ \begin{array}{ccc} 4&1&1\\ 1&4&1\\ 2&1&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') &=& w_1M\\ v_2 - f(c^{\prime\prime}d') + f(b^{\prime\prime}c') &=& 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') &=& w_1M\\ v_2 - f(c^{\prime\prime}d') + f(b^{\prime\prime}c') &=& 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)&=&f(b^{\prime\prime}Y_1c')-f(a^{\prime\prime}Y_1b')\\ &=&f(b^{\prime\prime}c')-f(a^{\prime\prime}b')+f(Y_2)-f(Y_1)\\ &=&f(b^{\prime\prime}c')-f(a^{\prime\prime}b')+f(Z_2)M-f(Z_1)M\\ &=&f(b^{\prime\prime}c')-f(a^{\prime\prime}b')+(f(Z_2)-f(Z_1))M\\ &=&f(b^{\prime\prime}c')-f(a^{\prime\prime}b')+w_1M\\ &=&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|> 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&\le&|u_1|\\ &=&|aX_1bX_2cX_3d|\\ &=&|a|+|X_1|+|b|+|X_2|+|c|+|X_3|+|d|\\ &\le& 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}&=&a'aX_1bX_2cX_3dd^{\prime\prime}\\ &=&a'aa^{\prime\prime}Y_1b'bb^{\prime\prime}Y_2c'cc^{\prime\prime}Y_3d'dd^{\prime\prime}\\ &\in&h(u_2) \end{eqnarray*} for some word $$u_2=AZ_1BZ_2CZ_3D \in L$$ satisfying \begin{eqnarray*} Y_i&\in& h(Z_i),\mbox{ }i=1,2,3\\ A,B,C,D &\in& \{\epsilon,0,1,2\}\\ b'bb^{\prime\prime}&\in& h(B)\\ c'cc^{\prime\prime}&\in&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') &=& w_1M\\ v_2 - f(c^{\prime\prime}d') + f(b^{\prime\prime}c') &=& 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|<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} >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]]; >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]]; >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]];} >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} > 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. > a:=template[1];b:=template[2];c:=template[3]; > d:=template[4];v1:=template[5];v2:=template[6]; > parentSet:={}; > for A in split[a] do for B in split[b] do for C in split[c] do > for D in split[d] do > if not((A[3]=3) or (D[3]=3)) then >> As:=A[2];Bp:=B[1];Bs:=B[2];Cp:=C[1];Cs:=C[2];Dp:=D[1]; > if ( > ((v1[1]+As[1]+Bp[1]-Bs[1]-Cp[1]+13*(v1[2]+As[2]+Bp[2]-Bs[2]-Cp[2]) > +19*(v1[3]+As[3]+Bp[3]-Bs[3]-Cp[3]) )mod 36 = 0) and > ((v2[1]+Bs[1]+Cp[1]-Cs[1]-Dp[1]+13*(v2[2]+Bs[2]+Cp[2]-Cs[2]-Dp[2]) > +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}: > w1:=[11/36*(v1[1]+As[1]+Bp[1]-Bs[1]-Cp[1])-1/36*(v1[2]+ > As[2]+Bp[2]-Bs[2]-Cp[2])-7/36*(v1[3]+As[3]+Bp[3]-Bs[3]- > Cp[3]),-1/18*(v1[1]+As[1]+Bp[1]-Bs[1]-Cp[1])+5/18*(v1[2]+ > As[2]+Bp[2]-Bs[2]-Cp[2])-1/18*(v1[3]+As[3]+Bp[3]-Bs[3]- > Cp[3]),-1/12*(v1[1]+As[1]+Bp[1]-Bs[1]-Cp[1])-1/12*(v1[2]+ > As[2]+Bp[2]-Bs[2]-Cp[2])+5/12*(v1[3]+As[3]+Bp[3]-Bs[3]- > Cp[3])]; > w2:=[11/36*(v2[1]+Bs[1]+Cp[1]-Cs[1]-Dp[1])-1/36*(v2[2]+ > Bs[2]+Cp[2]-Cs[2]-Dp[2])-7/36*(v2[3]+Bs[3]+Cp[3]-Cs[3]- > Dp[3]),-1/18*(v2[1]+Bs[1]+Cp[1]-Cs[1]-Dp[1])+5/18*(v2[2]+ > Bs[2]+Cp[2]-Cs[2]-Dp[2])-1/18*(v2[3]+Bs[3]+Cp[3]-Cs[3]- > Dp[3]),-1/12*(v2[1]+Bs[1]+Cp[1]-Cs[1]-Dp[1])-1/12*(v2[2]+ > Bs[2]+Cp[2]-Cs[2]-Dp[2])+5/12*(v2[3]+Bs[3]+Cp[3]-Cs[3]- > Dp[3])]; We will ignore parents which imply cubes > check1:=[0,0,0]; check1[A[3]+1]:=1; > check2:=[0,0,0]; if not(B[3]=3) then > check2[B[3]+1]:=1 fi; > check3:=[0,0,0]; if not(C[3]=3) then > check3[C[3]+1]:=1 fi; > check4:=[0,0,0]; check4[D[3]+1]:=1; > diff1:=check1-check2; Here 'diff1' is f(A) - f(B), for deciding if t2 implies a cube > diff2:=check2-check3; > diff3:=check3-check4; > cube:=((w1=diff1)and(w2=diff2)) or > ((w1=diff2)and(w2=diff3)); > if not(cube) then > parentSet:=parentSet union > {[A[3],B[3],C[3],D[3],w1,w2]}; > fi; > fi; > fi; > od;od;od;od; > return(parentSet); > 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}> grow:=proc(T) > seed:=T; closure:={}; > while not(seed={}) do > for t in seed do > closure:=closure union {t}; > candidatesForNewParents:=parents(t); > seed:=(seed union candidatesForNewParents) minus > closure; > od > od; > return(closure); > 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} > 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| >= 4 + |X1| +|X2| +|X3| >= 4 + 3|X1| -2, so that |X1| <= (|aWord| - 2)/3. > a:=template[1];b:=template[2];c:=template[3];d:=template[4]; > v1:=template[5];v2:=template[6];L:=length(aWord); > for L1 from 0 to (L-2)/3 do > for L2 from max(0,L1-1) to L1+1 do > for L3 from max(0,L1-1,L2-1) to min(L1+1,L2+1) do > for iStart from 1 to L-(L1+L2+L3+3) do > if ( > (numString(a)=substring(aWord,iStart..iStart)) > and (numString(b)=substring(aWord,iStart+L1+1..iStart+L1+1)) > and (numString(c)=substring(aWord,iStart+L1+L2+2..iStart+L1+L2+2)) > and (numString(d)=substring(aWord,iStart+L1+L2+L3+3..iStart+L1+L2 > +L3+3))) > then > X1:=substring(aWord,iStart+1..iStart+L1); > X2:=substring(aWord,iStart+L1+2..iStart+L1+L2+1); > X3:=substring(aWord,iStart+L1+L2+3..iStart+L1+L2+L3+2); > if ((f(X2)-f(X1)=v1) and (f(X3)-f(X2)=v2)) then > return(true) > fi > fi > od > od > od > od; > return(false) > end; \end{verbatim} For $w\in$ {\tt testSet}, we verify that no subword of $w$ realizes $t_c$ using procedure {\tt cubeOccurs}: \begin{verbatim} > cubeOccurs:=proc(aWord) > L:=length(aWord); > for L1 from 1 to L/3 do > for iStart from 1 to L-3*L1+1 do > X1:=substring(aWord,iStart..iStart+L1-1); > X2:=substring(aWord,iStart+L1..iStart+2*L1-1); > X3:=substring(aWord,iStart+2*L1..iStart+3*L1-1); > if ((f(X1)=f(X2)) and (f(X3)=f(X2))) then > return(true) > fi > od > od; > return(false) > end; \end{verbatim} \begin{thebibliography}{99} \bibitem{allouche} J.-P. Allouche \& 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 \& 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}