Efficient Lower Bounds on the Number of Repetition-free Words

Roman Kolpakov^{1} Lomonosov Moscow State University Vorobjovy Gory 119992 Moscow Russia

                        foroman@mail.ru

Abstract

We propose a new effective method for obtaining lower bounds on the number of repetition-free words over a finite alphabet.

1 Introduction

Repetition-free words over finite alphabets are a traditional object of research in combinatorics of words. A word w over an alphabet Σ is a finite sequence a_{1} ⋯ a_{n} of symbols from Σ. The number n is called the length of w and is denoted by |w|. The symbol a_{i} of w is denoted by w[i]. A word a_{i} ⋯ a_{j}, where 1 ≤ i ≤ j ≤ n, is called a factor of w and is denoted by w[i : j]. For any i = 1, …, n the factor w[1 : i] (w[i : n]) is called a prefix (a suffix) of w. A positive integer p is called a period of w if a_{i} = a_{i+p} for each i = 1, …, n − p. If p is the minimal period of w, the ratio n/p is called the exponent of w. Two words w′, w′′ over Σ are called isomorphic if |w′| = |w′′| and there exists a bijection σ : Σ ⟶ Σ such that w′′[i] = σ(w′[i]), i = 1, …, |w′|. The set of all words over Σ is denoted by Σ^{∗}.

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 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., [4, 1]) that there exists the limit lim_{n→∞} \sqrt[n]{|W (n)|} which is called the growth rate of words from W. For any word v and any n ≥ |v| we denote by W^{(v)}(n) the set of all words from W (n) which contain v as a suffix.

1This 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).

