\chapter{BINARY CUBE-FREE WORDS}
\section{Introduction}
\begin{def1}
A word is {\bf cube-free} if it contains no factors of the form
$xxx$, where $x$ is any non-empty word.
\end{def1}
E.g. The cube-free words of length 3 over the alphabet $\{a,b\}$ are \newline
$\{ [a,a,b], [a,b,a], [a,b,b], [b,a,a], [b,a,b], [b,b,a] \}$
My Maple package Cubefree (available from {\bf \newline
http://www.math.temple.edu/$\sim$anne/cubefree.html}) can be used to derive
cube-free words on any given alphabet up to the required length. The number of
binary cube-free words of length at most n for $0 \leq n \leq 47$ are given
below.
\section{Applying the Goulden-Jackson Method}
These results were obtained by applying the Goulden-Jackson Method with all
cubes of length at most 45 as the input mistakes.
\subsection{The Sequence of Binary Cube-Free Words of length up to 47}
1, 2, 4, 6, 10, 16, 24, 36, 56, 80, 118, 174, 254, 378, 554, 802, 1168, 1716,
2502, 3650, 5324, 7754, 11320, 16502, 24054, 35058, 51144, 74540, 108664,
158372, 230800, 336480, 490458, 714856, 1041910, 1518840, 2213868,
3226896, 4703372, 6855388, 9992596, 14565048, 21229606, 30943516,
45102942, 65741224, 95822908, 139669094.
\subsection{The `Connective Constant'}
Let $a_n$ be the number of cube-free words of length $n$.
Brandenburg \cite{BRA83} proved that for $n >18$
\begin{lem}
$\{a_n\}$ is sub-multiplicative.
\end{lem}
\noindent {\bf Proof:\/} Given a cube free word of length $n+m$ if
we split it into the first $n$ letters and the last $m$ letters
both of these words must be cube-free or the original word was
not. Hence $a_{n+m} \leq a_n a_m$.
It is also worth noting that when we adjoin two cube-free words we
do not necessarily obtain a cube-free word so this is not
multiplicative.
\begin{tem}
$\mu=\lim_{n \rightarrow \infty} a_n^{1/n}$ exists and
$\mu=\liminf_{n \rightarrow \infty}a_n$.
\end{tem}
\noindent {\bf Proof:\/} See \ref{submul}.
\begin{equation}
2 \times 1.080^n<2 \times 2^{\frac{n}{9}} \leq a_n
\leq2\times1251^{\frac{n-1}{17}}<1.315\times1.522^n
\end{equation}
Thus $1.080 \leq \mu \leq 1.522$
Using the `memory-45' analog
(i.e. the corresponding sequence that enumerates words that avoid
cubes $x^3$, with $length(x) \leq 15$), that was generated using
the Maple package, up to word-length $300$, we find the rigorous
upper bound $\mu <1.457579200596766$, which improves on
Brandenburg's result.
Using Zinn's method, we also found that, assuming that $a_n \sim
n^{\theta} \mu^n$, then $\mu \approx 1.457$, and $\theta \approx
0$. Hence it is reasonable to conjecture that $a_n \sim \mu^n$,
where $\mu := \lim_{n \rightarrow \infty} a_n^{1/n} \approx
1.457$.
\section{Lower-Bounds and the Brinkhuis Method}
\subsection{Lower Bounds for Square-free Ternary Words}
Jan Brinkhuis \cite{BRI83} obtained a lower bound for the number of square-free
ternary words in the following way. He found a pair of words, $U0,V0$, on
$\{0,1,2\}$ and from these forms $U1,V1$ and $U2,V2$ all with the following
property. If $W$ is a square-free word over $\{0,1,2\}$, and $S(W)$ is obtained
by replacing all the $0$'s in $W$ with $UO$ or $VO$, the $1$'s with $U1$ or $V1$
and the $2$'s with $U2$ or $V2$ then $S(W)$ is also square-free.
\begin{lem}\label{bri}
If we can find $U0,V0,U1,V1,U2,V2$ that satisfy the above condition and are of
length $k$ then $\mu \geq 2^{\frac{1}{k-1}}$.
\end{lem}
\noindent {\bf Proof:\/} As we have two choices of what to substitute for each
of the letters of $W$
\begin{equation}
a_{kn} \geq 2^n a_n
\end{equation}
Thus
\begin{equation}
a_{kn}^{\frac{1}{kn}} \geq 2^{\frac{1}{k}}
(a_n^{\frac{1}{n}})^{\frac{1}{k}}
\end{equation}
and taking the limit with respect to $n$ we obtain
\begin{equation}
\mu \geq 2^{\frac{1}{k}} \mu^{\frac{1}{k}}
\end{equation}
which simplifies to
\begin{equation}
\mu \geq 2^{\frac{1}{k-1}}
\end{equation}
Brinkhuis chose words that were palindromes and obtained $U1$ from
$U0$ by adding $1$ mod $3$ to each letter of $U0$ and $U2$ is
obtained from $U0$ by adding $2$ mod $3$ to each letter of $U0$.
Likewise for $V1$ and $V2$. He found (by hand) such a Brinkhuis
pair ($U0$ and $V0$) of length 24. Giving lower bound of $\mu
\geq 2^{\frac{1}{23}}=1.030595545$
Zeilberger and his servant Ekhad \cite{ZE98} removed the
palindromic requirement and computerized the search for good
pairs. They thus found a Brinkhuis pair of length 18, and so
improved the lower bound to $\mu \geq 2^{\frac{1}{17}}=1.04162$.
In their paper Zeilberger and Ekhad note that the relationship between $U0, U1$
and $U2$ and between $V0, V1$ and $V2$ is not necessary and it is with this
comment in mind that I began my adaptation of the Brinkhuis method to cube-free
words.
\subsection{Lower Bounds for Cube-Free Binary Words}
\begin{tem}
The number of n-letter binary cube-free words is greater than $2^{n/8}$.
\end{tem}
This result can be obtained as a corollary of Brandenburg's result, but as my
method is different from his I will give the full details.
The goal is to find binary words $U0, U1, V0, V1$ of minimal length such that if
we take a cube-free word $W$ over the alphabet $\{0,1\}$ and substitute $U0$ or
$V0$ for the zeros and $U1$ or $V1$ for the ones the resulting word $S(W)$ will
also be cube-free.
\begin{lem}
If $U0,V0,U1,$ and $V1$ satisfy the following conditions and if $W$ is
cube-free then $S(W)$ is cube-free.
\noindent
1) All legitimate triples of $U0,V0,U1,V1$ are cube-free
\noindent 2) None of $U0,V0,U1,V1$ are non-trivial sub-words of
all the possible pairs of $U0,V0,U1,V1$
\end{lem}
\noindent
{\bf Proof}:
Clearly as $U0,V0,U1,$ and $V1$ meet condition 1 then if W is cube-free and of
length at most 3 then $S(W)$ is cube-free.
So if $S(W)$ contains a cube it has length greater than 3. For
such a word to contain a cube the pattern of at least one of
$U0,V0,U1,$ and $V1$ must be repeated elsewhere in $S(W)$. If
every time such a repetition occurs it is as $U0,V0,U1,$ and $V1$
respectively then the original word $W$ cannot of been cube-free
(contrary to assumptions). So the only way the repeat can occur
is as a sub-word of a pair of concatenated words, but condition 2
eliminates this possibility. Therefore $S(W)$ is cube-free
whenever $W$ is.
\begin{lem}
If we can find $U0,V0,U1,V1$ that satisfy the above condition and
are of length $k$ then $\mu = \lim_{n\rightarrow\infty} a_n^{1/n}
\geq 2^{\frac{1}{k-1}}$. Where $a_n$ is the number of cube-free
words of length $n$.
\end{lem}
\noindent {\bf Proof:\/} As for the lemma \ref{bri} in the
square-free case.
\medskip
\noindent
{\bf Proof of Theorem}:
It is easily verified (by hand , or more quickly by computer) that
$U0=[0, 1, 1, 0, 0, 1, 1, 0, 1], V0=[0, 1, 1, 0, 1, 0, 0, 1,
0],U1=[1,0,0,1,1,0,0,1,0],$ and $V1=[1,0,0,1,0,1,1,0,1]$ satisfy the conditions
of the lemma. Hence $a(n) \geq 2^{1/8} \approx 1.09$
It should be noted that our words are not palindromic, but $U1$
and $V1$ can be obtained by switching 1's and 0'1 and vice-versa
in $U0$ and $V0$. Removing this condition does not seem to
produce any shorter choices for $U0,V0,U1$ and $V1$