Finite Test Sets for Morphisms That Are Squarefree on Some of Thue’s Squarefree Ternary Words

James D. Currie Department of Mathematics and Statistics University of Winnipeg Winnipeg, Manitoba R3B 2E9 Canada

                     j.currie@uwinnipeg.ca

Abstract

Let S be one of {aba, cbc} and {aba, aca}, and let w be an infinite squarefree word over Σ = {a, b, c} with no factor in S. Suppose that f : Σ → T^{∗} is a non-erasing morphism. We prove that the word f(w) is squarefree if and only if f is squarefree on factors of w of length 8 or less.

1 Introduction

The papers of Thue on squarefree words [12, 13] are foundational to the area of combinatorics on words. A word w is squarefree if we cannot write w = xyyz, where y is a non-empty word. The longest squarefree words over the 2-letter alphabet {a, b} are aba and bab, each of length 3, but Thue showed that arbitrarily long squarefree words exist over the 3-letter alphabet {a, b, c}. Infinite squarefree words over finite alphabets are routinely encountered in combinatorics on words, and are frequently used as building blocks in constructions. (See, for example, [9, 10].)

Let w be an infinite squarefree word over Σ = {a, b, c}. Thue showed that w must contain every squarefree word of length 2 over Σ . However, he showed that the same is not true for squarefree words of length 3 over Σ. For each of S_{1} = {aba, cbc}, S_{2} = {aba, aca}, and S_{3} = {aba, bab}, Thue constructed an infinite squarefree word over Σ with no factor in S_{i}. Constructions giving squarefree words equivalent to Thue’s word with no factors in S_{1} were independently discovered by Braunholtz [4] and Istrail [8]; Berstel [1] shows this equivalence. Their word is called vtm (for ‘variation of Thue-Morse’) by Blanchet-Sadri et al. [3], and has been used as the basis for various constructions [3, 6, 7]. These constructions require showing that f(vtm) is squarefree for particular morphisms f. In this paper, we give a testable characterization of morphisms f such that f(vtm) is squarefree; we do the same in the case where vtm is replaced by an infinite squarefree word over Σ with no factors in S_{2}. We leave as an open problem whether there is a characterization when we replace vtm by a word over Σ with no factor in S_{3}.

Theorem 1. Let w be an infinite squarefree word over Σ such that either w has no factor in S_{1}, or w has no factor in S_{2}. Suppose that f : Σ → T^{∗} is a non-erasing morphism. The word f(w) is squarefree if and only if f is squarefree on factors of w of length 8 or less.

Our theorem says that to establish squarefreeness of f(w), the morphism f need only be checked for squarefreeness on a finite test set. Crochemore [5] proved a variety of similar theorems; in particular, a morphism f defined on Σ^{∗} preserves squarefreeness exactly when f preserves squarefreeness on words of Σ^{∗} of length at most 5. Note that while Crochemore’s theorem requires testing the squarefreeness of f(v) for every squarefree word v ∈ Σ^{∗} up to a certain length, we only test words v that are factors of w. Thus, while aba is squarefree, we do not require f(aba) to be squarefree, for example. Finite test sets for morphisms preserving overlap-freeness have also been well-studied [11].

2 Preliminaries

Let S = S_{1} or S = S_{2}. For the remainder of this paper, let w be an infinite squarefree word over Σ with no factor in S. Write w = a_{0}a_{1}a_{2}a_{3} ⋯ with a_{i} ∈ Σ. For the remainder of this section suppose that f : Σ → T^{∗} is a non-erasing morphism that is squarefree on factors of w of length 8 or less.

Lemma 2. Suppose f(ξ) is a factor of f(x), where x ∈ Σ and ξ is a factor of w. Then |ξ| ≤ 3.

Proof. If x is a letter of ξ, but f(ξ) is a factor of f(x), we have

|f(x)| ≤ |f(ξ)|
≤ |f(x)|.

Since f is non-erasing, this forces x = ξ, giving |ξ| = 1.

If x is not a letter of ξ, then ξ is a squarefree word over a two-letter alphabet, so that |ξ| ≤ 3.