By a repetition we mean any word of exponent greater than 1. The best known example of a repetition is a square; that is, a word of the form uu, where u is an arbitrary nonempty word. Avoiding ambiguity^{2}, by the period of the square uu we mean the length of u. In an analogous way, a cube is a word of the form uuu for a nonempty word u, a the period of this cube is also the length of u. A word is called square-free (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 [19, 20], there exist ternary square-free words of arbitrary length and binary cube-free words of arbitrary length. If we denote by S^{⟨sf⟩}(n) the number of ternary square-free words of length n and by S^{⟨cf⟩}(n) the number of binary cube-free words of length n, we then have that S^{⟨sf⟩}(n) > 0 and S^{⟨cf⟩}(n) > 0 for any n. For ternary square-free words this result was strengthened by Dejean in [7]. 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 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 ≥ 5. This conjecture was proved for k = 4 by Pansiot [17], for 5 ≤ k ≤ 11 by Moulin Ollagnier [14], for 12 ≤ k ≤ 14 by Mohammad-Noori and Currie [13], and for k ≥ 38 by Carpi [5]. Denote by S^{⟨lf⟩}(n) the number of minimally repetitive ternary words of length n. It follows from the result of Dejean that S^{⟨lf⟩}(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 γ^{⟨sf⟩} = lim_{n→∞} \sqrt[n]{S^{⟨sf⟩}(n)}, γ^{⟨cf⟩} = lim_{n→∞} \sqrt[n]{S^{⟨cf⟩}(n)}, γ^{⟨lf⟩} = lim_{n→∞} \sqrt[n]{S^{⟨lf⟩}(n)} of

words from these sets. Brandenburg proved in [3] that the values S^{⟨sf⟩}(n) and S^{⟨cf⟩}(n) grew exponentially with n, namely, S^{⟨sf⟩}(n) ≥ 6 · 1.032^{n} and S^{⟨cf⟩}(n) ≥ 2 · 1.080^{n}, i. e. γ^{⟨sf⟩} ≥ 1.032 and γ^{⟨cf⟩} ≥ 1.080. Later the lower bound for γ^{⟨sf⟩} was improved consecutively^{3} by Ekhad, Zeilberger, Grimm, and Sun in [9, 10, 18]. The best upper bounds known at present γ^{⟨sf⟩} < 1.30178858 and γ^{⟨cf⟩} < 1.4576 are obtained by Ochem and Edlin in [16] and [8] respectively. In [15] 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 γ^{⟨lf⟩}.

In [12] we proposed a new method for obtaining lower bounds on the number of repetitionfree 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 γ^{⟨sf⟩} ≥ 1.30125 and γ^{⟨cf⟩} ≥ 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 γ^{⟨lf⟩} 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 γ^{⟨sf⟩} ≥ 1.30173, γ^{⟨lf⟩} ≥ 1.245, and γ^{⟨cf⟩} ≥ 1.457567. Comparing the obtained lower bounds for γ^{⟨sf⟩} and γ^{⟨cf⟩} with the known upper bounds, one can conclude that we have estimated γ^{⟨sf⟩} and γ^{⟨cf⟩} within a precision of 0.0001, which demonstrates the high efficiency of the proposed modification.

2Note that the period of a square is not necessarily the minimal period of this word.

3A review of results on the estimations for the number of repetition-free words can be found in [2].

2 Estimation for the number of ternary square-free words

For obtaining a lower bound on γ^{⟨sf⟩} we consider the alphabet Σ_{3} = {0, 1, 2}. Denote the set of all square-free words from Σ_{3}^{∗} by F. Let m be a natural number, m > 2, and w′, w′′ be two words from F(m). We call the word w′′ a descendant of the word w′ if w′[2 : m] = w′′[1 : m−1] and w′w′′[m] = w′[1]w′′ ∈ F(m + 1). The word w′ is called in this case an ancestor of the word w′′. Further, we introduce a notion of closed words in the following inductive way. A word w from F(m) is called right closed (left closed) if and only if this word satisfies one of the two following conditions:

(a) Basis of induction. w has no descendants (ancestors);

(b) Inductive step. All descendants (ancestors) of w are right closed (left closed). A word is closed if it is either right closed or left closed. Denote by L_{m} the set of all words from Σ_{3}^{∗} which do not contain closed words from F(m) as factors. By F_{m} we denote the set of all square-free words from 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.

Proposition 2.1. For any isomorphic words w′, w′′ and any n ≥ |w′| the equality |F_{m}^{(w′)}(n)| = |F_{m}^{(w′′)}(n)| holds.

By F′(m) we denote the set of all words w from F(m) such that w[1] = 0 and w[2] = 1. It is obvious that for any word w from F(m) there exists a single word from F′(m) which is isomorphic to w. Let w′, w′′ be two words from F′(m). We call the word w′′ a quasidescendant of the word w′ if w′′ is isomorphic to some descendant of w′. The word w′ is called in this case a quasi-ancestor of the word w′′. Let F′′(m) be the set of all words from F′(m) which are not closed. Since ternary square-free words of arbitrary length exist, F′′(m) is not empty for any m. Denote s = |F′′(m)|. We enumerate all words from F′′(m) by numbers 1, 2, …, s in lexicographic order and denote i-th word of the set F′′(m) by w_{i}, i = 1, …, s. Then we define a matrix Δ_{m} = (δ_{ij}) of size s × s in the following way: δ_{ij} = 1 if and only if w_{i} is an quasi-ancestor of w_{j}; otherwise δ_{ij} = 0. Note that Δ_{m} is a nonnegative matrix, so, by Perron-Frobenius theorem, for Δ_{m} there exists some maximal in modulus eigenvalue r which is a nonnegative real number. Moreover, we can find some eigenvector x̃ = (x_{1}; …; x_{s}) with nonnegative components which corresponds to r. Assume that r > 1 and all components of x̃ are positive. For n ≥ m define S_{m}^{⟨sf⟩}(n) = ∑_{i=1}^{s} x_{i} · |F_{m}^{(w_{i})}(n)|. In

an inductive way we estimate S_{m}^{⟨sf⟩}(n + 1) by S_{m}^{⟨sf⟩}(n).

First we estimate |F_{m}^{(w_{i})}(n + 1)| for i = 1, …, s. It is obvious that

|F_{m}^{(w_{i})}(n + 1)| = |G^{(w_{i})}(n + 1)| − |H^{(w_{i})}(n + 1)|,  (1)

where G^{(w_{i})}(n+1) is the set of all words w from L_{m}^{(w_{i})}(n+1) such that the words w[1 : n] and w[n − m + 1 : n + 1] are square-free, and H^{(w_{i})}(n + 1) is the set of all words from G^{(w_{i})}(n + 1) which contain some square as a suffix. Denote by π(i) the set of all quasi-ancestors of w_{i}. Taking into account Proposition 2.1, it is easy to see that

|G^{(w_{i})}(n + 1)| = ∑_{w∈π(i)} |F_{m}^{(w)}(n)|.  (2)

We now estimate |H^{(w_{i})}(n+1)|. For any word w from H^{(w_{i})}(n+1) we can find the minimal square which is a suffix of w. Denote the period of this square by λ(w). It is obvious that ⌊(m + 1)/2⌋ < λ(w) ≤ ⌊(n + 1)/2⌋. Denote by H_{j}^{(w_{i})}(n + 1) the set of all words w from H^{(w_{i})}(n + 1) such that λ(w) = j. Then

|H^{(w_{i})}(n + 1)| = ∑_{⌊(m+1)/2⌋<j≤⌊(n+1)/2⌋} |H_{j}^{(w_{i})}(n + 1)|.  (3)

Take some integer p ≥ m and assume that n ≥ 2p. Consider a set H_{j}^{(w_{i})}(n + 1) where j ≤ 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 F(m) nor other squares as factors and contains the word w_{i} as a suffix. Let v_{1}, …, v_{t} be all possible squares of period j which satisfy the given conditions. Denote by H_{j,k}^{(w_{i})}(n + 1) the set of all words from H_{j}^{(w_{i})}(n + 1) which contain the square v_{k} as a suffix, k = 1, …, t. Let w ∈ 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] ≠ w[n − 2j + 2] = v_{k}[1] and w[n−2j+1] ≠ w[n−j+1] = v_{k}[j]. Moreover, v_{k}[1] = w[n−j+2] ≠ w[n−j+1] = v_{k}[j]. Thus, the symbol w[n−2j+1] is determined uniquely by v_{k} as the symbol from Σ_{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 F(m) as a factor then H_{j,k}^{(w_{i})}(n+1) = ∅. Let b_{k}v_{k}[1 : 2j−1] ∈ 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 |H_{j,k}^{(w_{i})}(n+1)| ≤ |F_{m}^{(u_{k})}(n−2j+m)|. Denote by u′_{k} the word from F′(m) which is isomorphic to u_{k}. Then, by Proposition 2.1, we have

|H_{j,k}^{(w_{i})}(n + 1)| ≤ |F_{m}^{(u′_{k})}(n − 2j + m)|.

Thus, denoting by U_{j}(w_{i}) the set of all words^{4} u′_{k}, we obtain that

|H_{j}^{(w_{i})}(n + 1)| = ∑_{k=1}^{t} |H_{j,k}^{(w_{i})}(n + 1)| ≤ ∑_{u∈U_{j}(w_{i})} |F_{m}^{(u)}(n − 2j + m)|.  (4)

4Note 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}).

Consider now the set H_{j}^{(w_{i})}(n + 1) for j > p. Note that in this case j > m. Let w be an arbitrary word from 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

|H_{j}^{(w_{i})}(n + 1)| ≤ |F_{m}^{(w_{i})}(n − j + 1)|.  (5)

holds. Using inequalities (4) and (5) in (3), we obtain

|H^{(w_{i})}(n + 1)| ≤ A_{p}^{(w_{i})}(n + 1) + B_{p}^{(w_{i})}(n + 1)  (6)

where

A_{p}^{(w_{i})}(n + 1) = ∑_{⌊(m+1)/2⌋<j≤p} ( ∑_{u∈U_{j}(w_{i})} |F_{m}^{(u)}(n − 2j + m)|) ,
B_{p}^{(w_{i})}(n + 1) = ∑_{p<j≤⌊(n+1)/2⌋} |F_{m}^{(w_{i})}(n − j + 1)|.

We now estimate S_{m}^{⟨sf⟩}(n + 1). Using equality (1), we have

S_{m}^{⟨sf⟩}(n + 1) = ∑_{i=1}^{s} x_{i} · |G^{(w_{i})}(n + 1)| − ∑_{i=1}^{s} x_{i} · |H^{(w_{i})}(n + 1)|.  (7)

Recall that x̃ is a eigenvector of Δ_{m} for the eigenvalue r. So, applying equality (2), we obtain

∑_{i=1}^{s} x_{i} · |G^{(w_{i})}(n + 1)| = ∑_{i=1}^{s}(x_{i} · ∑_{w∈π(i)} |F_{m}^{(w)}(n)|)

