On Highly Repetitive and Power Free Words

Narad Rampersad Department of Mathematics and Statistics University of Winnipeg Canada

                   narad.rampersad@gmail.com

Elise Vaslet Department of Mathematics University of Turku Finland

Abstract

Answering a question of Richomme, Currie and Rampersad proved that 7/3 is the infimum of the real numbers α > 2 such that there exists an infinite binary word that avoids α-powers but is highly 2-repetitive, i.e., contains arbitrarily large squares beginning at every position. In this paper, we prove similar statements about βrepetitive words, for some other β’s, over the binary and the ternary alphabets.

1 Introduction

In this paper we study words that are non-repetitive, in the sense that they avoid α-powers for some α, but yet are highly repetitive, in the sense that for some β close to α, they contain infinitely many β-powers starting at every position. First we recall some basic definitions. A finite, non-empty word v can be written as v = p^{k}e, where k ≥ 1, the word e is a prefix of p, and the length of p is minimal. We say that v has period p, excess e, and exponent expo(v) = |v|/|p|. A word with exponent α is called an α-power. An α^{+}-power is a word that is a β-power for some β > α. A 2-power is called a square; a 2^{+}-power is called an overlap. A word is α-free if none of its factors is a β-power for any β ≥ α. A word is α^{+}-free if none of its factors is an α^{+}-power.

Thue [TH2] proved that there exist infinite overlap-free binary words. Dekking [DEK] later showed that any infinite overlap-free binary word must contain arbitrarily large squares.

Currie, Rampersad, and Shallit [CRS] constructed 7/3-free words containing infinitely many overlaps. Their motivation came from the following result of Shur [SHU]: Any bi-infinite 7/3-free binary word is overlap-free. The analogue of this surprising result is not true for onesided infinite words: There are infinite 7/3-free binary words that are not overlap-free. The result of Currie et al. shows that in fact the infinite 7/3-free binary words can be significantly different from the infinite overlap-free binary words.

Currie and Rampersad [CR] continued this line of study in order to respond to the following question of Richomme [RIC]: What is the infimum of the real numbers α > 2 such that there exists an infinite word that avoids α-powers but contains arbitrarily large squares beginning at every position? They showed that over the binary alphabet the answer to Richomme’s question is α = 7/3. In this paper we show that if instead of requiring arbitrarily large squares at every position, we only ask for arbitrarily large β-powers at every position for some fixed β < 2, then the answer of 7/3 for Richomme’s question can be replaced by 2. We also answer the analogous question for the ternary alphabet.

Specifically, we first define a highly α-repetitive word to be a word that contains infinitely many α-repetitions beginning at every position. Our main results are:

1. On the binary alphabet, for any real number β < 2, there exists a 2^{+}-free word that is highly β-repetitive.

2. On the ternary alphabet, for any real number β < 7/4, there exists a 7/4^{+}-free word that is highly β-repetitive.

We also mention here the related work of Saari [SAA], who also studied infinite words containing squares (not necessarily arbitrarily large) beginning at every position. He called such words squareful, but he imposed the additional condition that the word contain only finitely many distinct minimal squares.

2 Preliminary definitions and results

Let α be a real number.

Definition 1. A finite word is an α-repetition (resp. α^{+}-repetition) if it is a β-power for some β ≥ α (resp. β > α).

Definition 2. A word (finite or infinite) is highly α-repetitive (resp. highly α^{+}-repetitive) if it contains infinitely many α-repetitions (resp. α^{+}-repetitions) beginning at every position.

Definition 3. A word (finite or infinite) is α-free (resp. α^{+}-free) if it contains no α-repetition (resp. α^{+}-repetition).

Definition 4. A morphism μ : A^{∗} → B^{∗} is α-free (resp. α^{+}-free) if for any word w ∈ A^{∗}, the following equivalence holds:

w is α-free (resp. α^{+}-free) ⇔ μ(w) is α-free (resp. α^{+}-free).

Definition 5. The critical exponent E_{c}(w) of an infinite word w is the supremum of all rational numbers r such that w contains an r-power.

We now define some particular morphisms which we will use in the paper because of their α-freeness for certain α.

The Thue-Morse morphism is defined by

μ_{T M} : \begin{cases}0 ↦ 01 \\ 1 ↦ 10. \end{cases}

Proposition 6 ([TH2]). μ_{T M} is a 2^{+}-free morphism.

Dejean’s morphism is defined by

μ_{D} : \begin{cases}a ↦ abc acb cab c bac bca cba \\ b ↦ π(μ_{D}(a)) = bca bac abc a cba cab acb \\ c ↦ π^{2}(μ_{D}(a)) = cab cba bca b acb abc bac, \end{cases}

where π is the morphism that cyclically permutes the alphabet {a, b, c}. Proposition 7 ([DEJ]). μ_{D} is a 7/4^{+}-free morphism.

The following morphism was given by Brandenburg in [BRA]:

μ_{B} : \begin{cases}a ↦ abacbabcbac \\ b ↦ abacbcacbac \\ c ↦ abcbabcacbc. \end{cases}

Proposition 8 ([BRA]). μ_{B} is a 2-free morphism.

Finally, for any integers s, t such that 0 < s ≤ t, let us define the binary (t + 1)-uniform morphism ϕ_{s,t} by

ϕ_{s,t} : \begin{cases}0 & ↦ 01^{t} \\ 1 & ↦ 01^{s−1}0^{t−s+1}. \end{cases}

Moreover, we define the rational numbers

q_{s,t} = \begin{cases}t + \frac{s}{t}, & if s > 1; \\ t(t + 1) + 1 + \frac{1}{t}, & if s = 1. \end{cases}