Lemma 3. Suppose that f(x) is a prefix or a suffix of f(y) where x, y ∈ Σ. Then x = y.

Proof. We give the proof where f(x) is a prefix of f(y). (The other case is similar.) Suppose x ≠ y. Then xy must be a factor of w, and xy is squarefree. However, f(xy) begins with the square f(x)f(x), contradicting the squarefreeness of f on factors of w of length at most 8.

Lemma 4. There is no solution (α, β, γ, ξ, p, s, t, x, y, z) to

αξxyzβ is a factor of w; α, β, γ, x, y, z ∈ Σ, ξ ∈ Σ^{∗}; t is a suffix of f(γ); s is a suffix of f(α); p is a non-empty prefix of f(β); t = sf(ξxyz)p.

Proof. Suppose, for the sake of getting a contradiction, that (α, β, γ, ξ, p, s, t, x, y, z) is a solution.

Here p is a prefix of f(β), but also a suffix of t, that is a suffix of f(γ). Thus we see that f(γβ) contains square pp, so that γβ is not a factor of w. This forces γ = β. On the other hand, since zβ is a factor of w, we conclude that z ≠ γ. Again, f(z)p is a prefix of f(zβ), but also a suffix of f(γ), so that f(γzβ) contains a square. Since yzβ is a factor of w, it follows that y ≠ γ. Similarly, f(γyzβ) contains a square, but xyzβ is a factor of w, so that that x ≠ γ. Finally, we see that f(γxyzβ) contains a square. Let δ be the last letter of αξ. We conclude that δ ≠ γ. However, now δxyz is a squarefree word of length 4 over the two-letter alphabet Σ − {γ}. This is impossible.

The symmetrical lemma is proved analogously:

Lemma 5. There is no solution (α, β, γ, ξ, p, s, t, x, y, z) to

αξxyzβ is a factor of w; α, β, γ, x, y, z ∈ Σ, ξ ∈ Σ^{∗}; t is a suffix of f(γ); s is a non-empty suffix of f(α); p is a non-empty of f(β); t = sf(xyzξ)p.

Suppose that f(w) contains a non-empty square xx, with |x| as short as possible. Write f(w) = uxxv, such that

u = A_{0}A_{1} ⋯ A′_{i}
ux = A_{0}A_{1} ⋯ A′_{j}
uxx = A_{0}A_{1} ⋯ A′_{k},

where i ≤ j ≤ k are non-negative integers, and for each non-negative integer ℓ, A_{ℓ} = f(a_{ℓ}), and A′_{ℓ} is a prefix of A_{ℓ}, but A′_{ℓ} ≠ A_{ℓ}. This notation is not intended to exclude the possibilities that i = 0, i = j and/or j = k.

Remark 6. Since f is squarefree on factors of w of length at most 8, but f(a_{i} ⋯ a_{k}) contains the square xx, we must have k − i ≥ 8.

Remark 7. We cannot have i = j; otherwise suffix x of ux is a factor of A_{j} = A_{i}, and A_{i+1} ⋯ A_{k−1} is a factor of suffix x of uxx. Then, f(a_{i+1}a_{i+2} ⋯ a_{k−1}) is a factor of f(a_{i}), forcing (k − 1) − (i + 1) + 1 ≤ 3 by Lemma 2, so that k − i ≤ 4, a contradiction. Reasoning, in the same way, we show that i < j < k.

For ℓ ∈ {i, j, k}, let A′′_{ℓ} be the suffix of A_{ℓ} such that A_{ℓ} = A′_{ℓ}A′′_{ℓ}. By our choice of A′_{ℓ}, A′′_{ℓ} ≠ ϵ. Then

x = A′′_{i}A_{i+1} ⋯ A_{j−1}A′_{j} = A′′_{j}A_{j+1} ⋯ A_{k−1}A′_{k}.  (1)

Remark 8. Since k − i ≥ 8, we must have k − j − 1 ≥ 3 and/or j − i − 1 ≥ 3.