= (x_{1}; x_{2}; …; x_{s}) ( \begin{matrix}δ_{11} & δ_{21} & … & δ_{s1} \\ δ_{12} & δ_{22} & … & δ_{s2} \\ ⋮ & ⋮ & ... & ⋮ \\ δ_{1s} & δ_{2s} & … & δ_{ss} \end{matrix} ) ( |F_{m}^{(w_{1})}(n)| ; |F_{m}^{(w_{2})}(n)| ; ⋮ ; |F_{m}^{(w_{s})}(n)| )

= r · (x_{1}; x_{2}; …; x_{s}) ( |F_{m}^{(w_{1})}(n)| ; |F_{m}^{(w_{2})}(n)| ; ⋮ ; |F_{m}^{(w_{s})}(n)| ) = r · S_{m}^{⟨sf⟩}(n).  (8)

For estimating the second sum in the right side of (7) we use equality (6):

∑_{i=1}^{s} x_{i} · |H^{(w_{i})}(n + 1)| ≤ ∑_{i=1}^{s} x_{i} · A_{p}^{(w_{i})}(n + 1) + ∑_{i=1}^{s} x_{i} · B_{p}^{(w_{i})}(n + 1)  (9)

where

∑_{i=1}^{s} x_{i} · B_{p}^{(w_{i})}(n + 1) = ∑_{p<j≤⌊(n+1)/2⌋} (∑_{i=1}^{s} x_{i} · |F_{m}^{(w_{i})}(n − j + 1)|)
= ∑_{p<j≤⌊(n+1)/2⌋} S_{m}^{⟨sf⟩}(n − j + 1).  (10)

For k = 1, …, s denote by ζ_{j}^{(k)}(w_{i}) the number of words w_{k} in the set U_{j}(w_{i}), and define η_{k}(j) as ∑_{i=1}^{s} x_{i} · ζ_{j}^{(k)}(w_{i}). Note that any word from U_{j}(w_{i}) belongs to F′′(m). Hence

∑_{i=1}^{s} x_{i} · A_{p}^{(w_{i})}(n + 1) = ∑_{⌊(m+1)/2⌋<j≤p} ∑_{i=1}^{s} x_{i} ( ∑_{u∈U_{j}(w_{i})} |F_{m}^{(u)}(n − 2j + m)|)

= ∑_{⌊(m+1)/2⌋<j≤p} ∑_{k=1}^{s} η_{k}(j) · |F_{m}^{(w_{k})}(n − 2j + m)|.  (11)

Take some integer q ≥ 2p − m and assume that n ≥ q + m. For the sake of convenience we present sum (11) as

∑_{d=d_{0}}^{q} ∑_{k=1}^{s} η′_{k}(d) · |F_{m}^{(w_{k})}(n − d)|

where η′_{k}(d) = η_{k}((d+m)/2) if d+m is even, η′_{k}(d) = 0 otherwise, and d_{0} = 2·⌊(m+3)/2⌋−m.

We majorize this sum by some sum ∑_{d=d_{0}}^{q} ρ_{d} · S_{m}^{⟨sf⟩}(n − d) in the following way. We compute consecutively coefficients ρ_{d} of this sum for d = d_{0}, d_{0} + 1, …, q. For each d = d_{0}, d_{0} + 1, …, q − 1 together with the number ρ_{d} we compute also numbers η′′_{1}(d + 1), …, η′′_{s}(d + 1) such that

∑_{j=d_{0}}^{d+1} ∑_{k=1}^{s} η′_{k}(j) · |F_{m}^{(w_{k})}(n − j)| ≤ ∑_{k=1}^{s} η′′_{k}(d + 1) · |F_{m}^{(w_{k})}(n − d − 1)| + ∑_{j=d_{0}}^{d} ρ_{j} · S_{m}^{⟨sf⟩}(n − j). (12)

For d = d_{0} we take ρ_{d_{0}} = min_{1≤k≤s}(η′_{k}(d_{0})/x_{k}). Then

∑_{k=1}^{s} η′_{k}(d_{0}) · |F_{m}^{(w_{k})}(n − d_{0})| = ρ_{d_{0}} · S_{m}^{⟨sf⟩}(n − d_{0}) + ∑_{k=1}^{s} ν_{k} · |F_{m}^{(w_{k})}(n − d_{0})|

where ν_{k} = η′_{k}(d_{0}) − ρ_{d_{0}} · x_{k}, k = 1, …, s. Denote by ν̃ the vector (ν_{1}; …; ν_{s}) and consider the vector ν̃′ = Δ_{m}ν̃. Let ν̃′ = (ν′_{1}; …; ν′_{s}). It follows from (1) and (2) that

|F_{m}^{(w_{k})}(n − d_{0})| ≤ |G^{(w_{i})}(n − d_{0})| = ∑_{w∈π(k)} |F_{m}^{(w)}(n − d_{0} − 1)|

for any k = 1, …, s. Note also that ν_{k} ≥ 0 for k = 1, …, s. Hence

∑_{k=1}^{s} ν_{k} · |F_{m}^{(w_{k})}(n − d_{0})| ≤ ∑_{k=1}^{s} (ν_{k} · ∑_{w∈π(k)} |F_{m}^{(w)}(n − d_{0} − 1)|)

= ∑_{k=1}^{s} ν′_{k} · |F_{m}^{(w_{k})}(n − d_{0} − 1)|.

Thus

∑_{j=d_{0}}^{d_{0}+1} ∑_{k=1}^{s} η′_{k}(j) · |F_{m}^{(w_{k})}(n − j)| ≤ ρ_{d_{0}} · S_{m}^{⟨sf⟩}(n − d_{0}) + ∑_{k=1}^{s} η′′_{k}(d_{0} + 1) · |F_{m}^{(w_{k})}(n − d_{0} − 1)| (13)