These morphisms were introduced by Krieger, who proved that: Proposition 9 ([KRI]). The fixed point ϕ_{s,t}^{ω}(0) of ϕ_{s,t} has critical exponent

E_{c}(ϕ_{s,t}^{ω}(0)) = q_{s,t}.

In particular, the following remark will be useful: Remark 10. For any factor v of the fixed point ϕ_{s,t}^{ω}(0), the word ϕ_{s,t}(v) is q_{s,t}^{+}-free.

3 Highly repetitive binary words

The results of Currie and Rampersad [CR, Theorems 4 and 5] state that for any α > 7/3, there exists an infinite binary word which is both α-free and highly 2-repetitive, and that such a word does not exist if α ≤ 7/3. The following proposition gives a similar result in the case of highly β-repetitive words, with β < 2: for any α > 2 and any β < 2, there exists an infinite binary word which is both α-free and highly β-repetitive.

Theorem 11. For any real number β < 2, there exists an infinite binary word which is both 2^{+}-free and highly β-repetitive.

Proof. Let β < 2 be a real number. There exists an integer m ≥ 1 such that β ≤ 2− \frac{1}{2^{m}} < 2. Let r = 2 − \frac{1}{2^{m}}, and let us construct a binary infinite word with infinitely many r-powers at every position, and which is 2^{+}-free. We recall that μ_{T M} is the Thue-Morse morphism.

We remark that μ_{T M}^{m}(11) is a factor of μ_{T M}^{m+3}(1). Indeed, μ_{T M}^{3}(1) = 10010110, and so μ_{T M}^{m+3}(1) = μ_{T M}^{m}(10010110) = uμ_{T M}^{m}(11)μ_{T M}^{m}(0), where u = μ_{T M}^{m}(10010). Let us define q = m + 3. We define the following sequence of finite words:

A_{0} = μ_{T M}^{m}(11)
A_{1} = (u)^{−1}μ_{T M}^{q}(A_{0})
⋮
A_{n} = (u)^{−1}μ_{T M}^{q}(A_{n−1}),

where we denote by (x)^{−1}y the word obtained by removing the prefix x from the word y (here, the word μ_{T M}^{q}(A_{n}) always has u as a prefix, since A_{n} always has 1 as a prefix). As 11 and μ_{T M} are 2^{+}-free, then for any n ≥ 0, A_{n} is 2^{+}-free.

We show that for any n ≥ 0, A_{n} is a prefix of A_{n+1}. This is clearly true for n = 0. If A_{n−1} is a prefix of A_{n}, then we can write A_{n} = A_{n−1}S, where S is a binary word. Then, A_{n+1} = (u)^{−1}μ_{T M}^{q}(A_{n−1}S) = A_{n}μ_{T M}^{q}(S). Thus, the sequence A_{n} converges to an infinite limit word we denote by w, and this limit is 2^{+}-free. We now prove that w contains infinitely many r-powers beginning at every position. It can easily be seen that for any n ≥ 1,

A_{n} = (u)^{−1}[μ_{T M}^{q}(u)]^{−1} ⋯ [μ_{T M}^{q(n−1)}(u)]^{−1}μ_{T M}^{qn}(A_{0}).

(Here the sequence of deletions indicated by the terms appearing with exponent −1 should be understood as being applied from right to left.) Let us denote by p_{n} the word

μ_{T M}^{q(n−1)}(u) ⋯ μ_{T M}^{q}(u)u.

Then we have A_{n} = (p_{n})^{−1}μ_{T M}^{qn}(A_{0}), since for any words u and v, (uv)^{−1} = (v)^{−1}(u)^{−1}. Moreover, we can see that p_{n} is a prefix of μ_{T M}^{qn}(1). Indeed,

|p_{n}| = |u| ∑_{i=0}^{n−1} |μ_{T M}(1)|^{qi}

= |u| ∑_{i=0}^{n−1} 2^{qi}
< 2^{qn} = |μ_{T M}^{qn}(1)|,

since |u| ≤ 2^{q} − 1. So, we can write μ_{T M}^{qn}(1) = p_{n}s_{n}, where s_{n} is a binary word. For any n ≥ 1, A_{n} = (p_{n})^{−1}μ_{T M}^{qn}(A_{0}) = (p_{n})^{−1}μ_{T M}^{qn}(μ_{T M}^{m}(11)). We know that μ_{T M}^{m}(1) begins with the letter 1, and let us denote its last letter by a ∈ {0, 1}. We can write μ_{T M}^{m}(1) = 1xa, where x ∈ {0, 1}^{∗}. We can also write μ_{T M}^{qn}(a) = p̃_{n}s̃_{n}, with p̃_{n} and s̃_{n} two binary words such that |p̃_{n}| = |p_{n}| and |s̃_{n}| = |s_{n}|. Then,

A_{n} = s_{n}μ_{T M}^{qn}(x)p̃_{n}s̃_{n}p_{n}s_{n}μ_{T M}^{qn}(x)p̃_{n}s̃_{n}.

It follows that at all positions 0 ≤ j ≤ |s_{n}|, there begins a repetition with period a conjugate of s_{n}μ_{T M}^{qn}(x)p̃_{n}s̃_{n}p_{n}, and of length

|s_{n}μ_{T M}^{qn}(x)p̃_{n}s̃_{n}p_{n}s_{n}μ_{T M}^{qn}(x)p̃_{n}|
= 2 · |x| · 2^{qn} + 3 · 2^{qn}
= 2^{qn}(2^{m+1} − 1),

since |x| = |μ_{T M}^{m}(1)|−2 = 2^{m}−2. These repetitions have exponents \frac{2^{qn}(2^{m+1}−1)}{2^{qn}|x|+2·2^{qn}} = \frac{2^{m+1}−1}{2^{m}} = r. As n can be taken arbitrarily large, the result follows.

