The Number of Threshold Words on n Letters Grows Exponentially for Every n ≥ 27

James D. Currie^{1}, Lucas Mol, and Narad Rampersad^{2} Department of Mathematics and Statistics University of Winnipeg 515 Portage Avenue Winnipeg, MB R3B 2E9 Canada j.currie@uwinnipeg.ca l.mol@uwinnipeg.ca n.rampersad@uwinnipeg.ca

Abstract For every n ≥ 27, we show that the number of n/(n−1)^{+}-free words (i.e., threshold words) of length k on n letters grows exponentially in k. This settles all but finitely many cases of a conjecture of Ochem.

1 Introduction

Throughout, we use standard definitions and notations from combinatorics on words (see [13]). A square is a word of the form xx, where x is a nonempty word. A cube is a word of the form xxx, where x is a nonempty word. An overlap is a word of the form axaxa, where a is a letter and x is a (possibly empty) word. The study of words goes back to Thue, who demonstrated the existence of an infinite overlap-free word over a binary alphabet, and an infinite square-free word over a ternary alphabet (see [1]).

1The work of James D. Currie is supported by the Natural Sciences and Engineering Research Council of Canada (NSERC), [funding reference number 2017-03901].

2The work of Narad Rampersad is supported by the Natural Sciences and Engineering Research Council of Canada (NSERC), [funding reference number 2019-04111].

A language is a set of finite words over some alphabet A. The combinatorial complexity of a language L is the sequence C_{L} : ℕ → ℕ, where C_{L}(k) is defined as the number of words in L of length k. We say that a language L grows exactly as the sequence C_{L}(k) grows, be it exponentially, polynomially, etc. Since the work of Brandenburg [2], the study of the growth of languages has been a central theme in combinatorics on words. Given a language L, a key question is whether it grows exponentially (fast), or subexponentially (slow). Brandenburg [2] demonstrated that both the language of cube-free words over a binary alphabet, and the language of square-free words over a ternary alphabet, grow exponentially. On the other hand, Restivo and Salemi [19] demonstrated that the language of overlap-free binary words grows only polynomially.

Squares, cubes, and overlaps are all examples of repetitions in words, and can be considered in the same general framework. Let w = w_{1}w_{2} ⋯ w_{k} be a finite word, where the w_{i}’s are letters. A positive integer p is a period of w if w_{i+p} = w_{i} for all 1 ≤ i ≤ k − p. In this case, we say that |w|/p is an exponent of w, and the largest such number is called the exponent of w. For a real number r > 1, a finite or infinite word w is called r-free (r^{+}-free) if w contains no finite factors of exponent greater than or equal to r (strictly greater than r, respectively).

Throughout, for every positive integer n, let A_{n} denote the n-letter alphabet {1, 2, …, n}. For every n ≥ 2, the repetition threshold for n letters, denoted RT(n), is defined by

RT(n) = inf{r > 1: there is an infinite r^{+}-free word over A_{n}}.

Essentially, the repetition threshold describes the border between avoidable and unavoidable repetitions in words over an alphabet of n letters. The repetition threshold was first defined by Dejean [7]. Her 1972 conjecture on the values of RT(n) has now been confirmed through the work of many authors [3–7,14,15,17,18]:

RT(n) = \begin{cases}2, & if n = 2; \\ 7/4, & if n = 3; \\ 7/5, & if n = 4; \\ n/(n − 1), & if n ≥ 5. \end{cases}

The last cases of Dejean’s conjecture were confirmed in 2011 by the first and third authors [6], and independently by Rao [18]. However, probably the most important contribution was made by Carpi [3], who confirmed the conjecture in all but finitely many cases.

In this short note, we are concerned with the growth rate of the language of threshold words over A_{n}. For every n ≥ 2, let T_{n} denote the language of all RT(n)^{+}-free words over A_{n}. We call T_{n} the threshold language of order n, and we call its members threshold words of order n. Threshold words are also called Dejean words by some authors. For every n ≥ 2, the threshold language T_{n} is the minimally repetitive infinite language over A_{n}.

The threshold language T_{2} is exactly the language of overlap-free words over A_{2}, which is known to grow only polynomially [19].^{3}^{,}^{4} However, Ochem made the following conjecture about the growth of threshold languages of all other orders.

Conjecture 1 (Ochem [16]). For every n ≥ 3, the language T_{n} of threshold words of order n grows exponentially.