Lemma 9. We must have |A′′_{i}| + |A′_{k}| ≤ |x| and |A′′_{j}| + |A′_{j}| ≤ |x|.

Proof. We give the proof that |A′′_{j}| + |A′_{j}| ≤ |x|. (The proof of the other assertion is similar.) Suppose for the sake of getting a contradiction that |A′′_{j}|+|A′_{j}| > |x|. Then |A′′_{j}| > |x|−|A′_{j}| = |A′′_{i}A_{i+1} ⋯ A_{j−1}|. It follows that A′′_{j} = A′′_{i}A_{i+1} ⋯ A_{j−1}A′′′_{j} for some non-empty prefix A′′′_{j} of A_{j}. Similarly, one shows that A′_{j} = A′′′′_{j}A_{j+1} ⋯ A_{k−1}A′_{k} for some non-empty suffix A′′′′_{j} of A_{j}. Now |a_{i+1} ⋯ a_{j−1}| = (j −1)−(i+1)+1 = j −i−1, and |a_{j+1} ⋯ a_{k−1}| = (k−1)−(j +1)+1 = k − j − 1. However, either j − i − 1 ≥ 3, or k − j − 1 ≥ 3. If j − i − 1 ≥ 3, then A′′_{j} = A′′_{i}A_{i+1} ⋯ A_{j−1}A′′′_{j} for some non-empty prefix A′′′_{j} of A_{j} contradicts Lemma 4, letting s = A′′_{i}, α = a_{i}, ξ = a_{i+1} ⋯ a_{j−4}, xyz = a_{j−3}a_{j−2}a_{j−1}, p = A′′′_{j}, β = a_{j}.

In the case where k − j − 1 ≥ 3, we get the analogous contradiction using Lemma 5.

Lemma 10. We have j − i = k − j, A′′_{i} = A′′_{j}, A′_{j} = A′_{k}, and A_{i+ℓ} = A_{j+ℓ}, 1 ≤ ℓ ≤ j − i − 1.

Proof. To begin with we show that A′_{j} = A′_{k}. Since both words are suffixes of x, it suffices to show that |A′_{j}| = |A′_{k}|. Suppose not. Suppose that |A′_{k}| < |A′_{j}|.

By the previous lemma, |A′_{j}| ≤ |A_{j+1} ⋯ A_{k−2}A_{k−1}A′_{k}|. Let m be greatest such that |A_{m} ⋯ A_{k−1}A′_{k}| ≥ |A′_{j}|. Thus j + 1 ≤ m ≤ k − 1, and

|A_{m+1} ⋯ A_{k−1}A′_{k}| < |A′_{j}| ≤ |A_{m}A_{m+1} ⋯ A_{k−1}A′_{k}|.

If A′_{j} = A_{m}A_{m+1} ⋯ A_{k−1}A′_{k}, then A_{m} is a non-empty prefix of A′_{j}, forcing a_{m} = a_{j} so that A_{m} = A′_{j} = A_{j}, by Lemma 3. This is contrary to our choice of A′_{j}.

Similarly, suppose |A′_{k}| < |A′_{j}|. Suppose that |A′_{k}| < |A′_{j}|.

Again by the previous lemma, |A′_{k}| ≤ |A_{i+1} ⋯ A_{j−2}A_{j−1}A′_{j}|. Let m be greatest such that |A_{m} ⋯ A_{j−1}A′_{j}| ≥ |A′_{k}|. Thus i + 1 ≤ m ≤ j − 1, and

|A_{m+1} ⋯ A_{j−1}A′_{j}| < |A′_{k}| ≤ |A_{m}A_{m+1} ⋯ A_{j−1}A′_{j}|.

If A′_{k} = A_{m}A_{m+1} ⋯ A_{j−1}A′_{j}, then A_{m} is a non-empty prefix of A′_{k}, forcing a_{m} = a_{k} so that A_{m} = A′_{k} = A_{k}, by Lemma 3, contrary to our choice of A′_{k}.

We thus conclude that A′_{j} = A′_{k}, as desired.