Moreover, this result is optimal. Indeed, on the one hand, it is easy to see that for α ≤ 2, there is no infinite binary α-free word. On the other hand, Currie and Rampersad proved the following result.

Proposition 12 ([CR]). If w is an infinite 2^{+}-free binary word, then there is a position i such that w does not contain a square beginning at position i.

Our next result uses the morphisms ϕ_{s,t} defined in Section 2. We will first establish a few technical lemmas, which will be used to prove Proposition 16.

For any integers s, t and any integer N, we define

u_{s,t,N} = \begin{cases}ϕ_{s,t}^{N−3}(0), & if s > 1; \\ ϕ_{s,t}^{N−3}(01^{t}), & if s = 1, \end{cases}

and

r_{s,t} = \begin{cases}1^{t}0, & if s > 1; \\ 0^{t(t+1)+1}1, & if s = 1. \end{cases}

Lemma 13. For any N ≥ 3, ϕ_{s,t}^{N}(0) begins with the prefix u_{s,t,N}ϕ_{s,t}^{N−3}(r_{s,t}).

Proof. We prove this result by a simple induction. Suppose first that s > 1. It is clear that 01^{t}0 is a prefix of ϕ_{s,t}^{3}(0). Then, if we assume that ϕ_{s,t}^{N}(0) = u_{s,t,N}ϕ_{s,t}^{N−3}(r_{s,t})s_{s,t,N}, where s_{s,t,N} denotes the corresponding suffix, then, we have:

ϕ_{s,t}^{N+1}(0) = ϕ_{s,t}(ϕ_{s,t}^{N−3}(01^{t}0)s_{s,t,N})
= u_{s,t,N+1}ϕ_{s,t}^{N−2}(r_{s,t})ϕ_{s,t}(s_{s,t,N}),

which concludes the calculation. The case s = 1 is proved similarly.

We denote by P_{s,t,N} the longest common prefix of ϕ_{s,t}^{N}(0) and ϕ_{s,t}^{N}(1).

Lemma 14. For any integer N ≥ 1,

P_{s,t,N} = ϕ_{s,t}^{N−1}(01^{s−1})ϕ_{s,t}^{N−2}(01^{s−1}) ⋯ ϕ_{s,t}(01^{s−1})01^{s−1}.

Proof. We prove the result by induction. We suppose first that s > 1. It is clear that the longest common prefix of ϕ_{s,t}(0) and ϕ_{s,t}(1) is 01^{s−1}, since s ≤ t. Now, assuming that P_{s,t,N} = ϕ_{s,t}^{N−1}(01^{s−1})ϕ_{s,t}^{N−2}(01^{s−1}) ⋯ ϕ_{s,t}(01^{s−1})01^{s−1}, the longest common prefix of ϕ_{s,t}^{N+1}(0) and ϕ_{s,t}^{N+1}(1) is the longest common prefix of ϕ_{s,t}(P_{s,t,N}0) and ϕ_{s,t}(P_{s,t,N}1), i.e., the longest common prefix of

ϕ_{s,t}^{N}(01^{s−1})ϕ_{s,t}^{N}(01^{s−1}) ⋯ ϕ_{s,t}(01^{s−1})ϕ_{s,t}(0)

and

ϕ_{s,t}^{N}(01^{s−1})ϕ_{s,t}^{N}(01^{s−1}) ⋯ ϕ_{s,t}(01^{s−1})ϕ_{s,t}(1).

This prefix is obviously ϕ_{s,t}^{N}(01^{s−1})ϕ_{s,t}^{N}(01^{s−1}) ⋯ ϕ_{s,t}(01^{s−1})01^{s−1}. The case s = 1 is proved with similar arguments.

Lemma 15. For any N ≥ 3, ϕ_{s,t}^{N}(0) contains the repetition

R_{s,t,N} = \begin{cases}(ϕ_{s,t}^{N−3}(1))^{t}P_{s,t,N−3}, & if s > 1; \\ (ϕ_{s,t}^{N−3}(0))^{t(t+1)+1}P_{s,t,N−3}, & if s = 1, \end{cases}

which has exponent

E(R_{s,t,N}) = \begin{cases}t + \frac{s}{t} − \frac{s}{t(t+1)^{N−3}} , & if s > 1; \\ t(t + 1) + 1 + \frac{1}{t} − \frac{1}{t(t+1)^{N−3}} , & if s = 1. \end{cases}

More precisely, ϕ_{s,t}^{N}(0) begins with the prefix u_{s,t,N}R_{s,t,N}.

Proof. The fact that ϕ_{s,t}^{N}(0) contains the repetition R_{s,t,N} is easily deduced from Lemmas 13 and 14. The exponent of this repetition is a simple calculation. Indeed, R_{s,t,N} has period ϕ_{s,t}^{N−3}(1) or ϕ_{s,t}^{N−3}(0) (depending on the value of s), and excess P_{s,t,N−3}. As we have |P_{s,t,N−3}| = \frac{s((t+1)^{N−3}−1)}{t}, and |ϕ_{s,t}^{N−3}(1)| = |ϕ_{s,t}^{N−3}(0)| = (t + 1)^{N−3}, the result follows.

Proposition 16. For any integers s, t, such that 0 < s ≤ t, and any real number β < q_{s,t}, there exists an infinite binary word w which is both q_{s,t}^{+}-free and highly β-repetitive.