Conjecture 1 has been confirmed for n ∈ {3, 4} by Ochem [16], for n ∈ {5, 6, …, 10} by Kolpakov and Rao [12], and for all odd n less than or equal to 101 by Tunev and Shur [23]. In this note, we confirm Conjecture 1 for every n ≥ 27.

Theorem 2. For every n ≥ 27, the language T_{n} of threshold words of order n grows exponentially.

The layout of the remainder of the note is as follows. In Section 2, we summarize the work of Carpi [3] in confirming all but finitely many cases of Dejean’s conjecture. In Section 3, we establish Theorem 2 with constructions that rely heavily on the work of Carpi. We conclude with a discussion of problems related to the rate of growth of threshold languages.

2 Carpi’s reduction to ψ_{n}-kernel repetitions

In this section, let n ≥ 2 be a fixed integer. Pansiot [17] was first to observe that if a word over the alphabet A_{n} is (n − 1)/(n − 2)-free, then it can be encoded by a word over the binary alphabet B = {0, 1}. For consistency, we use the notation of Carpi [3] to describe this encoding. Let 𝕊_{n} denote the symmetric group on A_{n}, and define the morphism φ_{n} : B^{∗} → 𝕊_{n} by

φ_{n}(0) = (1  2 ⋯ n-1); and
φ_{n}(1) = (1  2 ⋯ n) .

Now define the map γ_{n} : B^{∗} → A_{n}^{∗} by

γ_{n}(b_{1}b_{2} ⋯ b_{k}) = a_{1}a_{2} ⋯ a_{k},

where

a_{i}φ_{n}(b_{1}b_{2} ⋯ b_{i}) = 1

for all 1 ≤ i ≤ k. To be precise, Pansiot proved that if a word α ∈ A_{n}^{∗} is (n − 1)/(n − 2)-free, then α can be obtained from a word of the form γ_{n}(u), where u ∈ B^{∗}, by renaming the letters.

3Currently the best known bounds on C_{T_{2}}(k) are due to Jungers et al. [9].

4The threshold between polynomial and exponential growth for repetition-free binary words is known to be 7/3 [10]. That is, the language of 7/3-free words over A_{2} grows polynomially, while the language of 7/3^{+}-free words over A_{2} grows exponentially.

Let u ∈ B^{∗}, and let α = γ_{n}(u). Pansiot showed that if α has a factor of exponent greater than n/(n−1), then either the word α itself contains a short repetition, or the binary word u contains a kernel repetition (see [17] for details). Carpi reformulated this statement so that both types of forbidden factors appear in the binary word u. Let k ∈ {1, 2, …, n−1}, and let v ∈ B^{+}. Then v is called a k-stabilizing word (of order n) if φ_{n}(v) fixes the points 1, 2, …, k. Let Stab_{n}(k) denote the set of k-stabilizing words of order n. The word v is called a kernel repetition (of order n) if it has period p and a factor v′ of length p such that v′ ∈ ker(φ_{n}) and |v| > \frac{np}{n−1} − (n − 1). Carpi’s reformulation of Pansiot’s result is the following.

Proposition 3 (Carpi [3, Proposition 3.2]). Let u ∈ B^{∗}. If a factor of γ_{n}(u) has exponent larger than n/(n − 1), then u has a factor v satisfying one of the following conditions:

(i) v ∈ Stab_{n}(k) and 0 < |v| < k(n − 1) for some 1 ≤ k ≤ n − 1; or

(ii) v is a kernel repetition of order n.

Now assume that n ≥ 9, and define m = ⌊(n − 3)/6⌋ and ℓ = ⌊n/2⌋. Carpi [3] defines an (n − 1)(ℓ + 1)-uniform morphism f_{n} : A_{m}^{∗} → B^{∗} with the following extraordinary property.

Proposition 4 (Carpi [3, Proposition 7.3]). Suppose that n ≥ 27, and let w ∈ A_{m}^{∗}. Then for every k ∈ {1, 2, …, n − 1}, the word f_{n}(w) contains no k-stabilizing word of length smaller than k(n − 1).

We note that Proposition 4 was proven by Carpi [3] in the case that n ≥ 30 in a computation-free manner. The improvement to n ≥ 27 stated here was achieved later by the first and third authors [4], using lemmas of Carpi [3] along with a significant computer check.