Next, we show that j − 1 = k − j and A_{i+ℓ} = A_{j+ℓ}, 1 ≤ ℓ ≤ j − i − 1. Suppose that j − i ≤ k − j. (The other case is similar.) Suppose now that we have shown that for some ℓ, 0 ≤ ℓ < j − i − 1 that

A_{j−ℓ} ⋯ A_{j−1}A′_{j} = A_{k−ℓ} ⋯ A_{k−1}A′_{k}.  (2)

This is true when ℓ = 0; i.e., A′_{j} = A′_{k}.

From (1), one of A_{j−ℓ−1}A_{j−ℓ} ⋯ A_{j−1}A′_{j} and A_{k−ℓ−1}A_{k−ℓ} ⋯ A_{k−1}A′_{k} is a suffix of the other. Together with (2), this implies that one of A_{j−ℓ−1} and A_{k−ℓ−1} is a suffix of the other. By Lemma 3, this implies that a_{j−ℓ−1} = a_{k−ℓ−1}, and by combining this with (2),

A_{j−ℓ−1} ⋯ A_{j−1}A′_{j} = A_{k−ℓ−1} ⋯ A_{k−1}A′_{k}.  (3)

By induction we conclude that

A_{j−ℓ} ⋯ A_{j−1}A′_{j} = A_{k−ℓ} ⋯ A_{k−1}A′_{k}, 0 ≤ ℓ ≤ j − i − 1,

which implies A_{j−ℓ} = A_{k−ℓ}, 1 ≤ ℓ ≤ j − i − 1. In particular, we note that

A_{i+1} ⋯ A_{j−1} = A_{k−j+i+1} ⋯ A_{k−1}.  (4)

If we now have k − j > j − i, then k − j + i > j, and (1) and (4) imply that A′′_{i} = A′′_{j}A_{j+1} ⋯ A_{k−j+i}. Then A_{k−j+i} is a suffix of A′′_{i} and Lemma 3 forces A_{k−j+i} = A_{i}. Then (1) and (4) force A_{i} = A′_{i}, contrary to our choice of A′_{i}. We conclude that k − j = j − i. From (1) and (4) we conclude that A′′_{i} = A′′_{j}, as desired.

Corollary 11. The word w contains a factor αzβzγ, α, β, γ ∈ Σ, α, γ ≠ β, |z| ≥ 3, such that αβγ is not a factor of w.

Proof. By Lemma 10, w contains a factor αzβzγ, where α = a_{i}, β = a_{j}, γ = a_{k}, z = a_{i+1} ⋯ a_{j−1} = a_{j+1} ⋯ a_{k−1}. This gives |z| = j − i − 1 = k − j − 1 ≥ 3.

Since w is squarefree, we cannot have a_{i} = a_{j}; otherwise w contains the square (a_{0}z)^{2}; similarly, a_{j} ≠ a_{k}. To see that αβγ is not a factor of w, we note that f is squarefree on factors of w of length at most 8, but f(αβγ) = A_{i}A_{j}A_{k} contains the square (A′′_{i}A′_{j})(A′′_{j}A′_{k}); this is a square since A′′_{i} = A′′_{j} and A′_{j} = A′_{k}. Since |A_{i}A_{j}A_{k}| = 3 ≤ 8, we conclude that A_{i}A_{j}A_{k} is not a factor of w.

3 Results

Lemma 12. If S = {aba, cbc}, the only squarefree words of length 3 that are not factors of w are aba and cbc. In addition, w contains no factor of the form azbza or czbzc.

Proof. Thue [13] showed that a squarefree word over Σ not containing aba or cbc as a factor contains every other length 3 squarefree word as a factor.

Suppose w contains a factor azbza. Since aba is not a factor of w, z ≠ ϵ. Since az and bz are factors of w, and hence squarefree, the first letter of z cannot be a or b, and must be c. Similarly, the last letter of z must be c. But w contains zbz, and thus cbc. This is a contradiction. Therefore w contains no factor azbza.

Replacing a by c and vice versa in the preceding argument shows that w contains no factor czbzc.

Combining the last two lemmas gives this corollary:

Corollary 13. If S = {aba, cbc} and f : Σ^{∗} → T^{∗} is squarefree on factors of w of length at most 8, then f(w) is squarefree.

Lemma 14. If S = {aba, aca}, the only squarefree words of length 3 that are not factors of w are aba and aca. In addition, w contains no factor of the form azbza or azcza, |z| ≥ 3.

Proof. Thue [13] showed that a squarefree word over Σ not containing aba or aca as a factor contains every other length 3 squarefree word as a factor.

Suppose w contains a factor azbza, |z| ≥ 3. Since aba is not a factor of w, z ≠ ϵ. Since az and bz are factors of w, and hence squarefree, the first letter of z cannot be a or b, and must be c. Similarly, the last letter of z must be c. However, since az is a factor of w, but aca is not, the second letter of z cannot be a and must be b. Write z = cbz′c. Then azbza = acbz′cbcbz′ca contains the square cbcb, that is impossible. We conclude that w contains no factor azbza, |z| ≥ 3.

Replacing c by b and vice versa in the preceding argument shows that w contains no factor azcza, |z| ≥ 3.

Corollary 15. If S = {aba, aca} and f : Σ^{∗} → T^{∗} is squarefree on factors of w of length at most 8, then f(w) is squarefree.

Lemma 16. The squarefree word azbza where z = cabcbacabcacbacabcbac has no factors aba or bab. It follows that any analogous theorem for S_{3}, with an analogous proof, would require us to replace 8 by a value of at least |azbza| = 45.

Proof. This is established by a finite check.

4 Acknowledgments

The author’s research was supported by the Natural Sciences and Engineering Research Council of Canada (NSERC), [funding reference number 2017-03901]. The author thanks the careful referee and editor for their comments.

References

[1] J. Berstel, Sur la construction de mots sans carré, Sém. Théor. Nombres Bordeaux (1978– 1979), 18.01–18.15.

[2] J. Berstel, Axel Thue’s Papers on Repetitions in Words: a Translation, Publications du Laboratoire de Combinatoire et d’Informatique Mathématique 20 Université du Québec à Montréal, 1995.

[3] F. Blanchet-Sadri, J. Currie, N. Fox, and N. Rampersad, Abelian complexity of fixed point of morphism 0 → 012, 1 → 02, 2 → 1, INTEGERS 14 (2014), A11.

[4] C. Braunholtz, An infinite sequence of three symbols with no adjacent repeats, Amer. Math. Monthly 70 (1963), 675–676.

[5] M. Crochemore, Sharp characterizations of squarefree morphisms, Theoret. Comput. Sci. 18 (1982), 221–226.

[6] J. D. Currie, Which graphs allow infinite nonrepetitive walks?, Discrete Math. 87 (1991), 249–260.

[7] James Currie, Tero Harju, Pascal Ochem, and Narad Rampersad, Some further results on squarefree arithmetic progressions in infinite words, Theoret. Comput. Sci. 799 (2019), 140–148.

[8] S. Istrail, On irreductible languages and nonrational numbers, Bull. Math. Soc. Sci. Math. R. S. Roumanie 21 (1977), 301–308.

[9] M. Lothaire, Combinatorics on Words, Cambridge University Press, 1997.

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

[11] G. Richomme and F. Wlazinski, Overlap-free morphisms and finite test-sets, Discrete Appl. Math. 143 (2004), 92–109.

[12] Axel Thue, Über unendliche Zeichenreihen, Norske Vid. Selsk. Skr. Mat. Nat. Kl. 7 (1906), 1–22.

[13] Axel Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichentreihen, Norske Vid. Selske Skr. Mat. Nat. Kl. 1 (1912), 1–67.

2010 Mathematics Subject Classification: Primary 68R15. Keywords: Thue-Morse sequence, squarefree word, nonrepetitive word, factor.

(Concerned with sequences \underline{A010060} and \underline{A036577}.) Received October 3 2019; revised versions received November 30 2019; December 7 2019. Published in Journal of Integer Sequences, December 9 2019. Return to Journal of Integer Sequences home page.