Proof. Let s, t be integers such that 0 < s ≤ t, and consider the morphism ϕ_{s,t} defined previously. Let β < q_{s,t} be a real number. There exists integers N and p such that β ≤ q_{s,t} − \frac{1}{t(t+1)^{N−3}} − \frac{1}{(t+1)^{N−3+p}} < q_{s,t} − \frac{1}{t(t+1)^{N−3}} . Let r = q_{s,t} − \frac{1}{t(t+1)^{N−3}} − \frac{s}{(t+1)^{N−3+p}}, and let us construct a binary infinite q_{s,t}^{+}-free word with infinitely many r-powers at every position.

As before, we define

r_{s,t} = \begin{cases}1^{t}0, & if s > 1; \\ 0^{t(t+1)+1}1, & if s = 1. \end{cases}

We can easily deduce from Lemma 13 that ϕ_{s,t}^{p+N−3}(r_{s,t}) is a factor of ϕ_{s,t}^{p+N}(0). Indeed, by the Lemma, ϕ_{s,t}^{N}(0) = u_{s,t,N}ϕ_{s,t}^{N−3}(r_{s,t})y, with y a binary word, so

ϕ_{s,t}^{p+N}(0) = ϕ_{s,t}^{p}(u_{s,t,N})ϕ_{s,t}^{p+N−3}(r_{s,t})ϕ_{s,t}^{p}(y).

Let us denote by u the word ϕ_{s,t}^{p}(u_{s,t,N}). Let us now set q = p + N, and define the following sequence of finite binary words:

A_{0} = ϕ_{s,t}^{p+N−3}(r_{s,t})
A_{1} = (u^{−1})ϕ_{s,t}^{q}(A_{0})
⋮
A_{M} = (u^{−1})ϕ_{s,t}^{q}(A_{M−1}).

(Here, the word ϕ_{s,t}^{q}(A_{M}) always has u as a prefix, since A_{M} always has 0 as a prefix.) As r_{s,t} is q_{s,t}^{+}-free and by Remark 10, we deduce that for any M ≥ 0, A_{M} is q_{s,t}^{+}-free. We now show that for any M ≥ 0, A_{M} is a prefix of A_{M+1}. This is clearly true for M = 0, by definition of u. Then, if A_{M−1} is a prefix of A_{M}, let us write A_{M} = A_{M−1}S, where S ∈ {0, 1}^{∗}. Then, A_{M+1} = (u)^{−1}ϕ_{s,t}^{q}(A_{M−1}S) = A_{M}ϕ_{s,t}^{q}(S). Thus, the sequence of words A_{M} converges to an infinite binary limit word we denote by w, and this limit is q_{s,t}^{+}-free. Let us now prove that w contains infinitely many r-powers beginning at every position. It is easy to see that for any M ≥ 1,

A_{M} = (u)^{−1}[ϕ_{s,t}^{q}(u)]^{−1} ⋯ [ϕ_{s,t}^{q(M−1)}(u)]^{−1}ϕ_{s,t}^{qM}(A_{0}).

We define p_{M} = ϕ_{s,t}^{q(M−1)}(u) ⋯ ϕ_{s,t}^{q}(u)u, and then we have A_{M} = (p_{M})^{−1}ϕ_{s,t}^{qM}(A_{0}), since for any words x, y, (xy)^{−1} = y^{−1}x^{−1}. Moreover, p_{M} is a prefix of ϕ_{s,t}^{qM}(0). Indeed, since ϕ_{s,t} is (t + 1)-uniform,

|p_{M}| = |u| ∑_{i=0}^{M−1}(t + 1)^{qi}
< (t + 1)^{qN} = |ϕ_{s,t}^{qN}(0)|,

since |u| ≤ |ϕ_{s,t}^{p+N−3}(01^{t})| = (t + 1)^{p+N−2} ≤ (t + 1)^{q} − 1. So, we can write ϕ_{s,t}^{qM}(0) = p_{M}s_{M}, where s_{M} is the corresponding suffix.

Now, by Lemma 14, we can write ϕ_{s,t}^{N−3}(1) = P_{s,t,N−3}P_{s,t,N−3}^{(1)} and ϕ_{s,t}^{N−3}(0) = P_{s,t,N−3}P_{s,t,N−3}^{(0)}, where we recall that P_{s,t,N−3} is the longest common prefix of ϕ_{s,t}^{N−3}(1) and ϕ_{s,t}^{N−3}(0), and where P_{s,t,N−3}^{(0)}, P_{s,t,N−3}^{(1)} are the corresponding suffixes. Now, consider the word ϕ_{s,t}^{p}(P_{s,t,N−3}). It begins with the letter 0. We can then write ϕ_{s,t}^{p}(P_{s,t,N−3}) = 0z, with z ∈ {0, 1}^{∗}.

Now, let us suppose first that s > 1. Then,

A_{M} = p_{M}^{−1}ϕ_{s,t}^{qM}(A_{0})
= p_{M}^{−1}ϕ_{s,t}^{qM}(ϕ_{s,t}^{p+N−3}(1^{t}0))
= p_{M}^{−1}ϕ_{s,t}^{qM}([0zϕ_{s,t}^{p}(P_{s,t,N−3}^{(1)})]^{t}[0zϕ_{s,t}^{p}(P_{s,t,N−3}^{(0)})])
= p_{M}^{−1}[p_{M}s_{M}ϕ_{s,t}^{qM}(z)ϕ_{s,t}^{p+qM}(P_{s,t,N−3}^{(1)})]^{t}[p_{M}s_{M}ϕ_{s,t}^{qM}(z)ϕ_{s,t}^{p+qM}(P_{s,t,N−3}^{(0)})].