Proposition 4 says that for every word w ∈ A_{m}^{∗}, no factor of f_{n}(w) satisfies condition (i) of Proposition 3. Thus, we need only worry about factors satisfying condition (ii) of Proposition 3, i.e., kernel repetitions. To this end, define the morphism ψ_{n} : A_{m}^{∗} → 𝕊_{n} by ψ_{n}(v) = φ_{n}(f_{n}(v)) for all v ∈ A_{m}^{∗}. A word v ∈ A_{m}^{∗} is called a ψ_{n}-kernel repetition if it has a period q and a factor v′ of length q such that v′ ∈ ker(ψ_{n}) and (n − 1)(|v| + 1) ≥ nq − 3. Carpi established the following result.

Proposition 5 (Carpi [3, Proposition 8.2]). Let w ∈ A_{m}^{∗}. If a factor of f_{n}(w) is a kernel repetition, then a factor of w is a ψ_{n}-kernel repetition.

In other words, if w ∈ A_{m}^{∗} contains no ψ_{n}-kernel repetitions, then no factor of f_{n}(w) satisfies condition (ii) of Proposition 3. Altogether, we have the following theorem, which we state formally for ease of reference.

Theorem 6. Suppose that n ≥ 27. If w ∈ A_{m}^{∗} contains no ψ_{n}-kernel repetitions, then γ_{n}(f_{n}(w)) is RT(n)^{+}-free.

Finally, we note that the morphism f_{n} is defined in such a way that the kernel of ψ_{n} has a very simple structure.

Lemma 7 (Carpi [3, Lemma 9.1]). If v ∈ A_{m}^{∗}, then v ∈ ker(ψ_{n}) if and only if 4 divides |v|_{a} for every letter a ∈ A_{m}.

3 Constructing exponentially many threshold words

In this section, let n ≥ 27 be a fixed integer, and let m = ⌊(n − 3)/6⌋ and ℓ = ⌊n/2⌋, as in the previous section. Since n ≥ 27, we have m ≥ 4. In order to prove that the threshold language T_{n} grows exponentially, we construct an exponentially growing language Z_{m} ⊆ A_{m}^{∗} of words that contain no ψ_{n}-kernel repetitions. If n ≥ 33 (or equivalently, if m ≥ 5), then we define Z_{m} by modifying Carpi’s construction of an infinite word α over A_{m} that contains no ψ_{n}-kernel repetitions. If 27 ≤ n ≤ 32 (or equivalently, if m = 4), then we define a 3-uniform substitution g: A_{4}^{∗} → 2^{A_{4}^{∗}}, and let Z_{4} be the set of all factors of words obtained by iterating g on the letter 1.

3.1 Case I: n ≥ 33

We first recall the definition of α, the infinite word over A_{m} defined by Carpi [3] that contains no ψ_{n}-kernel repetitions. First of all, define β = (b_{i})_{i≥1}, where

b_{i} = \begin{cases}1, & if i ≡ 1 (mod 3); \\ 2, & if i ≡ 2 (mod 3); \\ b_{i/3}, & if i ≡ 0 (mod 3). \end{cases}

Now define α = (a_{i})_{i≥1}, where for all i ≥ 1, we have

a_{i} = \begin{cases}max\{a ∈ A_{m}: 4^{a−2} divides i\}, & if i is even; \\ b_{(i+1)/2}, & if i is odd. \end{cases}

Note that if i ≡ 2 (mod 4), then a_{i} = 2. Let Z_{m} be the set of all finite words obtained from a prefix of α by exchanging any subset of these 2’s for 1’s. To be precise, if z = z_{1}z_{2} ⋯ z_{k}, then z ∈ Z_{m} if and only if all of the following hold:

• z_{i} ∈ {1, 2} if i ≡ 2 (mod 4);

• z_{i} = max {a ∈ A_{m}: 4^{a−2} divides i} if i ≡ 0 (mod 4); and

• z_{i} = b_{(i+1)/2} if i is odd.

Note in particular that if z = z_{1}z_{2} ⋯ z_{k} is in Z_{m}, then z_{i} ≥ 3 if and only if i ≡ 0 (mod 4).

We claim that no word z ∈ Z_{m} contains a ψ_{n}-kernel repetition. The proof is essentially analogous to Carpi’s proof that α contains no ψ_{n}-kernel repetitions. We begin with a lemma about the lengths of factors of words in Z_{m} that lie in ker(ψ_{n}).

