\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{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

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

\begin{center}
\vskip 1cm{\LARGE\bf 
Efficient Lower Bounds on the Number \\
\vskip .1in
of Repetition-free Words
}
\vskip 1cm
{\large
Roman Kolpakov\footnote{This work is supported 
by the program of the President of the Russian Federation 
for supporting of young researchers and scientific 
schools (Grants MD--3635.2005.1 and NSh--5400.2006.1)
and the Russian Foundation for Fundamental Research 
(Grant 05--01--00994).}\\
Lomonosov Moscow State University \\ 
Vorobjovy Gory \\
119992 Moscow \\
Russia \\
\href{mailto:foroman@mail.ru}{\tt foroman@mail.ru}
}
\end{center}

\vskip 1cm

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

\begin{abstract}
We propose a new effective method for obtaining lower bounds on the 
number of repetition-free words over a finite alphabet.
\end{abstract}

%\newtheorem{proposition}{Proposition}

\section{Introduction}

Repetition-free words over finite alphabets are a traditional object of 
research in combinatorics of words. A word~$w$ over an alphabet~$\Sigma$ 
is a finite sequence $a_1\cdots a_n$ of symbols from~$\Sigma$. The number~$n$
is called the {\it length} of~$w$ and is denoted by $|w|$. The symbol
$a_i$ of~$w$ is denoted by $w[i]$. A word $a_i\cdots a_j$, where $1\le 
i\le j\le n$, is called a {\it factor} of~$w$ and is denoted by $w[i:j]$. 
For any $i=1,\ldots,n$ the factor $w[1:i]$ ($w[i:n]$) is called a {\it prefix} 
(a {\it suffix}) of~$w$. A positive integer $p$ is called  a {\it period} of~$w$ 
if $a_i=a_{i+p}$ for each $i=1,\ldots ,n-p$. If $p$ is the minimal period 
of~$w$, the ratio $n/p$ is called the {\it exponent} of~$w$. Two words 
$w',w''$ over~$\Sigma$ are called {\it isomorphic} if $|w'|=|w''|$ and 
there exists a bijection $\sigma:\Sigma\longrightarrow\Sigma$ such that 
$w''[i]=\sigma (w'[i])$, $i=1,\ldots,|w'|$. The set of all words 
over~$\Sigma$ is denoted by $\Sigma^*$.

For any finite set~$A$ we denote by $|A|$ the number of elements of~$A$. 
Let $W$ be an arbitrary set of words. This set is called {\it factorial}
if for any word~$w$ from~$W$ all factors of~$w$ are also contained in~$W$.
We denote by $W(n)$ the subset of~$W$ consisting of all words of length~$n$. 
If $W$ is factorial then it is not difficult to show (see, e.g.,~\cite{Brink, 
BaElGr}) that there exists the limit $\lim_{n\to\infty} \sqrt[n]{|W(n)|}$
which is called the {\it growth rate} of words from~$W$. For any word~$v$ 
and any $n\ge |v|$ we denote by $W^{(v)}(n)$ the set of all words from $W(n)$ 
which contain~$v$ as a suffix. 

By a {\it repetition} we mean any word of exponent greater than~1.
The best known example of a repetition is a {\it square}; that is,
a word of the form $uu$, where $u$ is an arbitrary nonempty word.
Avoiding ambiguity\footnote{Note that the period of a square is not
necessarily the minimal period of this word.}, by the {\it period} 
of the square $uu$ we mean the length of~$u$. In an analogous way, 
a {\it cube} is a word of the form $uuu$ for a nonempty word~$u$,
a the {\it period} of this cube is also the length of~$u$. A word
is called {\it square-free} ({\it cube-free}) if it contains no squares
(cubes) as factors. It is easy to see that there are no binary square-free 
words of length more than~3. On the other hand, by the classical results
of Thue~\cite{Thue06,Thue12}, there exist ternary square-free words of 
arbitrary length and binary cube-free words of arbitrary length. If we 
denote by $S^{\langle\mbox{sf}\rangle}(n)$ the number of ternary square-free 
words of length~$n$ and by $S^{\langle\mbox{cf}\rangle}(n)$ the number 
of binary cube-free words of length~$n$, we then have that
$S^{\langle\mbox{sf}\rangle}(n)>0$ and $S^{\langle\mbox{cf}\rangle}(n)>0$
for any~$n$. For ternary square-free words this result was strengthened
by Dejean in~\cite{Dejan}. She found ternary words of arbitrary length
which have no factors with exponents greater than $7/4$. On the other hand, 
she showed that any long enough ternary word contains a factor with an
exponent greater than or equal to $7/4$. Thus, the number $7/4$ is the
minimal limit for exponents of prohibited factors in arbitrarily long
ternary words. For this reason we call ternary words having no factors 
with exponents greater than $7/4$ {\it minimally repetitive} ternary
words. Dejean conjectured also that the minimal limit for exponents of 
prohibited factors in arbitrarily long words over a $k$-letter alphabet
is equal to $7/5$ for $k=4$ and $k/k-1$ for $k\ge 5$. This conjecture
was proved for $k=4$ by Pansiot~\cite{Pans}, for $5\le k\le 11$ 
by Moulin Ollagnier~\cite{Olag}, for $12\le k\le 14$ by Mohammad-Noori
and Currie~\cite{Moh-Noor}, and for $k\ge 38$ by Carpi~\cite{Carpi}. 
Denote by $S^{\langle\mbox{lf}\rangle}(n)$ the number of minimally repetitive 
ternary words of length~$n$. It follows from the result of Dejean that 
$S^{\langle\mbox{lf}\rangle}(n)>0$ for any~$n$.

Note that the set of all ternary square-free words, the set of all
binary cube-free words, and the set of all minimally repetitive 
ternary words are factorial. So there exist the growth rates
$\gamma^{\langle\mbox{sf}\rangle}=\lim_{n\to\infty} 
\sqrt[n]{S^{\langle\mbox{sf}\rangle}(n)}$,
$\gamma^{\langle\mbox{cf}\rangle}=\lim_{n\to\infty} 
\sqrt[n]{S^{\langle\mbox{cf}\rangle}(n)}$,
$\gamma^{\langle\mbox{lf}\rangle}=\lim_{n\to\infty} 
\sqrt[n]{S^{\langle\mbox{lf}\rangle}(n)}$ of words from these sets. 
Brandenburg proved in~\cite{Brand} that the values 
$S^{\langle\mbox{sf}\rangle}(n)$ and $S^{\langle\mbox{cf}\rangle}(n)$ 
grew exponentially with~$n$, namely, $S^{\langle\mbox{sf}\rangle}(n)\ge 
6\cdot 1.032^n$  and $S^{\langle\mbox{cf}\rangle}(n)\ge 2\cdot 1.080^n$, 
i.~e. $\gamma^{\langle\mbox{sf}\rangle}\ge 1.032$ and $\gamma^{\langle
\mbox{cf}\rangle}\ge 1.080$. Later the lower bound for $\gamma^{\langle
\mbox{sf}\rangle}$ was improved consecutively\footnote{A review of
results on the estimations for the number of repetition-free words
can be found in~\cite{Berst}.} by Ekhad, Zeilberger, Grimm, and Sun
in~\cite{EkhZeil,Grimm,Sun}. The best upper bounds known at present
$\gamma^{\langle\mbox{sf}\rangle}<1.30178858$ and 
$\gamma^{\langle\mbox{cf}\rangle}<1.4576$ are obtained by Ochem and
Edlin in \cite{OchemWOWA} and~\cite{Edlin} respectively. In~\cite{OchemTIA}
Ochem established the exponential growth of the number of minimally
repetitive words over either a three-letter or a four-letter
alphabet. However, this result does not give any significant lower 
bound for $\gamma^{\langle\mbox{lf}\rangle}$.

In~\cite{WOWA} we proposed a new method for obtaining lower bounds on 
the number of repetition-free words. This method is essentially based on 
inductive estimation of the number of words which contain repetitions as 
factors. Using this method, we obtained the bounds $\gamma^{\langle\mbox{sf}
\rangle}\ge 1.30125$ and $\gamma^{\langle\mbox{cf}\rangle}\ge 1.456975$. 
The main drawback of the proposed method was the large size of computer 
computations required. In particular, for this reason we did not
manage to obtain
a lower bound for $\gamma^{\langle\mbox{lf}\rangle}$ by the proposed method.
In this paper we propose a modification of the given method which requires
a much less size of computer computations. Using this modification,
we obtain the bounds $\gamma^{\langle\mbox{sf}\rangle}\ge 1.30173$, 
$\gamma^{\langle\mbox{lf}\rangle}\ge 1.245$, and $\gamma^{\langle\mbox{cf}
\rangle}\ge 1.457567$. Comparing the obtained lower bounds for $\gamma^{\langle
\mbox{sf}\rangle}$ and $\gamma^{\langle\mbox{cf}\rangle}$ with the known upper 
bounds, one can conclude that we have estimated $\gamma^{\langle\mbox{sf}\rangle}$ 
and $\gamma^{\langle\mbox{cf}\rangle}$ within a precision of $0.0001$, which 
demonstrates the high efficiency of the proposed modification.


\section{Estimation for the number of ternary square-free words}

For obtaining a lower bound on $\gamma^{\langle\mbox{sf}\rangle}$ we 
consider the alphabet $\Sigma_3=\{0,1,2\}$. Denote the set of all 
square-free words from~$\Sigma^*_3$ by~${\cal F}$. Let $m$ be a 
natural number, $m>2$, and $w',w''$ be two words from ${\cal F}(m)$.
We call the word $w''$ a {\it descendant} of the word $w'$ if 
$w'[2:m]=w''[1:m-1]$ and $w'w''[m]=w'[1]w''\in {\cal F}(m+1)$.
The word $w'$ is called in this case an {\it ancestor} of the 
word~$w''$. Further, we introduce a notion of closed words in 
the following inductive way. A word $w$ from ${\cal F}(m)$ is 
called {\it right closed} ({\it left closed}) if and only if 
this word satisfies one of the two following conditions:

(a) {\bf Basis of induction.} $w$ has no descendants (ancestors);

(b) {\bf Inductive step.} All descendants (ancestors) of~$w$
are right closed (left closed).

\noindent
A word is {\it closed} if it is either right closed or left closed.
Denote by ${\cal L}_m$ the set of all words from $\Sigma^*_3$
which do not contain closed words from ${\cal F}(m)$ as factors. 
By ${\cal F}_m$ we denote the set of all square-free words from 
${\cal L}_m$. Note that a word $w$ is closed if and only if any 
word isomorphic to~$w$ is also closed. So we have the following
obvious fact.

\begin{proposition}
For any isomorphic words $w',w''$ and any $n\ge |w'|$ the 
equality $|{\cal F}_m^{(w')}(n)|=|{\cal F}_m^{(w'')}(n)|$ 
holds.
\label{utvizo}
\end{proposition}

\noindent
By ${\cal F}'(m)$ we denote the set of all words~$w$ from ${\cal F}(m)$ 
such that $w[1]=0$ and $w[2]=1$. It is obvious that for any word~$w$ 
from ${\cal F}(m)$ there exists a single word from ${\cal F}'(m)$ which 
is isomorphic to~$w$. Let $w',w''$ be two words from ${\cal F}'(m)$.
We call the word $w''$ a {\it quasi-descendant} of the word $w'$ if
$w''$ is isomorphic to some descendant of~$w'$. The word $w'$ is 
called in this case a {\it quasi-ancestor} of the word~$w''$. Let 
${\cal F}''(m)$ be the set of all words from ${\cal F}'(m)$
which are not closed. Since ternary square-free words of arbitrary
length exist, ${\cal F}''(m)$ is not empty for any~$m$. Denote 
$s=|{\cal F}''(m)|$. We enumerate all words from ${\cal F}''(m)$
by numbers $1, 2,\ldots,s$ in lexicographic order and denote 
$i$-th word of the set ${\cal F}''(m)$ by $w_i$, $i=1,\ldots ,s$.
Then we define a matrix $\Delta_m=(\delta_{ij})$ of size $s\times s$ 
in the following way: $\delta_{ij}=1$ if and only if $w_i$ is an
quasi-ancestor of $w_j$; otherwise $\delta_{ij}=0$. Note that $\Delta_m$ 
is a nonnegative matrix, so, by Perron-Frobenius theorem, for 
$\Delta_m$ there exists some maximal in modulus eigenvalue~$r$ which 
is a nonnegative real number. Moreover, we can find some eigenvector 
$\tilde x=(x_1;\ldots; x_s)$ with nonnegative components which 
corresponds to~$r$. Assume that $r>1$ and all components of~$\tilde x$
are positive. For $n\ge m$ define $S^{\langle\mbox{sf}\rangle}_m(n)=
\sum_{i=1}^s x_i\cdot |{\cal F}_m^{(w_i)}(n)|$. In an inductive way 
we estimate $S^{\langle\mbox{sf}\rangle}_m(n+1)$ by 
$S^{\langle\mbox{sf}\rangle}_m(n)$.  

First we estimate $|{\cal F}_m^{(w_i)}(n+1)|$ for $i=1,\ldots ,s$.
It is obvious that
\begin{equation}
|{\cal F}_m^{(w_i)}(n+1)|=|{\cal G}^{(w_i)}(n+1)|-|{\cal H}^{(w_i)}(n+1)|,
\label{Fwin}
\end{equation}
where ${\cal G}^{(w_i)}(n+1)$ is the set of all words~$w$ from 
${\cal L}_m^{(w_i)}(n+1)$ such that the words $w[1:n]$ and $w[n-m+1:n+1]$ 
are square-free, and ${\cal H}^{(w_i)}(n+1)$  is the set of all words
from ${\cal G}^{(w_i)}(n+1)$ which contain some square as a suffix. 
Denote by $\pi (i)$ the set of all quasi-ancestors of $w_i$. 
Taking into account Proposition~\ref{utvizo}, it is easy to see that
\begin{equation}
|{\cal G}^{(w_i)}(n+1)|=\sum_{w\in\pi (i)} |{\cal F}_m^{(w)}(n)|.
\label{Lwin}
\end{equation}


We now estimate $|{\cal H}^{(w_i)}(n+1)|$. For any word~$w$ from
${\cal H}^{(w_i)}(n+1)$ we can find the minimal square which is
a suffix of~$w$. Denote the period of this square by $\lambda (w)$.
It is obvious that $\lfloor (m+1)/2\rfloor <\lambda (w)\le
\lfloor (n+1)/2\rfloor$. Denote by ${\cal H}_j^{(w_i)}(n+1)$ 
the set of all words $w$ from ${\cal H}^{(w_i)}(n+1)$ such that 
$\lambda (w)=j$. Then
\begin{equation}
|{\cal H}^{(w_i)}(n+1)|=\sum_{\lfloor (m+1)/2\rfloor <j\le
\lfloor (n+1)/2\rfloor} |{\cal H}_j^{(w_i)}(n+1)|.
\label{Lwin2}
\end{equation}
Take some integer $p\ge m$ and assume that $n\ge 2p$.
Consider a set ${\cal H}_j^{(w_i)}(n+1)$ where $j\le p$. 
Let $w$ be an arbitrary word from this set. Then the suffix
$w[n-2j+2:n+1]$ is a square which contains neither closed 
words from ${\cal F}(m)$ nor other squares as factors and 
contains the word $w_i$ as a suffix. Let $v_1,\ldots,v_t$ 
be all possible squares of period~$j$ which satisfy the given 
conditions. Denote by ${\cal H}_{j,k}^{(w_i)}(n+1)$
the set of all words from ${\cal H}_j^{(w_i)}(n+1)$ which 
contain the square $v_k$ as a suffix, $k=1,\ldots, t$. Let 
$w\in {\cal H}_{j,k}^{(w_i)}(n+1)$. Since the prefix $w[1:n]$ 
is square-free, in this case we have $w[n-2j+1]\neq w[n-2j+2]=
v_k[1]$ and $w[n-2j+1]\neq w[n-j+1]=v_k[j]$. Moreover, 
$v_k[1]=w[n-j+2]\neq w[n-j+1]=v_k[j]$. Thus, the symbol 
$w[n-2j+1]$ is determined uniquely by $v_k$ as the symbol
from $\Sigma_3$ which is different from the two distinct 
symbols $v_k[1]$ and $v_k[j]$. Denoting this symbol by $b_k$,
we conclude that $v_k$ determines uniquely the factor $w[n-2j+1:n]$
as the word $b_k v_k[1:2j-1]$. Therefore, if this word is not
square-free or contains a closed word from ${\cal F}(m)$ as a
factor then ${\cal H}_{j,k}^{(w_i)}(n+1)=\emptyset$. Let 
$b_k v_k[1:2j-1]\in {\cal F}_m$. Then define $u_k=b_k v_k[1:m-1]=
w[n-2j+1:n-2j+m]$. Since $w$ is determined uniquely by the prefix 
$w[1:n-2j]$, we have $|{\cal H}_{j,k}^{(w_i)}(n+1)|\le 
|{\cal F}_m^{(u_k)}(n-2j+m)|$. Denote by $u'_k$ the word 
from ${\cal F}'(m)$ which is isomorphic to $u_k$. Then, 
by Proposition~\ref{utvizo}, we have
$$
|{\cal H}_{j,k}^{(w_i)}(n+1)|\le |{\cal F}_m^{(u'_k)}(n-2j+m)|.
$$
Thus, denoting by $U_j(w_i)$ the set of all words\footnote{Note 
that among words $u'_k$ we can have identical words, i.e., the same 
word can be counted several times in $U_j(w_i)$.} $u'_k$, we 
obtain that
\begin{equation}
|{\cal H}_j^{(w_i)}(n+1)|=\sum_{k=1}^t |{\cal H}_{j,k}^{(w_i)}(n+1)|\le
\sum_{u\in U_j(w_i)} |{\cal F}_m^{(u)}(n-2j+m)|.
\label{Ljwin}
\end{equation}

Consider now the set ${\cal H}_j^{(w_i)}(n+1)$ for $j>p$. 
Note that in this case $j>m$. Let $w$ be an arbitrary word from
${\cal H}_j^{(w_i)}(n+1)$. Then for~$w$ we have $w[n-2j+2:n-j+1]=
w[n-j+2:n+1]$, i.e., $w[n-j-m+2:n-j+1]=w_i$ and $w$ is determined 
uniquely by the prefix $w[1:n-j-m+1]$. Therefore, in this case
the inequality
\begin{equation}
|{\cal H}_j^{(w_i)}(n+1)|\le |{\cal F}_m^{(w_i)}(n-j+1)|.
\label{Ljwin1}
\end{equation}
holds. Using inequalities (\ref{Ljwin}) and~(\ref{Ljwin1}) 
in~(\ref{Lwin2}), we obtain
\begin{equation}
|{\cal H}^{(w_i)}(n+1)|\le A_p^{(w_i)}(n+1)+
B_p^{(w_i)}(n+1)
\label{Ljwin2}
\end{equation}
where
\begin{eqnarray*}
A_p^{(w_i)}(n+1)&=&\sum_{\lfloor (m+1)/2\rfloor <j\le p}
\left(\sum_{u\in U_j(w_i)} |{\cal F}_m^{(u)}(n-2j+m)|\right),\\
B_p^{(w_i)}(n+1)&=&
\sum_{p<j\le\lfloor (n+1)/2\rfloor} |{\cal F}_m^{(w_i)}(n-j+1)|.
\end{eqnarray*}

We now estimate $S^{\langle\mbox{sf}\rangle}_m(n+1)$. Using 
equality~(\ref{Fwin}), we have
\begin{equation}
S^{\langle\mbox{sf}\rangle}_m(n+1)=
\sum_{i=1}^s x_i\cdot |{\cal G}^{(w_i)}(n+1)|-
\sum_{i=1}^s x_i\cdot |{\cal H}^{(w_i)}(n+1)|.
\label{S_mn}
\end{equation}
Recall that $\tilde x$ is a eigenvector of $\Delta_m$ for
the eigenvalue~$r$. So, applying equality~(\ref{Lwin}),
we obtain
\begin{eqnarray}
\nonumber
&\sum_{i=1}^s x_i\cdot |{\cal G}^{(w_i)}(n+1)|=
\sum_{i=1}^s \bigl( x_i\cdot \sum_{w\in\pi (i)} |{\cal F}_m^{(w)}(n)| \bigr)&\\
\nonumber
&=(x_1;x_2;\ldots; x_s)\left(\begin{array}{cccc}
\delta_{11}& \delta_{21}& \ldots & \delta_{s1}\\
\delta_{12}& \delta_{22}& \ldots & \delta_{s2}\\
\vdots     & \vdots     & \ddots & \vdots     \\
\delta_{1s}& \delta_{2s}& \ldots & \delta_{ss}
\end{array}\right)
\left(\begin{array}{c}
|{\cal F}_m^{(w_1)}(n)|\\
|{\cal F}_m^{(w_2)}(n)|\\
\vdots \\
|{\cal F}_m^{(w_s)}(n)|
\end{array}\right)&\\
\label{rSmn}
&=r\cdot (x_1;x_2;\ldots; x_s)
\left(\begin{array}{c}
|{\cal F}_m^{(w_1)}(n)|\\
|{\cal F}_m^{(w_2)}(n)|\\
\vdots \\
|{\cal F}_m^{(w_s)}(n)|
\end{array}\right)=r\cdot S^{\langle\mbox{sf}\rangle}_m(n).&
\end{eqnarray}
For estimating the second sum in the right side of~(\ref{S_mn}) 
we use equality~(\ref{Ljwin2}):
\begin{equation}
\sum_{i=1}^s x_i\cdot |{\cal H}^{(w_i)}(n+1)|\le 
\sum_{i=1}^s x_i\cdot A_p^{(w_i)}(n+1)+
\sum_{i=1}^s x_i\cdot B_p^{(w_i)}(n+1)
\label{sum_is}
\end{equation}
where
\begin{eqnarray}
\nonumber
\displaystyle
\sum_{i=1}^s x_i\cdot B_p^{(w_i)}(n+1)&=&\sum_{p<j\le\lfloor (n+1)/2\rfloor}
\left(\sum_{i=1}^s x_i\cdot |{\cal F}_m^{(w_i)}(n-j+1)|\right)\\
\label{sum_pjle}
\displaystyle
&=&\sum_{p<j\le\lfloor (n+1)/2\rfloor} S^{\langle\mbox{sf}\rangle}_m(n-j+1).
\end{eqnarray}
For $k=1,\ldots ,s$ denote by $\zeta_j^{(k)}(w_i)$ the number of 
words $w_k$ in the set $U_j(w_i)$, and define $\eta_k(j)$ as
$\sum_{i=1}^s x_i\cdot \zeta_j^{(k)}(w_i)$. Note that any word
from $U_j(w_i)$ belongs to ${\cal F}''(m)$. Hence
\begin{eqnarray}
\nonumber
\displaystyle
\sum_{i=1}^s x_i\cdot A_p^{(w_i)}(n+1) &=&
\sum_{\lfloor (m+1)/2\rfloor <j\le p}\; \sum_{i=1}^s x_i
\left(\sum_{u\in U_j(w_i)} |{\cal F}_m^{(u)}(n-2j+m)|\right)\\
\displaystyle
&=& \sum_{\lfloor (m+1)/2\rfloor <j\le p}\; \sum_{k=1}^s
\eta_k(j)\cdot |{\cal F}_m^{(w_k)}(n-2j+m)|.
\label{sum_eta_j}
\end{eqnarray}
Take some integer $q\ge 2p-m$ and assume that $n\ge q+m$.
For the sake of convenience we present sum~(\ref{sum_eta_j}) as
$$
\sum_{d=d_0}^q \; \sum_{k=1}^s \eta'_k(d)\cdot |{\cal F}_m^{(w_k)}(n-d)|
$$ 
where $\eta'_k(d)=\eta_k\bigl((d+m)/2\bigr)$ if $d+m$ is even, 
$\eta'_k(d)=0$ otherwise, and $d_0=2\cdot \lfloor (m+3)/2\rfloor - m$. 
We majorize this sum by some sum  $\sum_{d=d_0}^q \rho_d\cdot 
S^{\langle\mbox{sf}\rangle}_m(n-d)$ in the following way. 
We compute consecutively coefficients $\rho_d$ of this sum for 
$d=d_0, d_0+1,\ldots ,q$. For each $d=d_0, d_0+1,\ldots ,q-1$ 
together with the number $\rho_d$ we compute also numbers
$\eta''_1(d+1),\ldots , \eta''_s(d+1)$ such that
\begin{equation}
\sum_{j=d_0}^{d+1} \; \sum_{k=1}^s \eta'_k(j)\cdot |{\cal F}_m^{(w_k)}(n-j)|
\le \sum_{k=1}^s \eta''_k(d+1)\cdot |{\cal F}_m^{(w_k)}(n-d-1)| +
\sum_{j=d_0}^{d} \rho_j\cdot S^{\langle\mbox{sf}\rangle}_m(n-j).
\label{sum_jd_1}
\end{equation}
For $d=d_0$ we take $\rho_{d_0}=\min_{1\le k\le s} (\eta'_k(d_0)/x_k)$.
Then
$$
\sum_{k=1}^s \eta'_k(d_0)\cdot |{\cal F}_m^{(w_k)}(n-d_0)|=
\rho_{d_0}\cdot S^{\langle\mbox{sf}\rangle}_m(n-d_0) + 
\sum_{k=1}^s \nu_k\cdot |{\cal F}_m^{(w_k)}(n-d_0)|
$$
where $\nu_k=\eta'_k(d_0)-\rho_{d_0}\cdot x_k$, $k=1,\ldots, s$. Denote
by $\tilde\nu$ the vector $(\nu_1;\ldots ;\nu_s)$ and consider the vector
$\tilde\nu'=\Delta_m \tilde\nu$. Let $\tilde\nu'=(\nu'_1;\ldots ;\nu'_s)$.
It follows from (\ref{Fwin}) and~(\ref{Lwin}) that
$$
|{\cal F}_m^{(w_k)}(n-d_0)|\le |{\cal G}^{(w_i)}(n-d_0)|=
\sum_{w\in\pi (k)} |{\cal F}_m^{(w)}(n-d_0-1)|
$$
for any $k=1,\ldots ,s$. Note also that $\nu_k\ge 0$ for $k=1,\ldots, s$.
Hence
\begin{eqnarray*}
\sum_{k=1}^s \nu_k\cdot |{\cal F}_m^{(w_k)}(n-d_0)|&\le& \sum_{k=1}^s 
\left(\nu_k\cdot \sum_{w\in\pi (k)} |{\cal F}_m^{(w)}(n-d_0-1)|\right)\\
&=&\sum_{k=1}^s \nu'_k\cdot |{\cal F}_m^{(w_k)}(n-d_0-1)|.
\end{eqnarray*}
Thus
\begin{equation}
\sum_{j=d_0}^{d_0+1} \; \sum_{k=1}^s \eta'_k(j)\cdot 
|{\cal F}_m^{(w_k)}(n-j)|\le\rho_{d_0}\cdot 
S^{\langle\mbox{sf}\rangle}_m(n-d_0)+\sum_{k=1}^s 
\eta''_k(d_0+1)\cdot |{\cal F}_m^{(w_k)}(n-d_0-1)|
\label{sum_jd_0}
\end{equation}
where $\eta''_k(d_0+1)=\eta'_k(d_0+1)+\nu'_k$. Assume now that for
some~$d$ such that $d_0<d<q$ we already computed the numbers $\rho_{d_0},
\ldots ,\rho_{d-1}$ and $\eta''_1(d),\ldots,\eta''_s(d)$. Then we take
$\rho_{d}=\min_{1\le k\le s} (\eta''_k(d)/x_k)$, $\tilde\nu=(\eta''_1(d)-
\rho_d\cdot x_1,\ldots ,\eta''_s(d)-\rho_d\cdot x_s)$, and $\tilde\nu'=
\Delta_m \tilde\nu$. We take also $\eta''_k(d+1)=\eta'_k(d+1)+\nu'_k$ 
where $\nu'_k$ is the $k$-th component of the vector $\tilde\nu'$, 
$k=1,\ldots ,s$. Analogously to inequality~(\ref{sum_jd_0}),
in this case we have the inequality
$$
\begin{array}{c}
\displaystyle
\sum_{k=1}^s \left(\eta''_k(d)\cdot |{\cal F}_m^{(w_k)}(n-d)|+
\eta'_k(d+1)\cdot |{\cal F}_m^{(w_k)}(n-d-1)|\right)\\
\displaystyle
\le \rho_d\cdot S^{\langle\mbox{sf}\rangle}_m(n-d)+\sum_{k=1}^s 
\eta''_k(d+1)\cdot |{\cal F}_m^{(w_k)}(n-d-1)|.
\end{array}
$$
This inequality implies that inequality~(\ref{sum_jd_1})
holds for every~$d$. For $d=q$ we take $\rho_q=\max_{1\le k\le s} 
(\eta''_k(q)/x_k)$. Thus,
\begin{equation}
\sum_{i=1}^s x_i A_p^{(w_i)}(n+1)=
\sum_{d=d_0}^q \; \sum_{k=1}^s \eta'_k(d)\cdot |{\cal F}_m^{(w_k)}(n-d)|\le
\sum_{d=d_0}^q \rho_d\cdot S^{\langle\mbox{sf}\rangle}_m(n-d).
\label{sum_i_sx}
\end{equation}
For the sake of convenience denote by ${\cal P}_m^{(p,q)}(z)$ the 
polynomial $\sum_{d=d_0}^q \rho_d\cdot z^d$ in a variable~$z$.

Let for some $\alpha >1$ and each $i=m, m+1,\ldots , n-1$ the inequality
$S^{\langle\mbox{sf}\rangle}_m(i+1)\ge \alpha S^{\langle\mbox{sf}\rangle}_m(i)$
be valid. Then for each $i=m, m+1,\ldots , n-1$ we have 
$S^{\langle\mbox{sf}\rangle}_m(i)\le 
S^{\langle\mbox{sf}\rangle}_m(n)/\alpha^{n-i}$. So relation~(\ref{sum_i_sx})
implies that 
$$
\sum_{i=1}^s x_i\cdot A_p^{(w_i)}(n+1)\le \sum_{d=d_0}^q \rho_d\cdot 
(S^{\langle\mbox{sf}\rangle}_m(n)/\alpha^d)=
{\cal P}_m^{(p,q)}(1/\alpha)\cdot S^{\langle\mbox{sf}\rangle}_m(n).
$$
In an analogous way relation~(\ref{sum_pjle}) implies that
\begin{eqnarray*}
\sum_{i=1}^s x_i B_p^{(w_i)}(n+1)&\le&\sum_{p<j\le\lfloor (n+1)/2\rfloor} 
S^{\langle\mbox{sf}\rangle}_m(n)/\alpha^{j-1} < 
S^{\langle\mbox{sf}\rangle}_m(n)\cdot \sum_{j=p}^{\infty} 1/\alpha^j\\
&=&\frac{S^{\langle\mbox{sf}\rangle}_m(n)}{\alpha^{p-1}(\alpha -1)}.
\end{eqnarray*}
Thus, from~(\ref{sum_is}) we have
$$
\sum_{i=1}^s x_i\cdot |{\cal H}^{(w_i)}(n+1)|< 
S^{\langle\mbox{sf}\rangle}_m(n)\cdot\left({\cal P}_m^{(p,q)}(1/\alpha)+
\frac{1}{\alpha^{p-1}(\alpha -1)}\right).
$$
Using this inequality together with equality~(\ref{rSmn}) in~(\ref{S_mn}), 
we obtain
$$
S^{\langle\mbox{sf}\rangle}_m(n+1)>S^{\langle\mbox{sf}\rangle}_m(n)\cdot
\left(r-{\cal P}_m^{(p,q)}(1/\alpha)-\frac{1}{\alpha^{p-1}(\alpha -1)}\right).
$$
Therefore, if $\alpha$ satisfy the inequality
$$
r-{\cal P}_m^{(p,q)}(1/\alpha)-\frac{1}{\alpha^{p-1}(\alpha -1)}
\ge\alpha,
$$
we obtain inductively that the inequality $S^{\langle\mbox{sf}\rangle}_m({n+1})
\ge \alpha S^{\langle\mbox{sf}\rangle}_m(n)$ holds for any~$n$. Thus, 
in this case we have $S^{\langle\mbox{sf}\rangle}_m(n)=\Omega (\alpha^n)$. 
Since, obviously, the order of growth of $S^{\langle\mbox{sf}\rangle}(n)$ 
is not less than $S^{\langle\mbox{sf}\rangle}_m(n)$, we then conclude that
$S^{\langle\mbox{sf}\rangle}(n)=\Omega (\alpha^n)$. Hence 
$\gamma^{\langle\mbox{sf}\rangle}\ge\alpha$.

For obtaining a concrete lower bound on $\gamma^{\langle\mbox{sf}\rangle}$
we take the parameters $m=45$, $p=52$, $q=60$. Using computer computations,
we have obtained\footnote{In this paper the obtained numerical results are 
given with precision of 6 decimal digits after the point.} that   
$|{\cal F}''(45)|=277316$, the maximal in modulus eigenvalue~$r$ for
$\Delta_{45}$ is $1.302011$, and all components of the eigenvector 
corresponding to~$r$ are positive. Further, we obtained that
$$
\begin{array}{c}
{\cal P}_{45}^{(52,60)}(z) = 3.759479\cdot z^{44} + 3.176743\cdot z^{45} 
+ 6.048526\cdot z^{46} + \\
7.120005\cdot z^{48} + 14.679230\cdot z^{50} + 41.594270\cdot z^{52}
+ 37.431675\cdot z^{55} + \\
40.471892\cdot z^{56} + 32.780085\cdot z^{58}
+ 5.235193\cdot z^{59} + 275.705551\cdot z^{60}.
\end{array}
$$
Let $\alpha =1.30173$. It is immediately checked that
$$
r-{\cal P}_{45}^{(52,60)}(1/\alpha)-\frac{1}{\alpha^{51}(\alpha -1)}
\ge\alpha.
$$
Moreover, the inequalities $S^{\langle\mbox{sf}\rangle}_{45}(n+1)\ge 
\alpha S^{\langle\mbox{sf}\rangle}_{45}(n)$ for each $n=45, 46,\ldots,
q+m-1=104$ are verified in the same inductive way as described above
with evident modifications following from the restriction $n<q+m$. 
Thus, we obtaine that $\gamma^{\langle\mbox{sf}\rangle}\ge 1.30173$.


\section{Estimation for the number of minimally repetitive 
ternary words}

For obtaining a lower bound on $\gamma^{\langle\mbox{lf}\rangle}$ we 
also consider words over $\Sigma_3$. Now denote by ${\cal F}$ the set 
of all minimally repetitive words from~$\Sigma^*_3$. By a prohibited
repetition we mean a word with an exponent greater than $7/4$. Let $m$ 
be a natural number, $m>2$. Analogously to the case of square-free words, 
we introduce also the notions of descendant, ancestor, and closed word
for minimally repetitive words, and denote by ${\cal L}_m$ the set 
of all words from $\Sigma^*_3$ which do not contain closed words from 
${\cal F}(m)$ as factors. Denote also by ${\cal F}_m$ the set of all 
minimally repetitive words from ${\cal L}_m$, by ${\cal F}'(m)$ the 
set of all words~$w$ from ${\cal F}(m)$ such that $w[1]=0$ and $w[2]=1$,
and by ${\cal F}''(m)$ the set of all words from ${\cal F}'(m)$ which are
not closed. As in the case of square-free words, we introduce the notions 
of quasi-descendant and quasi-ancestor, define for ${\cal F}''(m)$
the matrix $\Delta_m$ of size $s\times s$ where $s=|{\cal F}''(m)|$, 
and compute the maximal in modulus eigenvalue~$r$ of this matrix.
If $r>1$ and all components of the eigenvector $\tilde x=(x_1;\ldots; x_s)$ 
corresponding to~$r$ are positive, then we denote by $\mu$ the ratio 
$\max_i x_i/\min_i x_i$, and for $n\ge m$ consider 
$S^{\langle\mbox{lf}\rangle}_m(n)=\sum_{i=1}^s x_i\cdot |{\cal F}_m^{(w_i)}(n)|$
where $w_i$ is $i$-th word of the set ${\cal F}''(m)$, $i=1,\ldots ,s$.

Analogously to equality~(\ref{Fwin}), for $i=1,\ldots ,s$ we have
\begin{equation}
|{\cal F}_m^{(w_i)}(n+1)|=|{\cal G}^{(w_i)}(n+1)|-|{\cal H}^{(w_i)}(n+1)|
\label{Fwin-1}
\end{equation}
where ${\cal G}^{(w_i)}(n+1)$ is the set of all words~$w$ from 
${\cal L}_m^{(w_i)}(n+1)$ such that the words $w[1:n]$ and $w[n-m+1:n+1]$ 
are minimally repetitive, and ${\cal H}^{(w_i)}(n+1)$ is the set of all 
words from ${\cal G}^{(w_i)}(n+1)$ which contain some prohibited
repetition as a suffix. Analogously to equality~(\ref{Lwin}), we 
can obtain
$$
|{\cal G}^{(w_i)}(n+1)|=\sum_{w\in\pi (i)} |{\cal F}_m^{(w)}(n)|
$$
where $\pi (i)$ is the set of all quasi-ancestors of $w_i$.
For any word~$w$ from ${\cal H}^{(w_i)}(n+1)$ denote by~$\lambda (w)$
the minimal period of the shortest prohibited repetition which is 
a suffix of~$w$. Then, analogously to equality~(\ref{Lwin2}),
$$
|{\cal H}^{(w_i)}(n+1)|=\sum_{\lfloor (4m+3)/7\rfloor <j\le
\lfloor 4n/7\rfloor} |{\cal H}_j^{(w_i)}(n+1)|,
$$
where ${\cal H}_j^{(w_i)}(n+1)$ is the set of all words $w$ 
from ${\cal H}^{(w_i)}(n+1)$ such that $\lambda (w)=j$.
Take some integer $p\ge 4m/3-1$ and assume that $n>\lfloor 7p/4\rfloor$.
Let $w$ be an arbitrary word from ${\cal H}_j^{(w_i)}(n+1)$ 
where $j\le p$. Then the suffix $w[n-\lfloor 7p/4\rfloor +1:n+1]$ 
is a prohibited repetition which contains neither closed words 
from ${\cal F}(m)$ nor other prohibited repetitions as factors and 
contains the word $w_i$ as a suffix. Let $v_1,\ldots,v_t$ be all 
possible prohibited repetitions with minimal period~$j$ which satisfy 
the given conditions. Denote by ${\cal H}_{j,k}^{(w_i)}(n+1)$ the set 
of all words from ${\cal H}_j^{(w_i)}(n+1)$ which contain $v_k$ 
as a suffix, $k=1,\ldots, t$. Let $w\in {\cal H}_{j,k}^{(w_i)}(n+1)$. 
Analogously to the case of square-free words, the symbol 
$w[n-\lfloor 7j/4\rfloor ]$ is determined uniquely by $v_k$ as the 
symbol from $\Sigma_3$ which is different from the two distinct 
symbols $v_k[1]$ and $v_k[j]$. Denoting this symbol by $b_k$,
we conclude that the factor $w[n-\lfloor 7j/4\rfloor :n]$ is determined 
uniquely as the word $b_k v_k[1:\lfloor 7j/4\rfloor ]$. Let this word 
belong to ${\cal F}_m$. Then we denote by $u'_k$ the word from 
${\cal F}'(m)$ which is isomorphic to the word $b_k v_k[1:m-1]$. 
Analogously to inequality~(\ref{Ljwin}), one can obtain the inequality
$$
|{\cal H}_j^{(w_i)}(n+1)|\le\sum_{u\in U_j(w_i)} 
|{\cal F}_m^{(u)}(n+m-\lfloor 7j/4\rfloor -1)|
$$
where $U_j(w_i)$ is the set of all words\footnote{Note that, 
as in the case of square-free words, the same word can be counted
several times in $U_j(w_i)$.} $u'_k$. Thus,
\begin{equation}
|{\cal H}^{(w_i)}(n+1)|\le A_p^{(w_i)}(n+1)+
\sum_{p<j\le\lfloor 4n/7\rfloor} |{\cal H}_j^{(w_i)}(n+1)|
\label{Ljwin-2}
\end{equation}
where
$$
A_p^{(w_i)}(n+1)=\sum_{\lfloor (4m+3)/7\rfloor <j\le p}
\left(\sum_{u\in U_j(w_i)} |{\cal F}_m^{(u)}(n+m-\lfloor 7j/4\rfloor 
-1)|\right).
$$
From (\ref{Fwin-1}) and~(\ref{Ljwin-2}) we obtain that
\begin{eqnarray}
\nonumber
\displaystyle
S^{\langle\mbox{lf}\rangle}_m(n+1)&\ge&\sum_{i=1}^s x_i\cdot 
|{\cal G}^{(w_i)}(n+1)|-\sum_{i=1}^s x_i\cdot |A_p^{(w_i)}(n+1)|-\\
\displaystyle
&&\sum_{p<j\le\lfloor 4n/7\rfloor}\left(\sum_{i=1}^s x_i\cdot 
|{\cal H}_j^{(w_i)}(n+1)|\right).
\label{Ljwin-3}
\end{eqnarray}
Analogously to equality~(\ref{rSmn}), the equality
\begin{equation}
\sum_{i=1}^s x_i\cdot |{\cal G}^{(w_i)}(n+1)|=
r\cdot S^{\langle\mbox{lf}\rangle}_m(n)
\label{rSmn1}
\end{equation}
is valid. Let $j>p$, i.e., $j\ge 4m/3$. Note that the sets 
${\cal H}_j^{(w_i)}(n+1)$ are non-overlapping. So we have
the obvious inequality
\begin{equation}
\sum_{i=1}^s x_i\cdot |{\cal H}_j^{(w_i)}(n+1)|\le
|{\cal M}_j|\cdot \max_{i=1,\ldots,s} x_i
\label{sumHj}
\end{equation}
where ${\cal M}_j=\bigcup_{i=1}^s {\cal H}_j^{(w_i)}(n+1)$.
Note also that any word $w$ from ${\cal M}_j$ is determined 
uniquely by the prefix $w[1:n-\lfloor 3j/4\rfloor ]$ and
satisfies the conditions $w[n+2-m-j]=w[n+2-m]=0$ and
$w[n+3-m-j]=w[n+3-m]=1$. Thus $|{\cal M}_j|\le |{\cal M}'_j|$
where ${\cal M}'_j$ is the set of all words $w$ from
${\cal F}_m(n-\lfloor 3j/4\rfloor )$ such that $w[n+2-m-j]=0$
and $w[n+3-m-j]=1$. Consider also the set ${\cal M}''_j$ of all
words $w$ from ${\cal F}_m(n-\lfloor 3j/4\rfloor )$ such that
$w[n+1-\lfloor 3j/4\rfloor -m]=0$ and $w[n+2-\lfloor 3j/4\rfloor -m]=1$.
There is an evident bijection between the sets ${\cal M}'_j$ and 
${\cal M}''_j$, so $|{\cal M}'_j|=|{\cal M}''_j|$. Note also that
the set ${\cal M}''_j$ is the union of the non-overlapping sets
${\cal H}_j^{(w_i)}(n-\lfloor 3j/4\rfloor )$ for $i=1,\ldots, s$, 
i.e.,
$$
|{\cal M}''_j|\le \sum_{i=1}^s |{\cal H}_j^{(w_i)}(n-\lfloor 3j/4\rfloor )|
\le S^{\langle\mbox{lf}\rangle}_m(n-\lfloor 3j/4\rfloor )/
(\min_{i=1,\ldots,s} x_i).
$$
Therefore, it follows from~(\ref{sumHj}) that
$$
\sum_{i=1}^s x_i\cdot |{\cal H}_j^{(w_i)}(n+1)|\le
|{\cal M}'_j|\cdot \max_{i=1,\ldots,s} x_i =
|{\cal M}''_j|\cdot \max_{i=1,\ldots,s} x_i \le
\mu\cdot S^{\langle\mbox{lf}\rangle}_m(n-\lfloor 3j/4\rfloor ).
$$
Thus,
\begin{equation}
\sum_{p<j\le\lfloor 4n/7\rfloor}\left(\sum_{i=1}^s x_i
\cdot |{\cal H}_j^{(w_i)}(n+1)|\right)\le\mu\cdot
\sum_{p<j\le\lfloor 4n/7\rfloor} 
S^{\langle\mbox{lf}\rangle}_m(n-\lfloor 3j/4\rfloor ).
\label{sumplej}
\end{equation}

Let $\eta_k(j)=\sum_{i=1}^s x_i\cdot\zeta_j^{(k)}(w_i)$ where
$\zeta_j^{(k)}(w_i)$ is the number of words $w_k$ in the set  
$U_j(w_i)$, $k=1,\ldots ,s$. Then, analogously to equality~(\ref{sum_eta_j}),
\begin{equation}
\sum_{i=1}^s x_i\cdot |A_p^{(w_i)}(n+1)| =
\sum_{\lfloor (4m+3)/7\rfloor <j\le p}\; \sum_{k=1}^s
\eta_k(j)\cdot |{\cal F}_m^{(w_k)}(n+m-\lfloor 7j/4\rfloor -1)|.
\label{sum_eta1}
\end{equation}
Take some integer $q\ge \lfloor 7p/4\rfloor +1-m$ and assume that 
$n\ge q+m$. Analogously to the case of square-free words, sum~(\ref{sum_eta1})
can be majorized by some sum $\sum_{d=d_0}^q \rho_d\cdot S_m(n-d)$ where
$d_0=\lfloor 7j_0/4\rfloor +1- m$ for $j_0=\lfloor (4m+3)/7\rfloor +1$.

Let for some $\alpha >1$ and each $i=m, m+1,\ldots , n-1$ the inequality
$S^{\langle\mbox{lf}\rangle}_m(i+1)\ge \alpha S^{\langle\mbox{lf}\rangle}_m(i)$
be valid, i.e., $S^{\langle\mbox{lf}\rangle}_m(i)\le 
S^{\langle\mbox{lf}\rangle}_m(n)/\alpha^{n-i}$. Then
\begin{equation}
\sum_{i=1}^s x_i\cdot A_p^{(w_i)}(n+1)\le \sum_{d=d_0}^q \rho_d\cdot 
(S^{\langle\mbox{lf}\rangle}_m(n)/\alpha^d)=
{\cal P}_m^{(p,q)}(1/\alpha)\cdot S^{\langle\mbox{lf}\rangle}_m(n)
\label{sumA_p}
\end{equation}
where ${\cal P}_m^{(p,q)}(z)=\sum_{d=d_0}^q \rho_d\cdot z^d$.
Moreover, it follows from~(\ref{sumplej}) that
$$
\begin{array}{c}
\displaystyle
\sum_{p<j\le\lfloor 4n/7\rfloor}\left(\sum_{i=1}^s x_i\cdot 
|{\cal H}_j^{(w_i)}(n+1)|\right)\le\mu\cdot\sum_{p<j\le\lfloor 4n/7\rfloor} 
S^{\langle\mbox{lf}\rangle}_m(n)/\alpha^{\lfloor 3j/4\rfloor}\\
\displaystyle
<\mu S^{\langle\mbox{lf}\rangle}_m(n)\cdot \sum_{p<j} 
1/\alpha^{\lfloor 3j/4\rfloor} \\
\displaystyle
=\mu S^{\langle\mbox{lf}\rangle}_m(n)\cdot 
\left(\sum_{j\ge \lfloor 3(p+1)/4\rfloor} 1/\alpha^j +
\sum_{j\ge \lceil (p+1)/4\rceil} 1/\alpha^{3j}\right) \\
\displaystyle
=\mu S^{\langle\mbox{lf}\rangle}_m(n)\cdot 
\Bigl(1/\bigl(\alpha^{\lfloor (3p-1)/4\rfloor} 
(\alpha -1)\bigr) + 1/\bigl(\alpha^{3\lfloor p/4\rfloor}
(\alpha^3-1)\bigr)\Bigr).
\end{array}
$$
Thus, from inequality~(\ref{Ljwin-3}) together with relations
(\ref{rSmn1}) and~(\ref{sumA_p}) we obtain that
\begin{eqnarray*}
S^{\langle\mbox{lf}\rangle}_m(n+1)&>&S^{\langle\mbox{lf}\rangle}_m(n)
\cdot\Biggl(r-{\cal P}_m^{(p,q)}(1/\alpha)-\\
&&\mu\cdot\Bigl(1/\bigl(\alpha^{\lfloor (3p-1)/4\rfloor} (\alpha -1)\bigr)
+1/\bigl(\alpha^{3\lfloor p/4\rfloor}(\alpha^3-1)\bigr)\Bigr)\Biggr).
\end{eqnarray*}
Therefore, if
$$
r-{\cal P}_m^{(p,q)}(1/\alpha)-\mu\cdot\Bigl(
1/\bigl(\alpha^{\lfloor (3p-1)/4\rfloor} (\alpha -1)\bigr)+
1/\bigl(\alpha^{3\lfloor p/4\rfloor}(\alpha^3-1)\bigr)\Bigr)
\ge\alpha
$$
then $S^{\langle\mbox{lf}\rangle}_m(n+1)\ge 
\alpha S^{\langle\mbox{lf}\rangle}_m(n)$ for any~$n$, 
i.e., $S^{\langle\mbox{lf}\rangle}_m(n)=\Omega (\alpha^n)$.
Since the order of growth of $S^{\langle\mbox{lf}\rangle}(n)$
is not less than $S^{\langle\mbox{lf}\rangle}_m(n)$, in this case
we have $S^{\langle\mbox{lf}\rangle}(n)=\Omega (\alpha^n)$,
i.e., $\gamma^{\langle\mbox{lf}\rangle}\ge\alpha$.

Using computer computations with the parameters $m=42$, $p=72$, $q=85$,
we obtained that $|{\cal F}''(42)|=36141$, $r=1.247500$, all components 
of the eigenvector corresponding to~$r$ were positive, and
${\cal P}_{42}^{(72,85)}(z)$ was
$$
\begin{array}{l}
1.976268\cdot z^{42} + 1.148062\cdot z^{44} 
+ 3.519576\cdot z^{45} + 1.741046\cdot z^{47} + \\
9.687624\cdot z^{49} + 0.126312\cdot z^{50}+ 31.479339\cdot z^{52} + 
12.284335\cdot z^{53} + \\
21.010557\cdot z^{54} +  24.183001\cdot z^{56} + 96.529327\cdot z^{61} + 
129.216325\cdot z^{64} + \\
256.213310\cdot z^{66} + 14.826731\cdot z^{67} + 64.163103\cdot z^{68} + 
6.862805\cdot z^{69} + \\
84.819931\cdot z^{70} + 2.337610\cdot z^{72} + 175.026144\cdot z^{73} + 
41.068102\cdot z^{74} + \\
335.714818\cdot z^{75} + 341.576384\cdot z^{78} + 329.970329\cdot z^{80} + 
693.282157\cdot z^{81} + \\
763.104210\cdot z^{82} + 303.272754\cdot z^{83} +
583.157071\cdot z^{84} + 10510.070498\cdot z^{85}.
\end{array}
$$
Let $\alpha =1.245$. It is immediately checked that
$$
r-{\cal P}_{42}^{(72,85)}(1/\alpha)-\frac{1}{\alpha^{53}(\alpha-1)}-
\frac{1}{\alpha^{54}(\alpha^3-1)}\ge\alpha.
$$
Moreover, we estimate $S^{\langle\mbox{lf}\rangle}_{42}(n+1)\ge 
\alpha S^{\langle\mbox{lf}\rangle}_{42}(n)$ for each $n=42, 43,\ldots ,
q+m-1=126$ in the same inductive way with evident modifications 
following from the restriction $n<q+m$. Thus we obtain that 
$\gamma^{\langle\mbox{lf}\rangle}\ge 1.245$.

\section{Estimation for the number of binary cube-free words}

To obtain a lower bound on $\gamma^{\langle\mbox{cf}\rangle}$, we consider 
the alphabet $\Sigma_2=\{0,1\}$. Denote by~${\cal F}$ the set of all 
cube-free words from~$\Sigma^*_2$. Analogously to the case of square-free 
words, for any natural number $m>2$ we can introduce the notions of descendant, 
ancestor, and closed word for cube-free words. Denote also by ${\cal L}_m$ 
the set of all words from $\Sigma^*_2$ which do not contain closed words 
from ${\cal F}(m)$ as factors, and by ${\cal F}_m$ the set of all cube-free 
words from ${\cal L}_m$. By ${\cal F}'(m)$ we denote the set of all words~$w$ 
from ${\cal F}(m)$ such that $w[1]=0$. Note that for any word~$w$ from 
${\cal F}(m)$ there exists a single word from ${\cal F}'(m)$ which is 
isomorphic to~$w$. By ${\cal F}''(m)$ we denote the set of all words from 
${\cal F}'(m)$ which are not closed. We introduce also the notions of 
quasi-descendant and quasi-ancestor, define for ${\cal F}''(m)$ 
the matrix $\Delta_m$ of size $s\times s$ where $s=|{\cal F}''(m)|$, 
and compute the maximal in modulus eigenvalue~$r$ of this matrix.
If $r>1$ and all components of the eigenvector $\tilde x=(x_1;\ldots; x_s)$ 
corresponding to~$r$ are positive, then for $n\ge m$ we consider 
$S^{\langle\mbox{cf}\rangle}_m(n)=\sum_{i=1}^s x_i\cdot |{\cal F}_m^{(w_i)}(n)|$
where $w_i$ is $i$-th word of the set ${\cal F}''(m)$, $i=1,\ldots ,s$.

As in the case of square-free words, for $i=1,\ldots ,s$ we have
\begin{equation}
|{\cal F}_m^{(w_i)}(n+1)|=|{\cal G}^{(w_i)}(n+1)|-|{\cal H}^{(w_i)}(n+1)|
\label{Fwin-3}
\end{equation}
where ${\cal G}^{(w_i)}(n+1)$ is the set of all words~$w$ from 
${\cal L}_m^{(w_i)}(n+1)$ such that the words $w[1:n]$ and $w[n-m+1:n+1]$ 
are cube-free, and ${\cal H}^{(w_i)}(n+1)$ is the set of all words
from ${\cal G}^{(w_i)}(n+1)$ which contain some cube as a suffix. 
Analogously to equality~(\ref{Lwin}), we obtain
$$
|{\cal G}^{(w_i)}(n+1)|=\sum_{w\in\pi (i)} |{\cal F}_m^{(w)}(n)|
$$
where $\pi (i)$ is the set of all quasi-ancestors of $w_i$.
For any word~$w$ from ${\cal H}^{(w_i)}(n+1)$ denote by~$\lambda (w)$
the period of the minimal cube which is a suffix of~$w$. Then, 
analogously to equality~(\ref{Lwin2}),
\begin{equation}
|{\cal H}^{(w_i)}(n+1)|=\sum_{\lfloor (m+1)/3\rfloor <j\le
\lfloor (n+1)/3\rfloor} |{\cal H}_j^{(w_i)}(n+1)|,
\label{Lwin-2}
\end{equation}
where ${\cal H}_j^{(w_i)}(n+1)$ is the set of all words $w$ 
from ${\cal H}^{(w_i)}(n+1)$ such that $\lambda (w)=j$. 
Take some integer $p\ge m$ and assume that $n\ge 3p$.
Let $w$ be an arbitrary word from ${\cal H}_j^{(w_i)}(n+1)$
where $j\le p$. Then the suffix $w[n-3j+2:n+1]$ is a cube 
which contains neither closed words from ${\cal F}(m)$ nor 
other cubes as factors and contains the word $w_i$ as a suffix. 
Let $v_1,\ldots,v_t$ be all possible cubes of period~$j$ which 
satisfy the given conditions. Denote by ${\cal H}_{j,k}^{(w_i)}(n+1)$
the set of all words from ${\cal H}_j^{(w_i)}(n+1)$ which 
contain the cube $v_k$ as a suffix, $k=1,\ldots, t$. Let 
$w\in {\cal H}_{j,k}^{(w_i)}(n+1)$. Since the prefix $w[1:n]$ 
is cube-free, in this case we have $w[n-3j+1]\neq w[n-2j+1]=v_k[j]$. 
Thus, the symbol $w[n-3j+1]$ is determined uniquely by $v_k$
as the symbol from $\Sigma_2$ which is different from $v_k[j]$.
Denoting this symbol by $b_k$, we conclude that $v_k$ determines 
uniquely the factor $w[n-3j+1:n]$ as the word $b_k v_k[1:3j-1]$.
If this word is cube-free and does not contain closed words from 
${\cal F}(m)$ as factors then we denote by $u'_k$ the word from 
${\cal F}'(m)$ which is isomorphic to $w[n-3j+1:n-3j+m]$. 
Analogously to inequality~(\ref{Ljwin}), one can obtain the inequality
\begin{equation}
|{\cal H}_j^{(w_i)}(n+1)|\le\sum_{u\in U_j(w_i)} 
|{\cal F}_m^{(u)}(n-3j+m)|
\label{Ljwin0}
\end{equation}
where $U_j(w_i)$ is the set of all words\footnote{Note that, 
as in the case of square-free words, the same word can be counted 
several times in $U_j(w_i)$.} $u'_k$. For $j>p$, analogously to 
inequality~(\ref{Ljwin1}), we have
\begin{equation}
|{\cal H}_j^{(w_i)}(n+1)|\le |{\cal F}_m^{(w_i)}(n-2j+1)|.
\label{Ljwin-1}
\end{equation}
Thus, from (\ref{Lwin-2}), (\ref{Ljwin0}) and~(\ref{Ljwin-1})
we obtain that
\begin{equation}
|{\cal H}^{(w_i)}(n+1)|\le A_p^{(w_i)}(n+1)+
B_p^{(w_i)}(n+1)
\label{Ljwin3}
\end{equation}
where
\begin{eqnarray*}
A_p^{(w_i)}(n+1)&=&\sum_{\lfloor (m+1)/3\rfloor <j\le p}
\left(\sum_{u\in U_j(w_i)} |{\cal F}_m^{(u)}(n-3j+m)|\right),\\
B_p^{(w_i)}(n+1)&=&
\sum_{p<j\le\lfloor (n+1)/3\rfloor} |{\cal F}_m^{(w_i)}(n-2j+1)|.
\end{eqnarray*}
Moreover, analogously to equalities (\ref{rSmn}) and~(\ref{sum_pjle}),
the equalities
\begin{equation}
\sum_{i=1}^s x_i\cdot |{\cal G}^{(w_i)}(n+1)|=
r\cdot S^{\langle\mbox{cf}\rangle}_m(n)
\label{rSmn3}
\end{equation}
and
\begin{equation}
\sum_{i=1}^s x_i\cdot B_p^{(w_i)}(n+1)=
\sum_{p<j\le\lfloor (n+1)/3\rfloor} S^{\langle\mbox{cf}\rangle}_m(n-2j+1)
\label{sum_pjl1}
\end{equation}
hold. Let $\eta_k(j)=\sum_{i=1}^s x_i\cdot\zeta_j^{(k)}(w_i)$
where $\zeta_j^{(k)}(w_i)$ is the number of words $w_k$ in the 
set $U_j(w_i)$, $k=1,\ldots ,s$. Then, analogously to 
equality~(\ref{sum_eta_j}),
\begin{equation}
\sum_{i=1}^s x_i\cdot A_p^{(w_i)}(n+1) =
\sum_{\lfloor (m+1)/3\rfloor <j\le p}\; \sum_{k=1}^s
\eta_k(j)\cdot |{\cal F}_m^{(w_k)}(n-3j+m)|.
\label{sum_eta3}
\end{equation}
Take some integer $q\ge 3p-m$ and assume that $n\ge q+m$.
Analogously to the case of square-free words, sum~(\ref{sum_eta3}) 
can be majorized by some sum $\sum_{d=d_0}^q \rho_d\cdot 
S^{\langle\mbox{cf}\rangle}_m(n-d)$ where $d_0=3\cdot 
\lfloor (m+4)/3\rfloor - m$.

Let for some $\alpha >1$ and each $i=m, m+1,\ldots , n-1$ the inequalities
$S^{\langle\mbox{cf}\rangle}_m(i+1)\ge \alpha S^{\langle\mbox{cf}\rangle}_m(i)$ 
be valid. Then
$$
\sum_{i=1}^s x_i\cdot A_p^{(w_i)}(n+1)\le \sum_{d=d_0}^q \rho_d\cdot 
(S^{\langle\mbox{cf}\rangle}_m(n)/\alpha^d)={\cal P}_m^{(p,q)}(1/\alpha)\cdot 
S^{\langle\mbox{cf}\rangle}_m(n),
$$
where ${\cal P}_m^{(p,q)}(z)=\sum_{d=d_0}^q \rho_d\cdot z^d$.
Moreover, it follows from~(\ref{sum_pjl1}) that
$$
\sum_{i=1}^s x_i\cdot B_p^{(w_i)}(n+1)\le \sum_{p<j\le\lfloor (n+1)/3\rfloor} 
\frac{S^{\langle\mbox{cf}\rangle}_m(n)}{\alpha^{2j-1}}<
\sum_{j=p}^{\infty}\frac{S^{\langle\mbox{cf}\rangle}_m(n)}{\alpha^{2j+1}}
=\frac{S^{\langle\mbox{cf}\rangle}_m(n)}{\alpha^{2p-1}(\alpha^2-1)}.
$$
Thus, from~(\ref{Ljwin3}) we have
\begin{eqnarray*}
\sum_{i=1}^s x_i\cdot |{\cal H}^{(w_i)}(n+1)|&\le&
\sum_{i=1}^s x_i\cdot A_p^{(w_i)}(n+1)+
\sum_{i=1}^s x_i\cdot B_p^{(w_i)}(n+1)\\
&<& S^{\langle\mbox{cf}\rangle}_m(n)\cdot\left({\cal P}_m^{(p,q)}(1/\alpha)+
\frac{1}{\alpha^{2p-1}(\alpha^2-1)}\right).
\end{eqnarray*}
Using this inequality and equalities (\ref{Fwin-3}) and~(\ref{rSmn3}), 
we obtain
\begin{eqnarray*}
S^{\langle\mbox{cf}\rangle}_m(n+1)&=&\sum_{i=1}^s x_i\cdot 
|{\cal G}^{(w_i)}(n+1)|-\sum_{i=1}^s x_i\cdot |{\cal H}^{(w_i)}(n+1)|\\
&>&S^{\langle\mbox{cf}\rangle}_m(n)\cdot\left(r-{\cal P}_m^{(p,q)}(1/\alpha)-
\frac{1}{\alpha^{2p-1}(\alpha^2-1)}\right).
\end{eqnarray*}
Therefore, if 
$$
r-{\cal P}_m^{(p,q)}(1/\alpha)-\frac{1}{\alpha^{2p-1}(\alpha^2-1)}
\ge\alpha, 
$$
then $S^{\langle\mbox{cf}\rangle}_m({n+1})\ge \alpha 
S^{\langle\mbox{cf}\rangle}_m(n)$ for any~$n$, i.~e. 
$S^{\langle\mbox{cf}\rangle}_m(n)=\Omega (\alpha^n)$. 
Since the order of growth of $S^{\langle\mbox{cf}\rangle}(n)$ 
is not less than $S^{\langle\mbox{cf}\rangle}_m(n)$, we 
obtain in this case that $S^{\langle\mbox{cf}\rangle}(n)=
\Omega (\alpha^n)$, i.~e. $\gamma^{\langle\mbox{cf}\rangle}\ge\alpha$.

Using computer computations with the parameters $m=35$, $p=35$, $q=70$,
we obtained that $|{\cal F}''(35)|=732274$, $r=1.457599$, all components 
of the eigenvector corresponding to~$r$ were positive, and
${\cal P}_{35}^{(35,70)}(z)$ was
$$
\begin{array}{l}
0.890340\cdot z^{35} + 1.398382\cdot z^{37} 
+ 1.096456\cdot z^{38} +  30.292784\cdot z^{40} + \\
2.533687\cdot z^{41} + 1.296919\cdot z^{42} + 28.893958\cdot z^{43} + 
22.780262\cdot z^{44} + \\
10.699704\cdot z^{45} +  64.314464\cdot z^{47} + 92.853910\cdot z^{49} +
91.743094\cdot z^{50} + \\
67.688387\cdot z^{51} +  48.613345\cdot z^{52} + 68.285930\cdot z^{53} +
113.239316\cdot z^{54} + \\
144.612325\cdot z^{56} +  346.136318\cdot z^{58} + 173.468149\cdot z^{59} +
465.000388\cdot z^{60} + \\
134.993653\cdot z^{61} +  224.831969\cdot z^{62} + 585.928351\cdot z^{63} +
355.591901\cdot z^{65} + \\
1335.518621\cdot z^{67} +  343.074473\cdot z^{68} + 2202.468159\cdot z^{69} +
11098.126369\cdot z^{70}.
\end{array}
$$
It is immediately checked that for $\alpha =1.457567$ the inequality
$$
r-{\cal P}_{35}^{(35,70)}(1/\alpha)-\frac{1}{\alpha^{69}(\alpha^2-1)}
\ge\alpha
$$ is valid. Moreover, the inequalities $S^{\langle\mbox{cf}\rangle}_{35}(n+1)
\ge \alpha S^{\langle\mbox{cf}\rangle}_{35}(n)$ for $n=35, 36,\ldots ,q+m-1=104$
are also verified in the same inductive way with evident modifications 
following from the restriction $n<q+m$. Thus $\gamma^{\langle\mbox{cf}
\rangle}\ge 1.457567$.

\section{Conclusions}

Basing on results of computer experiments, we believe that by increasing
the parameter~$m$, one can estimate $\gamma^{\langle\mbox{sf}\rangle}$,
$\gamma^{\langle\mbox{lf}\rangle}$, and $\gamma^{\langle\mbox{cf}\rangle}$ 
with an arbitrarily high precision. Note also that the proposed method for 
estimation of growth rates of repetition-free words is quite general: 
it can be applyed for estimating the growth rate of words over any finite 
alphabet with any (including fractional) minimal threshold for exponents 
of prohibited factors (provided that the growth is exponential). Moreover, 
this method can be easily modified for the case when additional restrictions 
are imposed on the minimal value of periods of prohibited factors 
(see~\cite{IlOchSh}). We suppose that this method can be also generalized 
for estimation of growth rates of words avoiding patterns (see, 
e.g.,~\cite{Currie}).

\section*{Acknowledgments}

The author is grateful to the referee of this paper for
his useful comments.

\begin{thebibliography}{99}

\bibitem[1]{BaElGr}
M. Baake, V. Elser, U. Grimm, The entropy of square-free words,
{\it Math. Comput. Modelling} {\bf 26} (1997), 13--26.

\bibitem[2]{Berst}
J. Berstel, Growth of repetition-free words --- a review,
{\it Theoret. Comput. Science} {\bf 340} (2005), 280--290.

\bibitem[3]{Brand}
F.-J. Brandenburg, Uniformly growing $k$-th power-free homomorphisms, 
{\it Theoret. Comput. Science} {\bf 23} (1983), 69--82. 

\bibitem[4]{Brink}
J. Brinkhuis, Nonrepetitive sequences on three symbols, 
{\it Quart. J. Math. Oxford} {\bf 34} (1983), 145--149.

\bibitem[5]{Carpi}
A. Carpi, On the Repetition Threshold for Large Alphabets,
{\it Lecture Notes in Computer Science} {\bf 4162} (2006),
226--237.

\bibitem[6]{Currie}
J. Currie, Open problems in pattern avoidance, {\it American Mathematical
Monthly}, {\bf 100} (1993), 790--793.

\bibitem[7]{Dejan}
F. Dejean, Sur un th\'eor\`eme de Thue,
{\it J. Combin. Theory, Ser.~A} {\bf 13} (1972), 90--99.

\bibitem[8]{Edlin}
A. Edlin, The number of binary cube-free words of length up to 47 and
their numerical analysis, {\it J. of Differential Equations and Applications} 
{\bf 5} (1999), 153--154.

\bibitem[9]{EkhZeil}
S.B. Ekhad, D. Zeilberger, There are more than $2^{n/17}$ $n$-letter
ternary square-free words, {\it J. Integer Sequences} (1998),
Article 98.1.9.

\bibitem[10]{Grimm}
U. Grimm, Improved bounds on the number of ternary square-free words, 
{\it J. Integer Sequences} (2001), Article 01.2.7.

\bibitem[11]{IlOchSh}
L. Ilie, P. Ochem, J. Shallit, A generalization of repetition threshold,
{\it Theoret. Comput. Science} {\bf 345} (2005), 359--369.

\bibitem[12]{WOWA}
R. Kolpakov, On the number of repetition-free words,
{\it Proceedings of Workshop on Words and Automata (WOWA'06)} 
(St Petersburg, June 2006).

\bibitem[13]{Moh-Noor}
M. Mohammad-Noori, J. Currie, Dejean's conjecture and Sturmian words,
{\it European J. of Combinatorics} {\bf 28} (2007), 876--890.

\bibitem[14]{Olag}
J. Moulin Ollagnier, Proof of Dejean's conjecture for alphabets with 5, 6, 7, 8, 9,
10 and 11 letters, {\it  Theoret. Comput. Science} {\bf 95} (1992), 187--205. 

\bibitem[15]{OchemTIA}
P. Ochem, A generator of morphisms for infinite words,
{\it Proceedings of Workshop on Word Avoidability, Complexity, and Morphisms}
(Turku, Finland, July 2004), 9--14.

\bibitem[16]{OchemWOWA}
P. Ochem, T. Reix, Upper bound on the number of ternary square-free words,
{\it Proceedings of Workshop on Words and Automata (WOWA'06)} 
(St Petersburg, June 2006).

\bibitem[17]{Pans}
J.J. Pansiot, A propos d'une conjecture de F.~Dejean sur les r\'ep\'etitions
dans les mots, {\it Discrete Appl. Math.} {\bf 7} (1984), 297--311.

\bibitem[18]{Sun}
X. Sun, New lower bound on the number of ternary square-free words,
{\it J. Integer Sequences} (2003), Article 03.2.2.

\bibitem[19]{Thue06}
A. Thue, \"Uber unendliche Zeichenreihen. 
{\it Norske Vidensk. Selsk. Skrifter. I. Mat.-Nat. Kl.} {\bf 7}
(Christiania, 1906), 1--22.

\bibitem[20]{Thue12}
A. Thue, \"Uber die gegenseitige Lage gleicher Teile gewisser 
Zeichenreihen. {\it Norske Vidensk. Selsk. Skrifter. I. Mat.-Nat. Kl.} 
{\bf 10} (Christiania, 1912), 1--\nolinebreak 67.

\end{thebibliography}


\bigskip
\hrule
\bigskip

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

\noindent {\it Keywords: } 
{\it combinatorics on words, repetition-free words, growth rate}.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received January 9 2007;
revised version received March 8 2007. 
Published in {\it Journal of Integer Sequences}, March 20 2007.

\bigskip
\hrule
\bigskip

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


\end{document}