We deduce that at every position 0 ≤ j ≤ |s_{M}|, there begins a repetition with period a conjugate of s_{M}ϕ_{s,t}^{qM}(z)ϕ_{s,t}^{p+qM}(P_{s,t,N−3}^{(1)})p_{M}, and excess of length ≥ |(ϕ_{s,t}^{qM}(z)| = |z|(t + 1)^{qM}. Thus, these repetitions have exponent at least

t + \frac{|z|(t + 1)^{qM}}{(|z| + 1)(t + 1)^{qM} + |P_{s,t,N−3}^{(1)}|(t + 1)^{p+qM}}

= t + \frac{|z|}{|z| + 1 + |P_{s,t,N−3}^{(1)}|(t + 1)^{p}}

= t + \frac{|P_{s,t,N−3}|(t + 1)^{p} − 1}{(|P_{s,t,N−3}| + |P_{s,t,N−3}^{(1)}|)(t + 1)^{p}} (since |z| = |ϕ_{s,t}^{p}(P_{s,t,N−3})| − 1)

= t + \frac{|P_{s,t,N−3}|(t + 1)^{p} − 1}{(t + 1)^{N−3}(t + 1)^{p}}
= t + \frac{s}{t} − \frac{s}{t(t + 1)^{N−3}} − \frac{1}{(t + 1)^{p+N−3}} = r.

As N can be taken arbitrarily large, the result follows.

Finally, let us suppose that s = 1. Then,

A_{M} = p_{M}^{−1}ϕ_{s,t}^{qM}(A_{0})
= p_{M}^{−1}ϕ_{s,t}^{qM}(ϕ_{s,t}^{p+N−3}(0^{t(t+1)+1}1))
= p_{M}^{−1}ϕ_{s,t}^{qM}([0zϕ_{s,t}^{p}(P_{s,t,N−3}^{(0)})]^{t(t+1)+1}[0zϕ_{s,t}^{p}(P_{s,t,N−3}^{(1)})])
= p_{M}^{−1}[p_{M}s_{M}ϕ_{s,t}^{qM}(z)ϕ_{s,t}^{p+qM}(P_{s,t,N−3}^{(0)})]^{t(t+1)+1}[p_{M}s_{M}ϕ_{s,t}^{qM}(z)ϕ_{s,t}^{p+qM}(P_{s,t,N−3}^{(1)})].

We deduce that at every position 0 ≤ j ≤ |s_{M}|, there begins a repetition with period a conjugate of s_{M}ϕ_{s,t}^{qM}(z)ϕ_{s,t}^{p+qM}(P_{s,t,N−3}^{(0)})p_{M}, and excess of length ≥ |(ϕ_{s,t}^{qM}(z)| = |z|(t + 1)^{qM}. Thus, these repetitions have exponent at least

t(t + 1) + 1 + \frac{|z|(t + 1)^{qM}}{(|z| + 1)(t + 1)^{qM} + |P_{s,t,N−3}^{(0)}|(t + 1)^{p+qM}}

= t(t + 1) + 1 + \frac{|z|}{|z| + 1 + |P_{s,t,N−3}^{(0)}|(t + 1)^{p}}

= t(t + 1) + 1 + \frac{|P_{s,t,N−3}|(t + 1)^{p} − 1}{(|P_{s,t,N−3}| + |P_{s,t,N−3}^{(0)}|)(t + 1)^{p}} (since |z| = |ϕ_{s,t}^{p}(P_{s,t,N−3})| − 1)

= t(t + 1) + 1 + \frac{|P_{s,t,N−3}|(t + 1)^{p} − 1}{(t + 1)^{N−3}(t + 1)^{p}}
= t(t + 1) + 1 + \frac{s}{t} − \frac{s}{t(t + 1)^{N−3}} − \frac{1}{(t + 1)^{p+N−3}} = r.

As N can be taken arbitrarily large, the result follows.

The following proposition shows the optimality of the previous results.

Proposition 17. Let q ≥ 2 be a rational number. If an infinite word is q^{+}-free, then it is not highly q-repetitive.

Proof. The proof uses an idea of Richomme mentioned in the conclusion of [CR]. Suppose to the contrary that x is an infinite q^{+}-free word that is highly q-repetitive. Consider two positions i and i + 1 in x. Since x is highly q-repetitive, it contains infinitely many q-powers starting at position i + 1, so in particular, there is a square ww at position i + 1. Similarly, there are infinitely many squares starting at position i. We now apply the following result proved by Ilie [ILI, Lemma 2]: In any word, if vv and uu are two squares at position i and ww is a square at position i + 1, then either |w| = |u| or |w| = |v| or |w| ≥ 2|v|. Since there are infinitely many squares starting at position i, this implies that |w| equals |v| for some square vv occurring at position i. This means that the q-power w^{n} starting at position i + 1 can be extended to the left by one letter to create a q^{+}-power. This is a contradiction, since x is q^{+}-free.

4 Highly repetitive ternary words

In this part, we will state some similar results in the case of the ternary alphabet. We recall that the repetition threshold of the ternary alphabet is 7/4, so for any α ≤ 7/4, there is no infinite α-free ternary word.

Theorem 18. For any real number β < 7/4, there exists an infinite ternary word that is both 7/4^{+}-free and highly β-repetitive.

Proof. For any real number β < 7/4, there exists an integer m ≥ 1 such that β ≤ 7/4 − \frac{1}{19^{m+2}} < 7/4. Let r = 7/4 − \frac{1}{19^{m+2}} , and let us construct a 7/4^{+}-free word which contains infinitely many r-powers at every position. We recall that μ_{D} is Dejean’s morphism.

We remark that μ_{D}^{m}(abcbabc) is a factor of μ_{D}^{m+2}(a). Indeed,

μ_{D}^{2}(a) = μ_{D}(a)μ_{D}(b)cabcbabcabacbabcbacμ_{D}(acbcabcbacbcacba),

and so

μ_{D}^{m+2}(a) = uμ_{D}^{m}(abcbabc)μ_{D}^{m}(abacbabcbac)μ_{D}^{m+1}(acbcabcbacbcacba),

where u = μ_{D}^{m+1}(ab)μ_{D}^{m}(c). Let us define q = m + 2.

We define the following sequence of finite words:

A_{0} = μ_{D}^{m}(abcbabc)
A_{1} = (u)^{−1}μ_{D}^{q}(A_{0})
⋮
A_{n} = (u)^{−1}μ_{D}^{q}(A_{n−1}).

(Here, the word μ_{D}^{q}(A_{n}) always has u as a prefix, since A_{n} always has a as a prefix). As abcbabc and μ_{D} are 7/4^{+}-free, then for any n ≥ 0, A_{n} is 7/4^{+}-free.

Similar arguments as in the proof of Theorem 11 prove that the sequence A_{n} converges to an infinite limit word we denote by w, and this limit is 7/4^{+}-free. We now prove that w contains infinitely many α-powers beginning at every position. Again with similar arguments as in the proof of Theorem 11, we can see that for any n ≥ 1,

A_{n} = (p_{n})^{−1}μ_{D}^{qn}(A_{0}),

where p_{n} is the word μ_{D}^{q(n−1)}(u) ⋯ μ_{D}^{q}(u)u. Moreover, we can see that p_{n} is a prefix of μ_{D}^{qn}(a). Indeed,

|p_{n}| = |u| ∑_{i=0}^{n−1} |μ_{D}(a)|^{qi}

= |u| ∑_{i=0}^{n−1} 19^{qi}
< 19^{qn} = |μ_{D}^{qn}(a)|.

So, we can write μ_{D}^{qn}(a) = p_{n}s_{n}, where s_{n} is a ternary word. For any n ≥ 1, A_{n} = (p_{n})^{−1}μ_{D}^{qn}(A_{0}) = (p_{n})^{−1}μ_{D}^{qn}(μ_{D}^{m}(abcbabc)). We know that μ_{D}^{m}(a) begins with the letter a, and let us denote its last letter by x ∈ {a, b, c}. We can write μ_{D}^{m}(a) = aXx, where X ∈ {a, b, c}^{∗}. Similarly, let us write μ_{D}^{m}(c) = cY y, where Y ∈ {a, b, c}^{∗}, and y ∈ {a, b, c}. We can also write μ_{D}^{qn}(y) = p̃_{n}s̃_{n}, with p̃_{n} and s̃_{n} two ternary words such that |p̃_{n}| = |p_{n}| and |s̃_{n}| = |s_{n}|. Then,

A_{n} = s_{n}μ_{D}^{qn}(Xxμ_{D}^{m}(b)cY)p̃_{n}s̃_{n}μ_{D}^{qn+m}(b)p_{n}s_{n}μ_{D}^{qn}(Xxμ_{D}^{m}(b)cY)p̃_{n}s̃_{n}.

It follows that at all positions 0 ≤ j ≤ |s_{n}|, there begins a repetition with period a conjugate of s_{n}μ_{D}^{qn}(Xxμ_{D}^{m}(b)cY)p̃_{n}s̃_{n}μ_{D}^{qn+m}(b)p_{n}, and of length

l = |s_{n}μ_{D}^{qn}(Xxμ_{D}^{m}(b)cY)p̃_{n}s̃_{n}μ_{D}^{qn+m}(b)p_{n}s_{n}μ_{D}^{qn}(Xxμ_{D}^{m}(b)cY)p̃_{n}|
= 2 · |Xxμ_{D}^{m}(b)cY | · 19^{qn} + 19^{qn+m} + 3 · 19^{qn}
= 19^{qn} · (7 · 19^{m} − 1),

since |X| = |Y | = |μ_{D}^{m}(a)| − 2 = 19^{m} − 2. These repetitions have exponent

\frac{19^{qn}(7 · 19^{m} − 1)}{19^{qn}|Xxμ_{D}^{m}(b)cY | + 19^{qn+m} + 2 · 19^{qn}} = \frac{7 · 19^{m} − 1}{4 · 19^{m}} = α.

As n can be taken arbitrarily large, the result follows.

Now, we will consider the problem for highly 7/4-repetitive words. This would be Richomme’s question for the ternary alphabet: what is the infimum of the real numbers α such that there exists an infinite ternary word which is both α-free and highly 7/4-repetitive?

Proposition 19. Let q ≥ 7/4 be a rational number. There is no q^{+}-free ternary word which is highly q-repetitive.

Proof. For q ≥ 2, the result follows from Proposition 17, so let us suppose that q < 2. Suppose there exists a word w over {a, b, c} that is q^{+}-free and highly q-repetitive. Then, any factor of w is left-special (i.e., has two left extensions). Indeed, let u be a factor of w, and let i denote its position in w. w is recurrent (every factor occurs infinitely often) because it is highly repetitive, so we can suppose i ≥ 1. There is a long enough q-repetition v beginning at position i. We denote its period by p. Then, u is repeated in the excess of v: pu is a factor of v. Now, let x_{1} = w_{i−1} and x_{2} = p_{|p|}. It is clear that x_{1} ≠ x_{2}, since otherwise, x_{1}v would be a q^{+}-repetition, which is impossible since w is q^{+}-free. So u has two left extensions. Moreover, as the factors aa, bb and cc are clearly forbidden, we can see that w contains the factor abab (by extending b on the left). But abab is a square, which contradicts the fact that w is q^{+}-free.

Theorem 20. There exists an infinite ternary word which is both 2-free and highly 7/4repetitive.

Proof. We use the morphism of Brandenburg, which is a square-free morphism:

μ_{B} : \begin{cases}a ↦ abacbabcbac \\ b ↦ abacbcacbac \\ c ↦ abcbabcacbc. \end{cases}

We use it to give a similar construction as in the proofs of Theorems 11 and 18. We consider the sequence:

A_{0} = cbacμ_{B}(cbc)abac = cbacabcbabcacbcabacbcacbacabcbabcacbcabac
A_{1} = (u)^{−1}μ_{B}^{3}(A_{0})
⋮
A_{n} = (u)^{−1}μ_{B}^{3}(A_{n−1}),

where u = μ_{B}^{2}(a)μ_{B}(ab)abacbab. The sequence A_{n} converges to a limit we denote by w, which is a square-free word because μ_{B} is square-free. For any n ≥ 1, if we denote by p_{n} the word μ_{B}^{3(n−1)}(u) ⋯ μ_{B}^{3}(u)u, we can see that A_{n} = (p_{n})^{−1}μ_{B}^{3n}(A_{0}). But p_{n} is a prefix of μ_{B}^{3n}(c), since

|p_{n}| = |u| ∑_{i=0}^{n−1} |μ_{B}(a)|^{3i}

= |u| ∑_{i=0}^{n−1} 11^{3i}
< 11^{3n} = |μ_{B}^{3n}(c)|.

So, we can write μ_{B}^{3n}(c) = p_{n}s_{n}, where s_{n} is a ternary word. Then, for any n ≥ 1,

A_{n} = (p_{n})^{−1}μ_{B}^{3n}(A_{0})
= s_{n}μ_{B}^{3n}(bacabcbabcacbcaba)p_{n}s_{n}μ_{B}^{3n}(bca)p_{n}s_{n}μ_{B}^{3n}(bacabcbabcacbcaba)p_{n}s_{n}.

It follows that at all positions 0 ≤ j ≤ |s_{n}|, there begins a repetition with period a conjugate of s_{n}μ_{B}^{3n}(bacabcbabcacbcaba)p_{n}s_{n}μ_{B}^{3n}(bca)p_{n}, and of length

l = |s_{n}μ_{B}^{3n}(bacabcbabcacbcaba)p_{n}s_{n}μ_{B}^{3n}(bca)p_{n}s_{n}μ_{B}^{3n}(bacabcbabcacbcaba)p_{n}|
= 40 · 11^{3n}.

These repetitions have exponents 40/22 = 20/11 ≥ 7/4. As n can be taken arbitrarily large, the result follows.

Remark 21. In fact, with this proof, we have the result: There exists an infinite 2-free ternary word which is highly 20/11-repetitive.

So the problem of finding the infimum of the real numbers α such that there exists an infinite ternary α^{+}-free word which is highly 7/4-repetitive is open. We proved that this infimum is between 7/4 and 2.

5 Weaker results on ternary words

In the following section, we will prove some weaker results for words over the ternary alphabet. First, instead of considering highly repetitive words, we consider words with powers at every position. Then, we will discuss words containing infinitely many powers, but not necessary at every position. These questions were asked at the end of [CR] by Currie and Rampersad.

The following results concern Dejean’s morphism μ_{D} and its behaviour regarding repetitions and synchronizing properties, and were proved in [VAS]. If v is a word, we denote by δ the application that removes the first letter of v (and so, δ^{t}(v) removes the first t letters of v). Moreover, we denote by 𝔉_{D} the set Fact(μ_{D}({a, b, c}^{∗})) of factors of μ_{D}({a, b, c}^{∗}).

Lemma 22 ([VAS]). Let α ∈]7/4, 2[ be given. Let s, t be natural numbers such that μ_{D}^{s}(b) = xabcbabcy, with |x| = t. Let β = 2− \frac{t}{4·19^{s}}. Suppose that 7/4 < β < α, and that abcbabcv ∈ 𝔉_{D} is α-free. Consider the word w = δ^{t}μ_{D}^{s}(babcbabcv). Then, we have:

1. w has a prefix with exponent β.

2. If abcbabcv has a factor with exponent γ and period p, then, w has a factor with exponent γ and a period of length 19^{s}|p|.

3. w is α-free.

Definition 23 ([VAS]). A real number β < α is said to be obtainable if β can be written as β = 2 − \frac{t}{4·19^{s}}, where the natural numbers s and t satisfy:

* s ≥ 3

* the word δ^{t}(μ_{D}^{s}(b)) begins with abcbabc.

We note that for any given s ≥ 3, it is possible to choose t such that

* 7/4 < β = 2 − \frac{t}{4·19^{s}} < α

* |α − β| ≤ \frac{19^{2}}{4·19^{s}}.

Indeed, μ_{D}^{2}(a), μ_{D}^{2}(b), and μ_{D}^{2}(c) have length 19^{2}, and each has abcbabc as a factor. Therefore, choosing a large enough s, we can always find some obtainable real numbers β arbitrarily close to α.

Theorem 24. For every real number α > 7/4, there exists an infinite α-free ternary word that contains 7/4-powers beginning at every position.

Proof. Theorem 3.4 in [CR] established the result for any α > 2. Let us consider 7/4 < α ≤ 2. Let β be an obtainable number (see Definition 23), that is, it can be written as:

β = 2 − \frac{t}{4 · 19^{s}} ,

where s ≥ 3, and δ^{t}μ_{D}^{s}(b) begins with abcbabc.

For any word v in 𝔉_{D}, we denote by Φ(v) the word δ^{t}μ_{D}^{s}(bv) (we recall that δ(u), for some word u, removes the first letter of u) and we consider the sequence:

v_{1} = Φ(abcbabc) = δ^{t}μ_{D}^{s}(babcbabc)
v_{2} = Φ(v_{1}) = δ^{t}μ_{D}^{s}(bδ^{t}μ_{D}^{s}(babcbabc))
⋮
v_{n} = Φ(v_{n−1})
⋮

Let w = lim v_{n} (possible because each v_{i} is clearly a prefix of v_{i+1}). By iteration of Lemma 22, as abcbabc is α-free, each v_{i} is α-free, and then w is α-free.

For any n ≥ 0, w begins with a prefix of the form

δ^{t}μ_{D}^{s}(b)μ_{D}^{s}(δ^{t}μ_{D}^{s}(b)) ⋯ μ_{D}^{ns}(δ^{t}μ_{D}^{s}(b))μ_{D}^{(n+1)s}(abcbabc).

Thus, w contains the word μ_{D}^{ns}(δ^{t}(μ_{D}^{s}(b))μ_{D}^{(n+1)s}(abcbabc) at position

p_{n} = |δ^{t}μ_{D}^{s}(b)μ_{D}^{s}(δ^{t}μ_{D}^{s}(b)) ⋯ μ_{D}^{(n−1)s}(δ^{t}μ_{D}^{s}(b))|
= ∑_{i=1}^{n} |μ_{D}^{is}(b)| − ∑_{i=0}^{n−1} t · 19^{is}

= (19^{s} − t) ∑_{i=0}^{n−1} 19^{is}
= (19^{s} − t)\frac{19^{ns} − 1}{19^{s} − 1}

Moreover, the word μ_{D}^{ns}(δ^{t}μ_{D}^{s}(b))μ_{D}^{(n+1)s}(abcbabc) contains 7/4-powers at every position between 1 and q_{n} = |μ_{D}^{ns}(δ^{t}μ_{D}^{s}(b))| = (19^{s} − t) · 19^{ns}. So, in w, there is a 7/4-repetition starting at every position j, for every j ∈ [p_{n}, p_{n} + q_{n} − 1]. Since p_{n+1} = p_{n} + q_{n}, every position j in ℕ is reached.

Theorem 25. For every real number α ≥ 7/4 there exists a real number β, with 7/4 ≤ β < α, arbitrarily close to α, such that there is an infinite β^{+}-free ternary word containing infinitely many β-powers.

Proof. Theorem 3.4 in [CR] established the result for any α > 2. Let us consider 7/4 < α ≤ 2. Let β be an obtainable number, that is, it can be written as:

β = 2 − \frac{t}{4 · 19^{s}} ,

where s ≥ 3, and δ^{t}μ_{D}^{s}(b) begins with abcbabc.

Similarly to the proof of Theorem 24, we consider the sequence:

v_{1} = Φ(abcbabc) = δ^{t}μ_{D}^{s}(babcbabc)
v_{2} = Φ(v_{1}) = δ^{t}μ_{D}^{s}(bδ^{t}μ_{D}^{s}(babcbabc))
⋮
v_{n} = Φ(v_{n−1})
⋮

Let w = lim v_{n}. The word w is α-free, and it is β^{+}-free, since β < α. Moreover, for any n ≥ 1, w contains the word μ_{D}^{ns}(δ^{t}μ_{D}^{s}(babcbabc)), which has length 19^{ns}(8 · 19^{s} − t) and exponent β.

6 Conclusion

We propose the following definition. For an integer k, consider the set

𝔖_{k} = {(α, β) ∈ ℝ^{2} : there exists a word in {0, 1, …, k − 1}^{ω} which is α-free and

highly β-repetitive}.

The combined results of Currie and Rampersad [CR], and of Sections 3 and 4 of this paper, give a partial desciption of 𝔖_{k} for k = 2 and k = 3. We believe it is reasonable to expect the sets 𝔖_{k}, for k = 2 and k ≥ 3, to be as described respectively in Figure 1 and 2. Proving this would be an interesting continuation of this work, as it is obviously related to important open problems about critical exponents of morphic words.

β α 2\frac{7}{3}2\frac{7}{3}

Figure 1: Conjecture for k = 2 (𝔖_{2} in grey.)

\begin{matrix}β \\ α \\ 2 \\ RT (k) \\ RT (k) \end{matrix}

Figure 2: Conjecture for k ≥ 3 (𝔖_{k} in grey.)

References

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

[CR] J. Currie and N. Rampersad, Infinite words containing squares at every position, Theor. Inform. Appl. 44 (2010), 113–124.

[CRS] J. Currie, N. Rampersad, and J. Shallit, Binary words containing infinitely many overlaps, Electron. J. Combinatorics 13 (2006), #R82.

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

[DEK] F. M. Dekking, On repetitions in binary sequences, J. Comb. Theory Ser. A 20 (1976), 292–299.

[ILI] L. Ilie, A note on the number of squares in a word, Theoret. Comput. Sci. 380 (2007), 373–376.

[KRI] D. Krieger, Critical exponents and stabilizers of infinite words. Ph.D. thesis, University of Waterloo, 2008.

[RIC] G. Richomme. Personal communication, 2005.

[SAA] K. Saari, Everywhere α-repetitive sequences and Sturmian words, Europ. J. Combin. 31 (2010), 177–192.

[SHU] A. M. Shur, The structure of the set of cube-free ℤ-words in a two-letter alphabet (Russian), Izv. Ross. Akad. Nauk Ser. Mat. 64 (2000), 201–224. English translation in Izv. Math. 64 (2000), 847–871.

[TH2] A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiana No.10 (1912), 1–67.

[VAS] E. Vaslet, Critical exponents of words over 3 letters, Electron. J. Combinatorics 18 (2011), P125.

2010 Mathematics Subject Classification: Primary 68R15. Keywords: repetition, Thue-Morse word, critical exponent.

(Concerned with sequence \underline{A010060}.)

Received June 28 2012; revised version received November 12 2012. Published in Journal of Integer Sequences, March 2 2013.

Return to Journal of Integer Sequences home page.