Lemma 8 (Adapted from Carpi [3, Lemma 9.3]). Let z ∈ Z_{m}, and let v be a factor of z. If v ∈ ker(ψ_{n}), then 4^{m−1} divides |v|.

Proof. The statement is trivially true if v = ε, so assume |v| > 0. Set |v| = 4^{b}c, where 4^{b} is the maximal power of 4 dividing |v|. Suppose, towards a contradiction, that b ≤ m − 2. Since v ∈ ker(ψ_{n}), by Lemma 7, we see that 4 divides |v|, meaning b ≥ 1.

Write z = z_{1}z_{2} ⋯ z_{|z|}. Then we have v = z_{i}z_{i+1} ⋯ z_{i+4^{b}c−1} for some i ≥ 1. By definition, for any j ≥ 1, we have z_{j} ≥ b + 2 if and only if 4^{b} divides j. (Since b ≥ 1, we have b + 2 ≥ 3, and hence z_{j} ≥ b + 2 implies j ≡ 0 (mod 4).) Thus, we have that the sum ∑_{a=b+2}^{m} |v|_{a} is exactly the number of integers in the set {i, i+1, …, i+4^{b}c−1} that are divisible by 4^{b}, which is exactly c. Since v ∈ ker(ψ_{n}), by Lemma 7, we conclude that 4 divides c, contradicting the maximality of b.

Now, using Lemma 8 in place of [3, Lemma 9.3], a proof strictly analogous to that of [3, Proposition 9.4] gives the following. The only tool in the proof that we have not covered here is [3, Lemma 9.2], which is a short technical lemma about the repetitions in the word β, and which can be used without any modification.

Proposition 9. Suppose that n ≥ 33. Then no word z ∈ Z_{m} contains a ψ_{n}-kernel repetition.

3.2 Case II: 27 ≤ n ≤ 32

In this case, we have m = 4. For any set X, we let 2^{X} denote the power set of X. So in particular, the set 2^{A_{4}^{∗}} consists of all sets of finite words over A_{4}. For alphabets Σ and Δ, a substitution is a map s : Σ^{∗} → 2^{Δ^{∗}} such that s(xy) = s(x)s(y) for all x, y ∈ Σ^{∗} and s(ε) = {ε}.

Define a substitution g : A_{4}^{∗} → 2^{A_{4}^{∗}} by

g(1) = {112}
g(2) = {114}
g(3) = {113}
g(4) = {123, 213}.

We extend g to 2^{A_{4}^{∗}} by g(W) = ⋃_{w∈W} g(w), which allows us to iteratively apply g to an initial word in A_{4}^{∗}. Let Z_{4} = Fact{v: v ∈ g^{n}(1) for some n ≥ 1}, i.e., we have that Z_{4} is the set of factors of all words obtained by iteratively applying g to the initial word 1.

For a word w ∈ A_{4}^{∗}, let π(w) denote the Parikh vector of w, defined by

π(w) = [|w|_{1} |w|_{2} |w|_{3} |w|_{4}]^{T}

Note that for every a ∈ A_{4} and every x, y ∈ g(a), we have π(x) = π(y). Thus, we may let π_{g}(a) denote the common Parikh vector of every word in g(a). The frequency matrix M_{g} of g is then the 4 × 4 matrix defined by

(M_{g})_{ij} = (π_{g}(j))_{i}

i.e., the jth column of M_{g} is the Parikh vector of every word in g(j). Explicitly, we have

M_{g} = [\begin{matrix}2 & 2 & 2 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \end{matrix}] .

Evidently, if v ∈ g(u), then we have π(v) = M_{g}π(u). Note also that M_{g} is invertible modulo 4, with

M_{g}^{−1} = [\begin{matrix}3 & 3 & 2 & 2 \\ 0 & 0 & 0 & 1 \\ 3 & 2 & 3 & 2 \\ 1 & 2 & 2 & 2 \end{matrix}] .

This fact is the key to the proof of the following lemma.

Lemma 10. Let u ∈ A_{4}^{∗} be a word, and let v ∈ g(u). If v ∈ ker(ψ_{n}), then u ∈ ker(ψ_{n}).

Proof. By Lemma 7, for every word w ∈ A_{4}^{∗}, we have w ∈ ker(ψ_{n}) if and only if π(w) ≡ 0 (mod 4).

