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

\usepackage[usenames]{color}

\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{amsfonts,amstext,amsbsy,euscript}


\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prp}[thm]{Proposition}

\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{exmp}{Example}

\numberwithin{equation}{section}

\begin{document}

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

\begin{center}
\vskip 1cm {\LARGE\bf New Lower Bound On The Number of}
\vskip .2cm {\LARGE\bf Ternary Square-Free Words}
\vskip 1cm
\large
Xinyu Sun\\
Department of Mathematics\\
Temple University\\
Philadelphia, PA 19122\\
USA\\
\href{mailto:xysun@math.temple.edu}{xysun@math.temple.edu}\\
\end{center}

\vskip .2 in
\begin{center}
{\bf Abstract}

A new lower bound on the number of $n$-letter ternary 
square-free words is presented: $110^{n/42}$, which improves 
the previous best result of $65^{n/40}$.
\end{center}


\section{ Introduction}

A word $w$ is a finite sequence of letters from a certain alphabet $\Sigma$. 
The length of a word is the number of letters of the word.
Binary words are the words from a two-letter alphabet \{0, 1\}, whereas ternary words are
from a three-letter alphabet \{0, 1, 2\}.
A word is square-free if it does not contain two identical consecutive subwords (factors), 
i.e., $w$ cannot be written as $axxb$ where $a, b, x$ are words with $x$ non-empty. 

It is easy to see that there are only finitely
many binary square-free words. However, there are infinitely many ternary square-free
words. The fact was proved by utilizing what is now called 
the Prouhet-Thue-Morse sequence (see \cite{LO}).
Brinkhuis \cite{BR}, Brandenburg \cite{BG} (also in \cite{BE}), 
Zeilberger \cite{EZ} and Grimm \cite{GR}
showed that the numbers of such words of length $n$ are greater than 
$2^{n/24}$, $2^{n/21}$, $2^{n/17}$, and $65^{n/40}$ respectively.
Details on words and related topics can be found in \cite{SF} and \cite{WR}.

While the best available upper bound has been very close to the estimate
as described later, the available lower bounds still have much room for improvement.
Finding better lower bounds has posed as an algorithmic challenge, 
as well as a theoretic one. As explained later, the complexity of the algorithm
used here is likely (very) exponential.

\section{Brinkhuis Triples}

We denote $a(n)$ to be the number of ternary square-free words of length $n$. It is easy to
see that 
\begin{equation}
a(m+n) \le a(m)a(n)
\end{equation}
for all $m, \ n \ge 0$, which implies (see in \cite{BE}) the existence of the limit 
\begin{equation}
s := \lim_{n\rightarrow\infty}{a(n)^{1/n}},
\end{equation}
which is also called the growth rate or ``connective constant" of ternary square-free words.

It is widely believed that the available upper bounds are very close to the actual value
of $s$. In fact, it has been estimated by Noonan and Zeilberger \cite{NZ} 
that $s \approx 1.302$ using the Zinn-Justin method,
and they have also proved that $s \le 1.30201064$ 
by implementing the Goulden-Jackson method. 

\begin{defn}
An $n$-Brinkhuis $k$-triple is three sets of words 
$\mathcal{B}$ = \{$\mathcal{B}^0$, $\mathcal{B}^1$, $\mathcal{B}^2$\}, 
$\mathcal{B}^i = \{w^i_j | 1 \le j \le k\}$, where $w^i_j$ are square-free words of length $n$, such that
for any square-free word $i_1i_2i_3$, $0 \le i_1, i_2, i_3 \le 2$, and any $1 \le j_1, j_2, j_3 \le k$, the word 
$w^{i_1}_{j_1}w^{i_2}_{j_2}w^{i_3}_{j_3}$ of length $3n$ is also square-free.
\end{defn}

Based on an $n$-Brinkhuis $k$-triple, we can define 
the following set of uniformly growing morphisms:

\begin{equation}
\rho = \left\{ 
\begin{array}{c}		
0 \rightarrow w^0_{j_0},\ 1 \le j_0 \le k;	\\ [2mm]
1 \rightarrow w^1_{j_1},\ 1 \le j_1 \le k;	\\ [2mm]
2 \rightarrow w^2_{j_2},\ 1 \le j_2 \le k.
\end{array}
\right.
\end{equation}

As proven in \cite{BG}, \cite{CR} and \cite{LE}, $\rho$ are square-free morphisms, 
i.e., they map each square-free word of length $m$ onto $k^m$ different images of 
square-free words of length $nm$.

Therefore, the existence of an $n$-Brinkhuis $k$-triple indicates that 
\begin{equation}
\frac{a(mn)}{a(m)} \ge k^m
\end{equation}
for any $m \ge 1$, which implies
\begin{equation}
s^{n-1} = \lim_{n\rightarrow\infty}{\left(\frac{a(mn)}{a(m)}\right)^{1/m}} \ge k,
\end{equation}
and thus yields the lower bound of $s \ge k^{1/{(n-1)}}$.

Given the permutation $\tau$ = (0, 1, 2), we can have

\begin{defn}
A quasi-special $n$-Brinkhuis $k$-triple is an $n$-Brinkhuis $k$-triple 
such that $\mathcal{B}^1 = \tau(\mathcal{B}^0)$, $\mathcal{B}^2 = \tau(\mathcal{B}^1)$.
\end{defn}

\begin{defn}
A special $n$-Brinkhuis $k$-triple is a quasi-special $n$-Brinkhuis $k$-triple 
such that $w \in \mathcal{B}^0$ implies $\overline{w} \in \mathcal{B}^0$, 
where $\overline{w}$ is the reversion of $w$.
\end{defn}

Grimm\cite{GR} was able to construct a special 41-Brinkhuis 65-triple, 
hence proved $s \ge 65^{1/40}$.

\section{Main Results}

\begin{defn}
A word $w$ is admissible if $(w, \tau(w), \tau^2(w))$ is a quasi-special 
Brinkhuis 1-triple by itself.
\end{defn}

\begin{defn}
An optimal quasi-special (special) $n$-Brinkhuis $k$-triple is a quasi-special 
(special) $n$-Brinkhuis $k$-triple such that any quasi-special (special) 
$n$-Brinkhuis $l$-triple has $l \le k.$
\end{defn}

To find the optimal quasi-special $n$-Brinkhuis triples, 
we only need to find the set 
of all admissible words of length $n$, and its largest subset 
in which any three words $w_1, w_2, w_3$ can form a quasi-special $n$-Brinkhuis 3-triple,
i.e., $\{\{w_1$, $w_2$, $w_3\}$, $\{\tau(w_1)$, $\tau(w_2)$, $\tau(w_3)\}$, 
$\{\tau^2(w_1)$, $\tau^2(w_2)$, $\tau^2(w_3)\}\}$ is a quasi-special $n$-Brinkhuis 3-triple.
A Maple package was written to calculate such words and sets. The results are listed below.

\begin{prp}
Special $n$-Brinkhuis triples yield the best possible results for each $13 \le n \le 20$,
and quasi-special Brinkhuis triples do not yield better results than 
special $n$-Brinkhuis triples for each $13 \le n \le 39$, except 37.
\end{prp}

\begin{center}
%\begin{table}
\begin{tabular}{rp{0.5in}rp{0.5in}rp{0.5in}rp{0.5in}r}	\hline
$n$	&amp;&amp; $b_1$ &amp;&amp; $k_1$	&amp;&amp; $b_2$	&amp;&amp; $k_2$	\\	\hline
13	&amp;&amp;	1	&amp;&amp;	1	&amp;&amp;	1	&amp;&amp;	1	\\
14	&amp;&amp;	0	&amp;&amp;	0	&amp;&amp;	0	&amp;&amp;	0	\\
15	&amp;&amp;	0	&amp;&amp;	0	&amp;&amp;	0	&amp;&amp;	0	\\
16	&amp;&amp;	0	&amp;&amp;	0	&amp;&amp;	0	&amp;&amp;	0	\\
17	&amp;&amp;	1	&amp;&amp;	1	&amp;&amp;	1	&amp;&amp;	1	\\
18	&amp;&amp;	1	&amp;&amp;	2	&amp;&amp;	1	&amp;&amp;	2	\\
19	&amp;&amp;	1	&amp;&amp;	1	&amp;&amp;	1	&amp;&amp;	1	\\
20	&amp;&amp;	0	&amp;&amp;	0	&amp;&amp;	0	&amp;&amp;	0	\\
21	&amp;&amp;	0	&amp;&amp;	0	&amp;&amp;	0	&amp;&amp;	0	\\
22	&amp;&amp;	0	&amp;&amp;	0	&amp;&amp;	0	&amp;&amp;	0	\\
23	&amp;&amp;	1	&amp;&amp;	3	&amp;&amp;	1	&amp;&amp;	3	\\
24	&amp;&amp;	5	&amp;&amp;	2	&amp;&amp;	3	&amp;&amp;	2	\\
25	&amp;&amp;	1	&amp;&amp;	5	&amp;&amp;	1	&amp;&amp;	5	\\
26	&amp;&amp;	2	&amp;&amp;	2	&amp;&amp;	2	&amp;&amp;	2	\\
27	&amp;&amp;	1	&amp;&amp;	3	&amp;&amp;	1	&amp;&amp;	3	\\
28	&amp;&amp;	4	&amp;&amp;	4	&amp;&amp;	2	&amp;&amp;	4	\\
29	&amp;&amp;	2	&amp;&amp;	6	&amp;&amp;	2	&amp;&amp;	6	\\
30	&amp;&amp;	1	&amp;&amp;	8	&amp;&amp;	1	&amp;&amp;	8	\\
31	&amp;&amp;	4	&amp;&amp;	7	&amp;&amp;	2	&amp;&amp;	7	\\
32	&amp;&amp;	1	&amp;&amp;	8	&amp;&amp;	1	&amp;&amp;	8	\\
33	&amp;&amp;	1	&amp;&amp;	12	&amp;&amp;	1	&amp;&amp;	12	\\
34	&amp;&amp;	33	&amp;&amp;	10	&amp;&amp;	5	&amp;&amp;	10	\\
35	&amp;&amp;	2	&amp;&amp;	18	&amp;&amp;	2	&amp;&amp;	18	\\
36	&amp;&amp;	1	&amp;&amp;	32	&amp;&amp;	1	&amp;&amp;	32	\\
37	&amp;&amp;	66	&amp;&amp;	32	&amp;&amp;	24	&amp;&amp;	31	\\
38	&amp;&amp;	9	&amp;&amp;	28	&amp;&amp;	3	&amp;&amp;	28	\\
39	&amp;&amp;	1	&amp;&amp;	32	&amp;&amp;	1	&amp;&amp;	32	\\
40	&amp;&amp;		&amp;&amp;		&amp;&amp;	2	&amp;&amp;	48	\\
41	&amp;&amp;		&amp;&amp;		&amp;&amp;	8	&amp;&amp;	65	\\
42	&amp;&amp;		&amp;&amp;		&amp;&amp;	4	&amp;&amp;	76	\\
43	&amp;&amp;		&amp;&amp;		&amp;&amp;	2	&amp;&amp;	110	\\	\hline 
	&amp;&amp;		&amp;&amp;		&amp;&amp;		&amp;&amp;		\\	[-1mm]
\end{tabular}

%\vspace{2mm}
%\caption{Results of optimal quasi-special and special Brinkhuis triples} \label{tbl_result}
%\end{table}
\end{center}

%In the Table \ref{tbl_result}, $n$ is the length of the words; 
In the table above, $n$ is the length of the words; 
$b_1$ and $k_1$ are the numbers of all available optimal quasi-special Brinkhuis triples and 
the numbers of elements in the triples;
$b_2$ and $k_2$ are those of the special Brinkhuis triples. 
Notice the numbers of the triples and their sizes do not always grow as $n$ does,
and occasionally there are extraordinary amount of the triples for certain word lengths, 
i.e., 34 and 37.

Although there are often more choices for the regular 
and quasi-special Brinkhuis triples than 
the special Brinkhuis triples as listed above, none of them can be combined 
to form larger triples. 
And the exception of $n= 37$ has hardly any significance because the results 
are superceded by the 36-Brinkhuis 32-triples already.
These results strongly suggest that the special 
Brinkhuis triples will generally yield the best results regardless of $n$.

It is reasonable to believe that there exist $n$-Brinkhuis triples that are
not quasi-special when $ n &gt; 20$, or quasi-special $n$-Brinkhuis triples
that are not special when $n &gt; 39$. However, as explained in the proof of the 
following proposition, it is vary hard to find such triples due to the complexity.

\begin{prp}
The following 43-Brinkhuis 110-triple exists, and thus shows 
$s \ge 110^{1/42} = 1.118419 \ldots &gt; 65^{1/40} = 1.109999 \ldots$:
\begin{center}
\begin{tabular}{rll}
	\{	&amp; 0120212012102120102012102010212012102120210, &amp; \\ 
		&amp; 0120212010210120102012102010210120102120210, &amp; \\ 
		&amp; 0120212010201210212021020120212012102120210, &amp; \\ 
		&amp; 0120212012102120210201202120121020102120210, &amp; \\ 
		&amp; 0120210201210120210121020120212012102120210, &amp; \\ 
		&amp; 0120212012102120210201210120210121020120210, &amp; \\ 
		&amp; 0120210201210120102120210120212012102120210, &amp; \\ 
		&amp; 0120212012102120210120212010210121020120210, &amp; \\ 
		&amp; 0120210201210120212010210120212012102120210, &amp; \\ 
		&amp; 0120212012102120210120102120210121020120210, &amp; \\ 
		&amp; 0120212010201210212010210120212012102120210, &amp; \\ 
		&amp; 0120212012102120210120102120121020102120210, &amp; \\ 
		&amp; 0120212010210121021201210120212012102120210, &amp; \\ 
		&amp; 0120212012102120210121021201210120102120210, &amp; \\ 
		&amp; 0120212012101201021201210120212012102120210, &amp; \\ 
		&amp; 0120212012102120210121021201021012102120210, &amp; \\ 
		&amp; 0120212010210121021202102010212012102120210, &amp; \\ 
		&amp; 0120212012102120102012021201210120102120210, &amp; \\ 
		&amp; 0120212012101201021202102010212012102120210, &amp; \\ 
		&amp; 0120212012102120102012021201021012102120210, &amp; \\ 
		&amp; 0120212010210120102012102010212012102120210, &amp; \\ 
		&amp; 0120212012102120102012102010210120102120210, &amp; \\ 
		&amp; 0120210201210120102012102010212012102120210, &amp; \\ 
		&amp; 0120212012102120102012102010210121020120210, &amp; \\ 
		&amp; 0120210201210120212012102010212012102120210, &amp; \\ 
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{rll}
		&amp; 0120212012102120102012102120210121020120210, &amp; \\ 
		&amp; 0120212010201210212012102010212012102120210, &amp; \\ 
		&amp; 0120212012102120102012102120121020102120210, &amp; \\ 
		&amp; 0120210201210212021012102010212012102120210, &amp; \\ 
		&amp; 0120212012102120102012101202120121020120210, &amp; \\ 
		&amp; 0120212012101201021012102010212012102120210, &amp; \\ 
		&amp; 0120212012102120102012101201021012102120210, &amp; \\ 
		&amp; 0120212010201210201021012010212012102120210, &amp; \\ 
		&amp; 0120212012102120102101201020121020102120210, &amp; \\ 
		&amp; 0120212010212021020121012010212012102120210, &amp; \\ 
		&amp; 0120212012102120102101210201202120102120210, &amp; \\ 
		&amp; 0120212010210121020121012010212012102120210, &amp; \\ 
		&amp; 0120212012102120102101210201210120102120210, &amp; \\ 
		&amp; 0120212012101201021202102012021012102120210, &amp; \\ 
		&amp; 0120212012101202102012021201021012102120210, &amp; \\ 
		&amp; 0120210201210120212012102012021012102120210, &amp; \\ 
		&amp; 0120212012101202102012102120210121020120210, &amp; \\ 
		&amp; 0120212010201210212012102012021012102120210, &amp; \\ 
		&amp; 0120212012101202102012102120121020102120210, &amp; \\ 
		&amp; 0120212010210120102120121012021012102120210, &amp; \\ 
		&amp; 0120212012101202101210212010210120102120210, &amp; \\ 
		&amp; 0120210201210120102120121012021012102120210, &amp; \\ 
		&amp; 0120212012101202101210212010210121020120210, &amp; \\ 
		&amp; 0120212010210120102120210201021012102120210, &amp; \\ 
		&amp; 0120212012101201020120212010210120102120210, &amp; \\ 
		&amp; 0120210201210120102120210201021012102120210, &amp; \\ 
		&amp; 0120212012101201020120212010210121020120210, &amp; \\ 
		&amp; 0120212010210121021201210201021012102120210, &amp; \\ 
		&amp; 0120212012101201020121021201210120102120210, &amp; \\ 
		&amp; 0120212010210120102012021201021012102120210, &amp; \\ 
		&amp; 0120212012101201021202102010210120102120210, &amp; \\ 
		&amp; 0120210201210120102012021201021012102120210, &amp; \\ 
		&amp; 0120212012101201021202102010210121020120210, &amp; \\ 
		&amp; 0120210201210212021012021201021012102120210, &amp; \\ 
		&amp; 0120212012101201021202101202120121020120210, &amp; \\ 
		&amp; 0120210201210120210121021201021012102120210, &amp; \\ 
		&amp; 0120212012101201021201210120210121020120210, &amp; \\ 
		&amp; 0120212010210120102012101201021012102120210, &amp; \\ 
		&amp; 0120212012101201021012102010210120102120210, &amp; \\ 
		&amp; 0120210201210120212012101201021012102120210, &amp; \\ 
		&amp; 0120212012101201021012102120210121020120210, &amp; \\ 
		&amp; 0120212010201210212012101201021012102120210, &amp; \\ 
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{rll}
		&amp; 0120212012101201021012102120121020102120210, &amp; \\ 
		&amp; 0120210201210120212012102012021020102120210, &amp; \\ 
		&amp; 0120212010201202102012102120210121020120210, &amp; \\ 
		&amp; 0120212010201210212012102012021020102120210, &amp; \\ 
		&amp; 0120212010201202102012102120121020102120210, &amp; \\ 
		&amp; 0120212010210120102120121012021020102120210, &amp; \\ 
		&amp; 0120212010201202101210212010210120102120210, &amp; \\ 
		&amp; 0120210201210120102120121012021020102120210, &amp; \\ 
		&amp; 0120212010201202101210212010210121020120210, &amp; \\ 
		&amp; 0120210201210212012101201020121020102120210, &amp; \\ 
		&amp; 0120212010201210201021012102120121020120210, &amp; \\ 
		&amp; 0120210201210212012101202120121020102120210, &amp; \\ 
		&amp; 0120212010201210212021012102120121020120210, &amp; \\ 
		&amp; 0120212010210120102012102120121020102120210, &amp; \\ 
		&amp; 0120212010201210212012102010210120102120210, &amp; \\ 
		&amp; 0120210201210212021012102120121020102120210, &amp; \\ 
		&amp; 0120212010201210212012101202120121020120210, &amp; \\ 
		&amp; 0120210201210212021020102120121020102120210, &amp; \\ 
		&amp; 0120212010201210212010201202120121020120210, &amp; \\ 
		&amp; 0120212010201210120102120210121020102120210, &amp; \\ 
		&amp; 0120212010201210120212010210121020102120210, &amp; \\ 
		&amp; 0120210201210212021020120210121020102120210, &amp; \\ 
		&amp; 0120212010201210120210201202120121020120210, &amp; \\ 
		&amp; 0120212010210120102120210201202120102120210, &amp; \\ 
		&amp; 0120212010212021020120212010210120102120210, &amp; \\ 
		&amp; 0120210201210120102120210201202120102120210, &amp; \\ 
		&amp; 0120212010212021020120212010210121020120210, &amp; \\ 
		&amp; 0120212010210121021201210201202120102120210, &amp; \\ 
		&amp; 0120212010212021020121021201210120102120210, &amp; \\ 
		&amp; 0120212010210121021202102010210120102120210, &amp; \\ 
		&amp; 0120212010210120102012021201210120102120210, &amp; \\ 
		&amp; 0120210201210120102012102010210120102120210, &amp; \\ 
		&amp; 0120212010210120102012102010210121020120210, &amp; \\ 
		&amp; 0120210201210120212012102010210120102120210, &amp; \\ 
		&amp; 0120212010210120102012102120210121020120210, &amp; \\ 
		&amp; 0120210201210212021012102010210120102120210, &amp; \\ 
		&amp; 0120212010210120102012101202120121020120210, &amp; \\ 
		&amp; 0120210201210120102012021201210120102120210, &amp; \\ 
		&amp; 0120212010210121021202102010210121020120210, &amp; \\ 
		&amp; 0120210201210212021012021201210120102120210, &amp; \\ 
		&amp; 0120212010210121021202101202120121020120210, &amp; \\ 
		&amp; 0120210201210120210121021201210120102120210, &amp; \\ 
		&amp; 0120212010210121021201210120210121020120210 &amp; \} \\
\end{tabular}
\end{center}
\end{prp}

\noindent{\bf Proof:} Each admissible word is of length at least 13 and of the form
either 
$012021\cdots120210$ or $012102\cdots201210$ as proved by Grimm \cite{GR}.
So we first find all the square-free words of length $n-12$, attach the two pairs
of prefixes and suffixes to these words, 
then determine if the results are square-free and admissible words,
and label them from 1 to $m$, where $m$ is the total number of such words.
The next step is to find all quasi-special (special) Brinkhuis 3-triples
and replace the words with the labels we just assigned to them. Thus each
triple correspond to a unique ordered list of three different integers, 
and we have created a set of lists of integers $S$. Note that if the square-free words
of length $n-12$ are known, the rest of the process above only take polynomial time.
Now the problem is reduced to find the largest subset $T$ of $\{1, \ldots, m\}$
so that the list of any three elements of $T$ is an element of $S$. 
Such a question is obviously NP, because the certificate will be the solution itself,
and the time required to verify the certificate will be  
$O( \binom{n}{3} )$, thus polynomial. 
Fortunately, we are not obliged to tell how long it takes to get the certificate.

We now create a graph $G$ so that each element in $S$ is a vertex
of $G$, and any two vertices are connected if and only if any combination of 
three different numbers from the two lists can form a quasi-special (special) Brinkhuis 3-triple.
For example, if $[1,2,3]$ and $[1,2,4]$ are vertices of the graph, they can be connected
if and only if $[1,3,4]$ and $[2,3,4]$ are vertices of the graph too. And in this case,
the four vertices will form a complete graph. Now we have reduced the problem into
finding the largest complete subgraph of a graph, which is known to be NP-complete, 
in polynomial time.
Although what we did does not imply the original problem to be NP-complete, it does shed
some light on how to solve the problem: we will use the backtracking method to find the largest
Brinkhuis triple. 

We say a number $i$ is compatible with a list of numbers $i_1, \ldots, i_n$ 
if any three words chosen from the corresponding words $w_i, w_{i_1}, \ldots, w_{i_n}$ 
can form a quasi-special (special) Brinkhuis 3-triple.

Assuming all the numbers in the vertices are ordered increasingly,
we try to construct the largest quasi-special (special) Brinkhuis triples recursively:
We start with the pair of numbers, $a_1$ and $a_2$, who has the largest set 
of compatible numbers of all pairs of numbers in $\{1, \ldots, m\}$.
After we have a list $a_1, \ldots, a_{n-1}$ such that every three numbers in the list
can form a quasi-special (special) Brinkhuis 3-triple, we try to find $a_n$
as the number such that $a_{n}$ is compatible with $a_1, \ldots, a_{n-1}$, and
$a_1, \ldots, a_{n}$ has the largest possible set of compatible numbers. 
If there is a tie, we choose the smallest possible number. 
Once we cannot add another number to the current list of $a_1, \ldots, a_n$, 
we have found a ``locally optimal" Brinkhuis $n$-triple. 
We then backtrack to $a_{n-1}$ and search for the next best choice of $a_n$.
When all such choices are analyzed, we backtrack to $a_{n-2}$. 
We repeat the process until we backtrack to $a_1$ and $a_2$, 
when we try the pair of numbers who has the next largest set of compatible numbers.
We will continue until all the possibilities are considered. 
Of course, we can always break out of the search if the size of the list of numbers found 
plus the number of compatible numbers available is less than the best known 
size of the triples at the time.

The complexity of searching the largest complete subgraph of $n$ vertices
is equivalent to searching the largest independent set of vertices
of the complement of the graph, 
whose {\em average} rate of growth is subexponential, i.e., $O(n^{\log n})$. 
However, the exact amount of labor required 
for a specific kind of graphs can be very exponential. 
Theoretically, we can take advantage of the special structure of the graphs
to increased the performance: if vertices $[1,2,3]$ and $[4,5,6]$ are connected, 
there is automatically a complete subgraph of 20 vertices, 
namely any combinations of three numbers from 1 to 6. 
But such an approach will use
recursive programming, which would have required exponential space 
and thus is impractical. Unless we can find other methods to find the lower bound,
using Brinkhuis triples cannot provide must better results, even with more
powerful (multi-processor) computers. Unfortunately, this is the best method known yet, 
if not the only one.

The Maple package and the results on optimal Brinkhuis triples
are all available at 
\href{http://www.math.temple.edu/~xysun/ternarysf/ternary_square_free.htm}{\tt http://www.math.temple.edu/$\sim$xysun/ternarysf/ternary\_square\_free.htm}.


\section{Acknowledgement}

Many thanks to Doron Zeilberger for his encouragements, to Uwe Grimm for pointing out
an error in the first attempt, and to 
Li Zhang for his useful discussions and comments during the development 
of the programs. Also thanks to the referees who provided suggestions that
made this paper more informative and readable.

\makeatletter \renewcommand{\@biblabel}[1]{\hfill#1.}\makeatother

\begin{thebibliography}{2}

\bibitem{BE} M. Baake, V. Elaser and U. Grimm, The entropy of square-free words, 
	{\em Math. Comput. Modelling} \textbf{26} (1997), 13--26.

\bibitem{BG} F.-J. Brandenburg, Uniformly growing $k^{th}$ power-free homomorphisms, 
	{\em Theoret. Comput. Sci.} \textbf{23} (1983), 69--82.

\bibitem{BR}  J. Brinkhuis, Nonrepetitive sequences on three symbols, 
	{\em Quart. J. Math. Oxford} \textbf{34} (1983), 145--149.

\bibitem{CR} M. Crochemore, Sharp characterizations of squarefree morphisms, 
	{\em Theoret. Comput. Sci.} \textbf{18} (1982), 221--226.

\bibitem{EZ} S. B. Ekhad and D. Zeilberger, There are more than $2\sp {n/17}$ $n$-letter 
	ternary square-free words, {\em J. Integer Seq.} \textbf{1} (1998), Article 98.1.9.

\bibitem{SF} S. Finch, Pattern-free word constants, 
\href{http://pauillac.inria.fr/algo/bsolve/constant/words/words.html}{\tt http://pauillac.inria.fr/algo/bsolve/constant/words/words.html}

\bibitem{NZ} John Noonan and Doron Zeilberger, The Goulden-Jackson cluster method: 
	extensions, applications and implementations, {\em J. Differ. Equations Appl.}
	\textbf{5} (1999), 355--377.

\bibitem{GR} Uwe Grimm, Improved bounds on the number of ternary square-free words, 
	{\em J. Integer Seq.} \textbf{4} (2001), Article 01.2.7.

\bibitem{LE} Michel Leconte, A characterization of power-free morphisms, 
	{\em Theoret. Comput. Sci.} \textbf{38} (1985), 117--122.

\bibitem{LO} M. Lothaire, {\em Combinatorics on Words}, Addison-Wesley, 1983.

\bibitem{WR} Wolfram Research, Squarefree word, 
	\href{http://mathworld.wolfram.com/SquarefreeWord.html}{\tt http://mathworld.wolfram.com/SquarefreeWord.html}

\end{thebibliography}

\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords: square-free, ternary, word, Brinkhuis triple}


\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip


\vspace*{+.1in}
\noindent
Received November 21, 2002;
revised version received  August 1, 2003;
Published in {\it Journal of Integer Sequences},
August 18, 2003.
\bigskip
\hrule
\bigskip

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




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