where η′′_{k}(d_{0} + 1) = η′_{k}(d_{0} + 1) + ν′_{k}. Assume now that for some d such that d_{0} < d < q we already computed the numbers ρ_{d_{0}}, …, ρ_{d−1} and η′′_{1}(d), …, η′′_{s}(d). Then we take ρ_{d} = min_{1≤k≤s}(η′′_{k}(d)/x_{k}), ν̃ = (η′′_{1}(d) − ρ_{d} · x_{1}, …, η′′_{s}(d) − ρ_{d} · x_{s}), and ν̃′ = Δ_{m}ν̃. We take also η′′_{k}(d + 1) = η′_{k}(d + 1) + ν′_{k} where ν′_{k} is the k-th component of the vector ν̃′, k = 1, …, s. Analogously to inequality (13), in this case we have the inequality

\begin{matrix}∑_{k=1}^{s} & (η′′_{k}(d) · |F_{m}^{(w_{k})}(n − d)| + η′_{k}(d + 1) · |F_{m}^{(w_{k})}(n − d − 1)|) \\ ≤ ρ_{d} · S_{m}^{⟨sf⟩}(n − d) + ∑_{k=1}^{s} η′′_{k}(d + 1) · |F_{m}^{(w_{k})}(n − d − 1)|. \end{matrix}

This inequality implies that inequality (12) holds for every d. For d = q we take ρ_{q} = max_{1≤k≤s}(η′′_{k}(q)/x_{k}). Thus,

∑_{i=1}^{s} x_{i}A_{p}^{(w_{i})}(n + 1) = ∑_{d=d_{0}}^{q} ∑_{k=1}^{s} η′_{k}(d) · |F_{m}^{(w_{k})}(n − d)| ≤ ∑_{d=d_{0}}^{q} ρ_{d} · S_{m}^{⟨sf⟩}(n − d).  (14)

For the sake of convenience denote by P_{m}^{(p,q)}(z) the polynomial ∑_{d=d_{0}}^{q} ρ_{d} · z^{d} in a variable z.

Let for some α > 1 and each i = m, m+1, …, n−1 the inequality S_{m}^{⟨sf⟩}(i+1) ≥ αS_{m}^{⟨sf⟩}(i) be valid. Then for each i = m, m + 1, …, n − 1 we have S_{m}^{⟨sf⟩}(i) ≤ S_{m}^{⟨sf⟩}(n)/α^{n−i}. So relation (14) implies that

∑_{i=1}^{s} x_{i} · A_{p}^{(w_{i})}(n + 1) ≤ ∑_{d=d_{0}}^{q} ρ_{d} · (S_{m}^{⟨sf⟩}(n)/α^{d}) = P_{m}^{(p,q)}(1/α) · S_{m}^{⟨sf⟩}(n).

In an analogous way relation (10) implies that

∑_{i=1}^{s} x_{i}B_{p}^{(w_{i})}(n + 1) ≤ ∑_{p<j≤⌊(n+1)/2⌋} S_{m}^{⟨sf⟩}(n)/α^{j−1} < S_{m}^{⟨sf⟩}(n) · ∑_{j=p}^{∞} 1/α^{j}

= \frac{S_{m}^{⟨sf⟩}(n)}{α^{p−1}(α − 1)}.

Thus, from (9) we have

∑_{i=1}^{s} x_{i} · |H^{(w_{i})}(n + 1)| < S_{m}^{⟨sf⟩}(n) · (P_{m}^{(p,q)}(1/α) + \frac{1}{α^{p−1}(α − 1)}) .

Using this inequality together with equality (8) in (7), we obtain

S_{m}^{⟨sf⟩}(n + 1) > S_{m}^{⟨sf⟩}(n) · (r − P_{m}^{(p,q)}(1/α) − \frac{1}{α^{p−1}(α − 1)}) .

Therefore, if α satisfy the inequality

r − P_{m}^{(p,q)}(1/α) − \frac{1}{α^{p−1}(α − 1)} ≥ α,

we obtain inductively that the inequality S_{m}^{⟨sf⟩}(n + 1) ≥ αS_{m}^{⟨sf⟩}(n) holds for any n. Thus, in this case we have S_{m}^{⟨sf⟩}(n) = Ω(α^{n}). Since, obviously, the order of growth of S^{⟨sf⟩}(n) is not less than S_{m}^{⟨sf⟩}(n), we then conclude that S^{⟨sf⟩}(n) = Ω(α^{n}). Hence γ^{⟨sf⟩} ≥ α.

For obtaining a concrete lower bound on γ^{⟨sf⟩} we take the parameters m = 45, p = 52, q = 60. Using computer computations, we have obtained^{5} that |F′′(45)| = 277316, the maximal in modulus eigenvalue r for Δ_{45} is 1.302011, and all components of the eigenvector corresponding to r are positive. Further, we obtained that

P_{45}^{(52,60)}(z) = 3.759479 · z^{44} + 3.176743 · z^{45} + 6.048526 · z^{46}+
7.120005 · z^{48} + 14.679230 · z^{50} + 41.594270 · z^{52} + 37.431675 · z^{55}+
40.471892 · z^{56} + 32.780085 · z^{58} + 5.235193 · z^{59} + 275.705551 · z^{60}.

Let α = 1.30173. It is immediately checked that

r − P_{45}^{(52,60)}(1/α) − \frac{1}{α^{51}(α − 1)} ≥ α.

Moreover, the inequalities S_{45}^{⟨sf⟩}(n+1) ≥ αS_{45}^{⟨sf⟩}(n) for each n = 45, 46, …, 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 γ^{⟨sf⟩} ≥ 1.30173.

3 Estimation for the number of minimally repetitive ternary words