Now suppose that v ∈ ker(ψ_{n}). Then π(v) ≡ 0 (mod 4). Since v ∈ g(u), we have π(v) = M_{g}π(u). It follows that π(u) ≡ M_{g}^{−1}π(v) ≡ 0 (mod 4) as well, and thus we have u ∈ ker(ψ_{n}).

If a word w ∈ A_{4}^{∗} has period p and the length p prefix of w is in ker(ψ_{n}), then we say that p is a kernel period of w.

Proposition 11. Suppose that 27 ≤ n ≤ 32. Then no word in Z_{4} contains a ψ_{n}-kernel repetition.

Proof. Suppose otherwise that the word v_{0} ∈ Z_{4} is a ψ_{n}-kernel repetition. Write v_{0} = x_{0}y_{0}, where v_{0} has kernel period |x_{0}|. From the definition of ψ_{n}-kernel repetition, we must have

(n − 1)(|v_{0}| + 1) ≥ n|x_{0}| − 3,

or equivalently,

|x_{0}| ≤ (n − 1)|y_{0}| + n + 2.

Since n ≤ 32, we certainly have

|x_{0}| ≤ 31|y_{0}| + 34.  (1)

If |y_{0}| ≤ 3, then we have |x_{0}| ≤ 127, and hence |v_{0}| ≤ 130. We eliminate this possibility by exhaustive search, so we may assume that |y_{0}| ≥ 4.

Let z be the length 3 prefix of y_{0}. By inspection of all words in Z_{4} of length 3, there is a unique factorization z = z′z′′, where z′ is a nonempty suffix of some word in g(A_{4}), and z′′ is a (possibly empty) prefix of some word in g(A_{4}). Since y_{0} is a prefix of x_{0}y_{0}, it must be the case that z is a prefix of x_{0}. Write x_{0}z = z′z′′x′_{0}z′z′′. Then we must have z′′x′_{0}z′ ∈ g(A_{4}^{∗}), and hence |x_{0}| = |z′′x′_{0}z′| is a multiple of 3.

Now write v_{0} = s_{0}v′_{0}p_{0} for some suffix s_{0} of a word in g(A_{4}), some prefix p_{0} of a word in g(A_{4}), and some word v′_{0} ∈ g(v_{1}), where v_{1} ∈ Z_{4}. Since |s_{0}| ≤ 2 and |p_{0}| ≤ 2, we have |v′_{0}| ≥ |v_{0}| − 4 ≥ |x_{0}|, and hence v′_{0} has kernel period |x_{0}|. Now write v_{1} = x_{1}y_{1}, where 3|x_{1}| = |x_{0}|. Evidently, we have 3|y_{1}| + 4 ≥ |y_{0}|. Note that v_{1} has period |x_{1}|. Further, by Lemma 10, we have x_{1} ∈ ker(ψ_{n}), and hence |x_{1}| is a kernel period of v_{1}.

We may now repeat the process described above. Eventually, for some r ≥ 1, we reach a word v_{r} ∈ Z_{4} that can be written v_{r} = x_{r}y_{r}, where |x_{r}| is a kernel period of v_{r}, and |y_{r}| ≤ 3. For all 1 ≤ i ≤ r, one proves by induction that |x_{0}| = 3^{i}|x_{i}| and |y_{0}| ≤ 3^{i}|y_{i}| + 4 ∑_{j=0}^{i−1} 3^{j} = 3^{i}|y_{i}| + 2(3^{i} − 1). Thus, from (1), we obtain

3^{i}|x_{i}| ≤ 31 [3^{i}|y_{i}| + 2(3^{i} − 1)] + 34

for all 1 ≤ i ≤ r. Dividing through by 3^{i}, and then simplifying, we obtain

|x_{i}| ≤ 31 [|y_{i}| + 2] − \frac{28}{3^{i}} ≤ 31 [|y_{i}| + 2]  (2)

for all 1 ≤ i ≤ r.

Since |y_{r}| ≤ 3, we obtain |x_{r}| ≤ 155 from (2). By Lemma 7, the kernel period |x_{r}| of v_{r} is a multiple of 4, so in fact we have |x_{r}| ≤ 152, and in turn |v_{r}| ≤ 155. By exhaustive search of all words in Z_{4} of length at most 155, we find that v_{r} ∈ W, where W is a set containing exactly 200 words. Indeed, the set W contains

• 160 words with kernel period 76 and length 77,

• 36 words with kernel period 92 and length 93, and

• 4 words with kernel period 112 and length 114.

For every w ∈ W, let

E_{w} = Fact ({g(awb): a, b ∈ A_{4}, awb ∈ Z_{4}}) .

Evidently, we have v_{r−1} ∈ E_{v_{r}}. For every word w ∈ W, let p_{w} denote the kernel period of w, and let q_{w} denote the maximum length of a repetition with kernel period 3p_{w} across all words in E_{w}. By exhaustive check, for every w ∈ W, we find 3p_{w} > 31 [q_{w} − 3p_{w} + 2]. However, the word v_{r−1} = x_{r−1}y_{r−1} must be in E_{v_{r}}, and by (2), we have

3p_{v_{r}} = |x_{r−1}| ≤ 31 [|y_{r−1}| + 2] ≤ 31 [q_{v_{r}} − 3p_{v_{r}} + 2] .

This is a contradiction. We conclude that the set Z_{4} contains no ψ_{n}-kernel repetitions.

We now proceed with the proof of our main result.

Proof of Theorem 2. First suppose that n ≥ 33. By Proposition 9, no word z ∈ Z_{m} contains a ψ_{n}-kernel repetition. From the definition of Z_{m}, one easily proves that

C_{Z_{m}}(k) = Ω (2^{k/4}) .

By Theorem 6, for every word z ∈ Z_{m}, the word γ_{n}(f_{n}(z)) is in the threshold language T_{n} of order n. Moreover, the maps γ_{n} and f_{n} are injective, and |γ_{n}(f_{n}(z))|/|z| = (n − 1)(ℓ + 1), since f_{n} is (n − 1)(ℓ + 1)-uniform and γ_{n} preserves length. It follows that

C_{T_{n}}(k) = Ω (2^{k/4(n−1)(ℓ+1)}) .

Since n, and hence ℓ, are fixed, the quantity (n − 1)(ℓ + 1) is a constant, and we conclude that the language T_{n} grows exponentially.

Suppose now that 27 ≤ n ≤ 32. By Proposition 11, no word z ∈ Z_{4} contains a ψ_{n}-kernel repetition. Since |g^{4}(a)| ≥ 4 for all a ∈ A_{4}, we have

C_{Z_{4}}(k) = Ω (4^{k/81}) .

By the same argument as above, we see that

C_{T_{n}}(k) = Ω (4^{k/81(n−1)(ℓ+1)}) ,

and we conclude that the language T_{n} grows exponentially.

As pointed out by one of the anonymous referees, the constructions given in this section can also be used to demonstrate the existence of uncountably many infinite threshold words over A_{n} for every n ≥ 27.

4 Conclusion

Conjecture 1 has now been established for all n ∉ {12, 14, …, 26}. We remark that different techniques than those presented here will be needed to establish Conjecture 1 in all but one of these remaining cases. (It appears that the techniques presented here could potentially be used for n = 22, but we do not pursue this isolated case.) For example, let n = 26. Then we have m = 3. By computer search, for every letter a ∈ A_{m}, the word f_{n}(a3) contains a 15-stabilizing word of length 350, which is less than 15(n − 1) = 375. By another computer search, the longest word on {1, 2} avoiding ψ_{n}-kernel repetitions has length 15. So there are only finitely many words in A_{m}^{∗} that avoid both ψ_{n}-kernel repetitions and the forbidden stabilizing words. Similar arguments lead to the same conclusion for all n ∈ {12, 14, 16, 18, 20, 24}.

For a language L, the value ρ(L) = lim sup_{k→∞}(C_{L}(k))^{1/k} is called the growth rate of L. If L is factorial (i.e., closed under taking factors), then by an application of Fekete’s lemma, we can safely replace lim sup by lim in this definition. If ρ(L) > 1, then the language L grows exponentially, and in this case, ρ(L) is a good description of how quickly the language grows.

For all n ≥ 33, we have established that ρ(T_{n}) ≥ 2^{1/4(n−1)(ℓ+1)}. However, this lower bound tends to 1 as n tends to infinity, and this seems far from best possible. Indeed, Shur and Gorbunova proposed the following conjecture concerning the asymptotic behaviour of ρ(T_{n}).

Conjecture 12 (Shur and Gorbunova [22]). The sequence {ρ(T_{n})} of the growth rates of threshold languages converges to a limit ρ̂ ≈ 1.242 as n tends to infinity.