For obtaining a lower bound on γ^{⟨lf⟩} we also consider words over Σ_{3}. Now denote by F the set of all minimally repetitive words from Σ_{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 L_{m} the set of all words from Σ_{3}^{∗} which do not contain closed words from F(m) as factors. Denote also by F_{m} the set of all minimally repetitive words from L_{m}, by F′(m) the set of all words w from F(m) such that w[1] = 0 and w[2] = 1, and by F′′(m) the set of all words from 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 F′′(m) the matrix Δ_{m} of size s × s where s = |F′′(m)|, and compute the maximal in modulus eigenvalue r of this matrix. If r > 1 and all components of the eigenvector x̃ = (x_{1}; …; x_{s}) corresponding to r are positive, then we denote by μ the ratio max_{i} x_{i}/ min_{i} x_{i}, and for n ≥ m consider S_{m}^{⟨lf⟩}(n) = ∑_{i=1}^{s} x_{i} · |F_{m}^{(w_{i})}(n)| where w_{i} is i-th word of the set F′′(m), i = 1, …, s.

Analogously to equality (1), for i = 1, …, s we have

|F_{m}^{(w_{i})}(n + 1)| = |G^{(w_{i})}(n + 1)| − |H^{(w_{i})}(n + 1)|  (15)

5In this paper the obtained numerical results are given with precision of 6 decimal digits after the point.

where G^{(w_{i})}(n+1) is the set of all words w from L_{m}^{(w_{i})}(n+1) such that the words w[1 : n] and w[n − m + 1 : n + 1] are minimally repetitive, and H^{(w_{i})}(n + 1) is the set of all words from G^{(w_{i})}(n+1) which contain some prohibited repetition as a suffix. Analogously to equality (2), we can obtain

|G^{(w_{i})}(n + 1)| = ∑_{w∈π(i)} |F_{m}^{(w)}(n)|

where π(i) is the set of all quasi-ancestors of w_{i}. For any word w from H^{(w_{i})}(n + 1) denote by λ(w) the minimal period of the shortest prohibited repetition which is a suffix of w. Then, analogously to equality (3),

|H^{(w_{i})}(n + 1)| = ∑_{⌊(4m+3)/7⌋<j≤⌊4n/7⌋} |H_{j}^{(w_{i})}(n + 1)|,

where H_{j}^{(w_{i})}(n + 1) is the set of all words w from H^{(w_{i})}(n + 1) such that λ(w) = j. Take some integer p ≥ 4m/3 − 1 and assume that n > ⌊7p/4⌋. Let w be an arbitrary word from H_{j}^{(w_{i})}(n + 1) where j ≤ p. Then the suffix w[n − ⌊7p/4⌋ + 1 : n + 1] is a prohibited repetition which contains neither closed words from F(m) nor other prohibited repetitions as factors and contains the word w_{i} as a suffix. Let v_{1}, …, v_{t} be all possible prohibited repetitions with minimal period j which satisfy the given conditions. Denote by H_{j,k}^{(w_{i})}(n + 1) the set of all words from H_{j}^{(w_{i})}(n + 1) which contain v_{k} as a suffix, k = 1, …, t. Let w ∈ H_{j,k}^{(w_{i})}(n + 1). Analogously to the case of square-free words, the symbol w[n−⌊7j/4⌋] is determined uniquely by v_{k} as the symbol from Σ_{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 − ⌊7j/4⌋ : n] is determined uniquely as the word b_{k}v_{k}[1 : ⌊7j/4⌋]. Let this word belong to F_{m}. Then we denote by u′_{k} the word from F′(m) which is isomorphic to the word b_{k}v_{k}[1 : m − 1]. Analogously to inequality (4), one can obtain the inequality

|H_{j}^{(w_{i})}(n + 1)| ≤ ∑_{u∈U_{j}(w_{i})} |F_{m}^{(u)}(n + m − ⌊7j/4⌋ − 1)|

where U_{j}(w_{i}) is the set of all words^{6} u′_{k}. Thus,

|H^{(w_{i})}(n + 1)| ≤ A_{p}^{(w_{i})}(n + 1) + ∑_{p<j≤⌊4n/7⌋} |H_{j}^{(w_{i})}(n + 1)|  (16)

where

A_{p}^{(w_{i})}(n + 1) = ∑_{⌊(4m+3)/7⌋<j≤p} ( ∑_{u∈U_{j}(w_{i})} |F_{m}^{(u)}(n + m − ⌊7j/4⌋ − 1)|) .

From (15) and (16) we obtain that

S_{m}^{⟨lf⟩}(n + 1) ≥ ∑_{i=1}^{s} x_{i} · |G^{(w_{i})}(n + 1)| − ∑_{i=1}^{s} x_{i} · |A_{p}^{(w_{i})}(n + 1)| −

∑_{p<j≤⌊4n/7⌋} (∑_{i=1}^{s} x_{i} · |H_{j}^{(w_{i})}(n + 1)|) .  (17)

6Note that, as in the case of square-free words, the same word can be counted several times in U_{j}(w_{i}).

Analogously to equality (8), the equality

∑_{i=1}^{s} x_{i} · |G^{(w_{i})}(n + 1)| = r · S_{m}^{⟨lf⟩}(n)  (18)

is valid. Let j > p, i.e., j ≥ 4m/3. Note that the sets H_{j}^{(w_{i})}(n + 1) are non-overlapping. So we have the obvious inequality

∑_{i=1}^{s} x_{i} · |H_{j}^{(w_{i})}(n + 1)| ≤ |M_{j}| · max_{i=1,...,s} x_{i}  (19)

where M_{j} = ⋃_{i=1}^{s} H_{j}^{(w_{i})}(n + 1). Note also that any word w from M_{j} is determined uniquely by the prefix w[1 : n−⌊3j/4⌋] 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 |M_{j}| ≤ |M′_{j}| where M′_{j} is the set of all words w from F_{m}(n − ⌊3j/4⌋) such that w[n + 2 − m − j] = 0 and w[n + 3 − m − j] = 1. Consider also the set M′′_{j} of all words w from F_{m}(n − ⌊3j/4⌋) such that w[n + 1 − ⌊3j/4⌋ − m] = 0 and w[n + 2 − ⌊3j/4⌋ − m] = 1. There is an evident bijection between the sets M′_{j} and M′′_{j}, so |M′_{j}| = |M′′_{j}|. Note also that the set M′′_{j} is the union of the non-overlapping sets H_{j}^{(w_{i})}(n − ⌊3j/4⌋) for i = 1, …, s, i.e.,

|M′′_{j}| ≤ ∑_{i=1}^{s} |H_{j}^{(w_{i})}(n − ⌊3j/4⌋)| ≤ S_{m}^{⟨lf⟩}(n − ⌊3j/4⌋)/( min_{i=1,...,s} x_{i}).

Therefore, it follows from (19) that

∑_{i=1}^{s} x_{i} · |H_{j}^{(w_{i})}(n + 1)| ≤ |M′_{j}| · max_{i=1,...,s} x_{i} = |M′′_{j}| · max_{i=1,...,s} x_{i} ≤ μ · S_{m}^{⟨lf⟩}(n − ⌊3j/4⌋).

Thus,

∑_{p<j≤⌊4n/7⌋} (∑_{i=1}^{s} x_{i} · |H_{j}^{(w_{i})}(n + 1)|) ≤ μ · ∑_{p<j≤⌊4n/7⌋} S_{m}^{⟨lf⟩}(n − ⌊3j/4⌋).  (20)

Let η_{k}(j) = ∑_{i=1}^{s} x_{i} · ζ_{j}^{(k)}(w_{i}) where ζ_{j}^{(k)}(w_{i}) is the number of words w_{k} in the set U_{j}(w_{i}), k = 1, …, s. Then, analogously to equality (11),

∑_{i=1}^{s} x_{i} · |A_{p}^{(w_{i})}(n + 1)| = ∑_{⌊(4m+3)/7⌋<j≤p} ∑_{k=1}^{s} η_{k}(j) · |F_{m}^{(w_{k})}(n + m − ⌊7j/4⌋ − 1)|.  (21)

Take some integer q ≥ ⌊7p/4⌋ + 1 − m and assume that n ≥ q + m. Analogously to the case of square-free words, sum (21) can be majorized by some sum ∑_{d=d_{0}}^{q} ρ_{d} · S_{m}(n − d) where d_{0} = ⌊7j_{0}/4⌋ + 1 − m for j_{0} = ⌊(4m + 3)/7⌋ + 1.

Let for some α > 1 and each i = m, m + 1, …, n − 1 the inequality S_{m}^{⟨lf⟩}(i + 1) ≥ αS_{m}^{⟨lf⟩}(i) be valid, i.e., S_{m}^{⟨lf⟩}(i) ≤ S_{m}^{⟨lf⟩}(n)/α^{n−i}. Then

∑_{i=1}^{s} x_{i} · A_{p}^{(w_{i})}(n + 1) ≤ ∑_{d=d_{0}}^{q} ρ_{d} · (S_{m}^{⟨lf⟩}(n)/α^{d}) = P_{m}^{(p,q)}(1/α) · S_{m}^{⟨lf⟩}(n)  (22)

where P_{m}^{(p,q)}(z) = ∑_{d=d_{0}}^{q} ρ_{d} · z^{d}. Moreover, it follows from (20) that

∑_{p<j≤⌊4n/7⌋} (∑_{i=1}^{s} x_{i} · |H_{j}^{(w_{i})}(n + 1)|) ≤ μ · ∑_{p<j≤⌊4n/7⌋} S_{m}^{⟨lf⟩}(n)/α^{⌊3j/4⌋}

< μS_{m}^{⟨lf⟩}(n) · ∑_{p<j} 1/α^{⌊3j/4⌋}

= μS_{m}^{⟨lf⟩}(n) · ( ∑_{j≥⌊3(p+1)/4⌋} 1/α^{j} + ∑_{j≥⌈(p+1)/4⌉} 1/α^{3j})

= μS_{m}^{⟨lf⟩}(n) · (1/(α^{⌊(3p−1)/4⌋}(α − 1)) + 1/(α^{3⌊p/4⌋}(α^{3} − 1))).

Thus, from inequality (17) together with relations (18) and (22) we obtain that

S_{m}^{⟨lf⟩}(n + 1) > S_{m}^{⟨lf⟩}(n) · (r − P_{m}^{(p,q)}(1/α) −

μ · (1/(α^{⌊(3p−1)/4⌋}(α − 1)) + 1/(α^{3⌊p/4⌋}(α^{3} − 1)))).

Therefore, if

r − P_{m}^{(p,q)}(1/α) − μ · (1/(α^{⌊(3p−1)/4⌋}(α − 1)) + 1/(α^{3⌊p/4⌋}(α^{3} − 1))) ≥ α

then S_{m}^{⟨lf⟩}(n + 1) ≥ αS_{m}^{⟨lf⟩}(n) for any n, i.e., S_{m}^{⟨lf⟩}(n) = Ω(α^{n}). Since the order of growth of S^{⟨lf⟩}(n) is not less than S_{m}^{⟨lf⟩}(n), in this case we have S^{⟨lf⟩}(n) = Ω(α^{n}), i.e., γ^{⟨lf⟩} ≥ α.

Using computer computations with the parameters m = 42, p = 72, q = 85, we obtained that |F′′(42)| = 36141, r = 1.247500, all components of the eigenvector corresponding to r were positive, and P_{42}^{(72,85)}(z) was

1.976268 · z^{42} + 1.148062 · z^{44} + 3.519576 · z^{45} + 1.741046 · z^{47}+
9.687624 · z^{49} + 0.126312 · z^{50} + 31.479339 · z^{52} + 12.284335 · z^{53}+
21.010557 · z^{54} + 24.183001 · z^{56} + 96.529327 · z^{61} + 129.216325 · z^{64}+
256.213310 · z^{66} + 14.826731 · z^{67} + 64.163103 · z^{68} + 6.862805 · z^{69}+
84.819931 · z^{70} + 2.337610 · z^{72} + 175.026144 · z^{73} + 41.068102 · z^{74}+
335.714818 · z^{75} + 341.576384 · z^{78} + 329.970329 · z^{80} + 693.282157 · z^{81}+
763.104210 · z^{82} + 303.272754 · z^{83} + 583.157071 · z^{84} + 10510.070498 · z^{85}.

Let α = 1.245. It is immediately checked that

r − P_{42}^{(72,85)}(1/α) − \frac{1}{α^{53}(α − 1)} − \frac{1}{α^{54}(α^{3} − 1)} ≥ α.

Moreover, we estimate S_{42}^{⟨lf⟩}(n + 1) ≥ αS_{42}^{⟨lf⟩}(n) for each n = 42, 43, …, q + m − 1 = 126 in the same inductive way with evident modifications following from the restriction n < q + m. Thus we obtain that γ^{⟨lf⟩} ≥ 1.245.

4 Estimation for the number of binary cube-free words

To obtain a lower bound on γ^{⟨cf⟩}, we consider the alphabet Σ_{2} = {0, 1}. Denote by F the set of all cube-free words from Σ_{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 L_{m} the set of all words from Σ_{2}^{∗} which do not contain closed words from F(m) as factors, and by F_{m} the set of all cube-free words from L_{m}. By F′(m) we denote the set of all words w from F(m) such that w[1] = 0. Note that for any word w from F(m) there exists a single word from F′(m) which is isomorphic to w. By F′′(m) we denote the set of all words from F′(m) which are not closed. We introduce also the notions of quasi-descendant and quasi-ancestor, define for F′′(m) the matrix Δ_{m} of size s × s where s = |F′′(m)|, and compute the maximal in modulus eigenvalue r of this matrix. If r > 1 and all components of the eigenvector x̃ = (x_{1}; …; x_{s}) corresponding to r are positive, then for n ≥ m we consider S_{m}^{⟨cf⟩}(n) = ∑_{i=1}^{s} x_{i} · |F_{m}^{(w_{i})}(n)| where w_{i} is i-th word of the set F′′(m), i = 1, …, s.

As in the case of square-free words, for i = 1, …, s we have

|F_{m}^{(w_{i})}(n + 1)| = |G^{(w_{i})}(n + 1)| − |H^{(w_{i})}(n + 1)|  (23)

where G^{(w_{i})}(n+1) is the set of all words w from L_{m}^{(w_{i})}(n+1) such that the words w[1 : n] and w[n − m + 1 : n + 1] are cube-free, and H^{(w_{i})}(n + 1) is the set of all words from G^{(w_{i})}(n + 1) which contain some cube as a suffix. Analogously to equality (2), we obtain

|G^{(w_{i})}(n + 1)| = ∑_{w∈π(i)} |F_{m}^{(w)}(n)|

where π(i) is the set of all quasi-ancestors of w_{i}. For any word w from H^{(w_{i})}(n + 1) denote by λ(w) the period of the minimal cube which is a suffix of w. Then, analogously to equality (3),

|H^{(w_{i})}(n + 1)| = ∑_{⌊(m+1)/3⌋<j≤⌊(n+1)/3⌋} |H_{j}^{(w_{i})}(n + 1)|,  (24)

where H_{j}^{(w_{i})}(n + 1) is the set of all words w from H^{(w_{i})}(n + 1) such that λ(w) = j. Take some integer p ≥ m and assume that n ≥ 3p. Let w be an arbitrary word from H_{j}^{(w_{i})}(n + 1) where j ≤ p. Then the suffix w[n − 3j + 2 : n + 1] is a cube which contains neither closed words from F(m) nor other cubes as factors and contains the word w_{i} as a suffix. Let v_{1}, …, v_{t} be all possible cubes of period j which satisfy the given conditions. Denote by H_{j,k}^{(w_{i})}(n + 1) the set of all words from H_{j}^{(w_{i})}(n + 1) which contain the cube v_{k} as a suffix, k = 1, …, t. Let w ∈ 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] ≠ w[n − 2j + 1] = v_{k}[j]. Thus, the symbol w[n − 3j + 1] is determined uniquely by v_{k} as the symbol from Σ_{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 F(m) as factors then we denote by u′_{k} the word from F′(m) which is isomorphic to w[n − 3j + 1 : n − 3j + m].

Analogously to inequality (4), one can obtain the inequality

|H_{j}^{(w_{i})}(n + 1)| ≤ ∑_{u∈U_{j}(w_{i})} |F_{m}^{(u)}(n − 3j + m)|  (25)

where U_{j}(w_{i}) is the set of all words^{7} u′_{k}. For j > p, analogously to inequality (5), we have

|H_{j}^{(w_{i})}(n + 1)| ≤ |F_{m}^{(w_{i})}(n − 2j + 1)|.  (26)

Thus, from (24), (25) and (26) we obtain that

|H^{(w_{i})}(n + 1)| ≤ A_{p}^{(w_{i})}(n + 1) + B_{p}^{(w_{i})}(n + 1)  (27)

where

A_{p}^{(w_{i})}(n + 1) = ∑_{⌊(m+1)/3⌋<j≤p} ( ∑_{u∈U_{j}(w_{i})} |F_{m}^{(u)}(n − 3j + m)|) ,
B_{p}^{(w_{i})}(n + 1) = ∑_{p<j≤⌊(n+1)/3⌋} |F_{m}^{(w_{i})}(n − 2j + 1)|.

Moreover, analogously to equalities (8) and (10), the equalities

∑_{i=1}^{s} x_{i} · |G^{(w_{i})}(n + 1)| = r · S_{m}^{⟨cf⟩}(n)  (28)

and

∑_{i=1}^{s} x_{i} · B_{p}^{(w_{i})}(n + 1) = ∑_{p<j≤⌊(n+1)/3⌋} S_{m}^{⟨cf⟩}(n − 2j + 1)  (29)

hold. Let η_{k}(j) = ∑_{i=1}^{s} x_{i} · ζ_{j}^{(k)}(w_{i}) where ζ_{j}^{(k)}(w_{i}) is the number of words w_{k} in the set U_{j}(w_{i}), k = 1, …, s. Then, analogously to equality (11),

∑_{i=1}^{s} x_{i} · A_{p}^{(w_{i})}(n + 1) = ∑_{⌊(m+1)/3⌋<j≤p} ∑_{k=1}^{s} η_{k}(j) · |F_{m}^{(w_{k})}(n − 3j + m)|.  (30)

Take some integer q ≥ 3p − m and assume that n ≥ q + m. Analogously to the case of square-free words, sum (30) can be majorized by some sum ∑_{d=d_{0}}^{q} ρ_{d} · S_{m}^{⟨cf⟩}(n − d) where d_{0} = 3 · ⌊(m + 4)/3⌋ − m.

Let for some α > 1 and each i = m, m+1, …, n−1 the inequalities S_{m}^{⟨cf⟩}(i+1) ≥ αS_{m}^{⟨cf⟩}(i) be valid. Then

∑_{i=1}^{s} x_{i} · A_{p}^{(w_{i})}(n + 1) ≤ ∑_{d=d_{0}}^{q} ρ_{d} · (S_{m}^{⟨cf⟩}(n)/α^{d}) = P_{m}^{(p,q)}(1/α) · S_{m}^{⟨cf⟩}(n),

7Note that, as in the case of square-free words, the same word can be counted several times in U_{j}(w_{i}).

∑_{i=1}^{s} x_{i} · B_{p}^{(w_{i})}(n + 1) ≤ ∑_{p<j≤⌊(n+1)/3⌋} \frac{S_{m}^{⟨cf⟩}(n)}{α^{2j−1}} < ∑_{j=p}^{∞} \frac{S_{m}^{⟨cf⟩}(n)}{α^{2j+1}} = \frac{S_{m}^{⟨cf⟩}(n)}{α^{2p−1}(α^{2} − 1)}.

Thus, from (27) we have

∑_{i=1}^{s} x_{i} · |H^{(w_{i})}(n + 1)| ≤ ∑_{i=1}^{s} x_{i} · A_{p}^{(w_{i})}(n + 1) + ∑_{i=1}^{s} x_{i} · B_{p}^{(w_{i})}(n + 1)

< S_{m}^{⟨cf⟩}(n) · (P_{m}^{(p,q)}(1/α) + \frac{1}{α^{2p−1}(α^{2} − 1)}) .

Using this inequality and equalities (23) and (28), we obtain

S_{m}^{⟨cf⟩}(n + 1) = ∑_{i=1}^{s} x_{i} · |G^{(w_{i})}(n + 1)| − ∑_{i=1}^{s} x_{i} · |H^{(w_{i})}(n + 1)|

> S_{m}^{⟨cf⟩}(n) · (r − P_{m}^{(p,q)}(1/α) − \frac{1}{α^{2p−1}(α^{2} − 1)}) .

Therefore, if

r − P_{m}^{(p,q)}(1/α) − \frac{1}{α^{2p−1}(α^{2} − 1)} ≥ α,

then S_{m}^{⟨cf⟩}(n + 1) ≥ αS_{m}^{⟨cf⟩}(n) for any n, i. e. S_{m}^{⟨cf⟩}(n) = Ω(α^{n}). Since the order of growth of S^{⟨cf⟩}(n) is not less than S_{m}^{⟨cf⟩}(n), we obtain in this case that S^{⟨cf⟩}(n) = Ω(α^{n}), i. e. γ^{⟨cf⟩} ≥ α.

Using computer computations with the parameters m = 35, p = 35, q = 70, we obtained that |F′′(35)| = 732274, r = 1.457599, all components of the eigenvector corresponding to r were positive, and P_{35}^{(35,70)}(z) was

0.890340 · z^{35} + 1.398382 · z^{37} + 1.096456 · z^{38} + 30.292784 · z^{40}+
2.533687 · z^{41} + 1.296919 · z^{42} + 28.893958 · z^{43} + 22.780262 · z^{44}+
10.699704 · z^{45} + 64.314464 · z^{47} + 92.853910 · z^{49} + 91.743094 · z^{50}+
67.688387 · z^{51} + 48.613345 · z^{52} + 68.285930 · z^{53} + 113.239316 · z^{54}+
144.612325 · z^{56} + 346.136318 · z^{58} + 173.468149 · z^{59} + 465.000388 · z^{60}+
134.993653 · z^{61} + 224.831969 · z^{62} + 585.928351 · z^{63} + 355.591901 · z^{65}+
1335.518621 · z^{67} + 343.074473 · z^{68} + 2202.468159 · z^{69} + 11098.126369 · z^{70}.

It is immediately checked that for α = 1.457567 the inequality

r − P_{35}^{(35,70)}(1/α) − \frac{1}{α^{69}(α^{2} − 1)} ≥ α

is valid. Moreover, the inequalities S_{35}^{⟨cf⟩}(n+1) ≥ αS_{35}^{⟨cf⟩}(n) for n = 35, 36, …, q+m−1 = 104 are also verified in the same inductive way with evident modifications following from the restriction n < q + m. Thus γ^{⟨cf⟩} ≥ 1.457567.

5 Conclusions

Basing on results of computer experiments, we believe that by increasing the parameter m, one can estimate γ^{⟨sf⟩}, γ^{⟨lf⟩}, and γ^{⟨cf⟩} 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 [11]). We suppose that this method can be also generalized for estimation of growth rates of words avoiding patterns (see, e.g., [6]).

Acknowledgments

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

References

[1] M. Baake, V. Elser, U. Grimm, The entropy of square-free words, Math. Comput. Modelling 26 (1997), 13–26.

[2] J. Berstel, Growth of repetition-free words — a review, Theoret. Comput. Science 340 (2005), 280–290.

[3] F.-J. Brandenburg, Uniformly growing k-th power-free homomorphisms, Theoret. Comput. Science 23 (1983), 69–82.

[4] J. Brinkhuis, Nonrepetitive sequences on three symbols, Quart. J. Math. Oxford 34 (1983), 145–149.

[5] A. Carpi, On the Repetition Threshold for Large Alphabets, Lecture Notes in Computer Science 4162 (2006), 226–237.

[6] J. Currie, Open problems in pattern avoidance, American Mathematical Monthly, 100 (1993), 790–793.

[7] F. Dejean, Sur un théorème de Thue, J. Combin. Theory, Ser. A 13 (1972), 90–99.

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

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

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

[11] L. Ilie, P. Ochem, J. Shallit, A generalization of repetition threshold, Theoret. Comput. Science 345 (2005), 359–369.

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

[13] M. Mohammad-Noori, J. Currie, Dejean’s conjecture and Sturmian words, European J. of Combinatorics 28 (2007), 876–890.

[14] J. Moulin Ollagnier, Proof of Dejean’s conjecture for alphabets with 5, 6, 7, 8, 9, 10 and 11 letters, Theoret. Comput. Science 95 (1992), 187–205.

[15] P. Ochem, A generator of morphisms for infinite words, Proceedings of Workshop on Word Avoidability, Complexity, and Morphisms (Turku, Finland, July 2004), 9–14.

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

[17] J.J. Pansiot, A propos d’une conjecture de F. Dejean sur les répétitions dans les mots, Discrete Appl. Math. 7 (1984), 297–311.

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

[19] A. Thue, Über unendliche Zeichenreihen. Norske Vidensk. Selsk. Skrifter. I. Mat.-Nat. Kl. 7 (Christiania, 1906), 1–22.

[20] A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske Vidensk. Selsk. Skrifter. I. Mat.-Nat. Kl. 10 (Christiania, 1912), 1–67.

2000 Mathematics Subject Classification: Primary 05A20; Secondary 68R15. Keywords: combinatorics on words, repetition-free words, growth rate.

(Concerned with sequence \underline{A006156}.)

Received January 9 2007; revised version received March 8 2007. Published in Journal of Integer Sequences, March 20 2007.

Return to Journal of Integer Sequences home page.