A wide variety of evidence supports this conjecture – we refer the reader to [8,20–22] for details. For a fixed n, there are efficient methods for determining upper bounds on ρ(T_{n}) which appear to be rather sharp, even for relatively large values of n (see [22], for example). Establishing a sharp lower bound on ρ(T_{n}) appears to be a more difficult problem. We note that a good lower bound on ρ(T_{3}) is given by Kolpakov [11] using a method that requires some significant computation. For all n ∈ {5, 6, …, 10}, Kolpakov and Rao [12] give lower bounds for ρ(T_{n}) using a similar method. They were then able to estimate the value of ρ(T_{n}) with precision 0.005 using upper bounds obtained by the method of Shur and Gorbunova [22].

Thus, in addition to resolving the finitely many remaining cases of Conjecture 1, improving our lower bound for ρ(T_{n}) when n ≥ 27 remains a significant open problem.

5 Acknowledgments

We thank the anonymous referees, whose comments and suggestions helped to improve the paper.

References

[1] J. Berstel, Axel Thue’s papers on repetitions in words: a translation, in Publications du LaCIM, Vol. 20, Université du Québec à Montréal, 1995.

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

[3] A. Carpi, On Dejean’s conjecture over large alphabets, Theoret. Comput. Sci. 385 (2007), 137–151.

[4] J. D. Currie and N. Rampersad, Dejean’s conjecture holds for n ≥ 27, RAIRO—Theor. Inform. Appl. 43 (2009), 775–778.

[5] J. D. Currie and N. Rampersad, Dejean’s conjecture holds for n ≥ 30, Theoret. Comput. Sci. 410 (2009), 2885–2888.

[6] J. D. Currie and N. Rampersad, A proof of Dejean’s conjecture, Math. Comp. 80 (2011), 1063–1070.

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

[8] I. A. Gorbunova and A. M. Shur, On Pansiot words avoiding 3-repetitions, in Proc. 8th Internat. Conf. Words 2011 (WORDS 2011), Electron. Proc. Theor. Comput. Sci., Vol. 63, 2012, pp. 138–146.

[9] R. M. Jungers, V. Y. Protasov, and V. D. Blondel, Overlap-free words and spectra of matrices, Theoret. Comput. Sci. 410 (2009), 3670–3684.

[10] J. Karhumäki and J. Shallit, Polynomial versus exponential growth in repetition-free binary words, J. Combin. Theory Ser. A 105 (2004), 335–347.

[11] R. Kolpakov, Efficient lower bounds on the number of repetition-free words, J. Integer Sequences 10 (2007), 1–16.

[12] R. Kolpakov and M. Rao, On the number of Dejean words over alphabets of 5, 6, 7, 8, 9 and 10 letters, Theoret. Comput. Sci. 412 (2011), 6507–6516.

[13] M Lothaire, Algebraic Combinatorics on Words, Cambridge University Press, 2002.

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

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

[16] P. Ochem, A generator of morphisms for infinite words, RAIRO—Theor. Inform. Appl. 40 (2006), 427–441.

[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] M. Rao, Last cases of Dejean’s conjecture, Theoret. Comput. Sci. 412 (2011), 3010– 3018.

[19] A. Restivo and S. Salemi, Overlap free words on two symbols, in M. Nivat and D. Perrin, eds., Automata on Infinite Words, Lect. Notes in Comput. Sci., Vol. 192, Springer-Verlag, 1985, pp. 198–206.

[20] A. M. Shur, Growth properties of power-free languages, Comput. Sci. Rev. 6 (2012), 187–208.

[21] A. M. Shur, Growth of power-free languages over large alphabets, Theory Comput. Syst. 54 (2014), 224–243.

[22] A. M. Shur and I. A. Gorbunova, On the growth rates of complexity of threshold languages, RAIRO—Theor. Inform. Appl. 44 (2010), 175–192.

[23] I. N. Tunev and A. M. Shur, On two stronger versions of Dejean’s conjecture, in Proc. 37th Internat. Conf. on Mathematical Foundations of Computer Science (MFCS 2012), Lect. Notes in Comput. Sci., Vol. 7464, Springer, 2012, pp. 800–812.

2010 Mathematics Subject Classification: Primary 68R15. Keywords: threshold word, repetition threshold, Dejean word, exponential growth, Dejean’s conjecture, Dejean’s theorem.

Received November 13 2019; revised version received February 21 2020. Published in Journal of Integer Sequences, February 22 2020.

Return to Journal of Integer Sequences home page.