Acta Polytechnica doi:10.14311/AP.2013.53.0868 Acta Polytechnica 53(6):868–871, 2013 © Czech Technical University in Prague, 2013 available online at http://ojs.cvut.cz/ojs/index.php/ap FACTOR AND PALINDROMIC COMPLEXITY OF THUE-MORSE’S AVATARS Christiane Frougnya, Karel Kloudab,∗ a LIAFA, CNRS UMR 7089, Case 7014, 75205 Paris Cedex 13, France b Faculty of Information Technology, Czech Technical University in Prague, Thákurova 9, Praha 6, 160 00, Czech Republic ∗ corresponding author: karel.klouda@fit.cvut.cz Abstract. Two infinite words that are connected with some significant univoque numbers are studied. It is shown that their factor and palindromic complexities almost coincide with the factor and palindromic complexities of the famous Thue-Morse word. Keywords: factor complexity, palindromic complexity, univoque numbers, Thue-Morse word. 1. Introduction The main result of this paper is the computation of the factor and palindromic complexity of two infinite words which appear in [1] as a representation of some significant univoque numbers. A real number λ > 1 is said to be univoque if 1 admits a unique expansion in base λ of the form 1 = ∑ i>0 aiλ −i with ai ∈{0, 1, . . . ,dλe− 1}. Komornik and Loreti showed in [2] that there is a smallest univoque number γ in the interval (1, 2). This number is transcendental [3] and is connected with the Thue-Morse word in this sense: if 1 = ∑ i>0 aiγ −i, then a1a2a3 · · · = 11010011 · · · = 0−1uTM, i.e., the Thue-Morse word without the leading zero. There are two generalizations of this result. The first one is the work of the same authors [4], where they studied the univoque numbers λ ∈ (1,b + 1), b ∈ N. The second one is the work of Allouche and Frougny [1]. They proved that there exists a smallest univoque number in (b,b + 1) (this is proved also in [5]) and they also found the corresponding unique expansion of 1. These expansions and some other significant words from [1] are studied in the sequel. As explained in the concluding remark, at least the factor complexity could be computed using the com- mon method employing special factors (see e.g. [6] for details). However, here we derive both complexities directly from the definition of words which really en- lighten the connection between the studied words and the Thue-Morse word. 2. Preliminaries An alphabet A is a finite set of letters. A concatenation of n letters v = v0v1 · · ·vn−1 from A is a (finite) word over A of length n. An infinite sequence u = u0u1u3 · · · is an infinite word over A. Any finite word v such that v = ukuk+1 · · ·uk+n−1 for some k ∈ N is called a factor of u and ukuk+1 · · ·uk+n−1 is its occurrence in it. The set of all factors of u is denoted by L(u), the set Ln(u) is the set of all factors of length n. The factor complexity of an infinite word u is the function Cu(n) that returns for all n ∈ N the number of factors of u of length n. Given a word v = v0v1 · · ·vn−1, the word ṽ is defined as vn−1vn−2 · · ·v1v0. If v = ṽ, v is called a palindrome. The palindromic complexity of an infinite word u is the function Pu(n) that returns for all n ∈ N the number of factors of u of length n that are palindromes. All infinite words in question are derived from the famous Thue-Morse word uTM. The Thue-Morse word is the fixed point of the Thue-Morse morphism ϕTM(0) = 01 ϕTM(1) = 10 starting in the letter 0, i.e., uTM = lim n→∞ ϕnTM(0) = 0110100110 · · · = ε0ε1ε2ε3 · · · . We are interested in the factor and palindromic com- plexity of infinite words w = m0m1m2 · · · given by mn = εn+1 − (2t− b− 1)εn + t− 1, (1) where 2t > b ≥ 1. In particular, we want to determine both complexities for all the three cases stated in [1, Theorem 2], i.e., for 2t ≥ b+3, 2t = b+2 and 2t = b+1. If 2t = b + 1, then mn = εn+1 + t−1 and so w equals the word 0−1uTM (after renaming the letters 0 → t−1 and 1 → t) having the same factor and palindromic complexity. Analogously, in the other two cases 2t ≥ b+ 3 and 2t = b+ 2, it is sufficient to consider only one choice of parameters t and b satisfying the inequality and the equality, respectively. That is because the former formula implies that the word w consists of four distinct letters b−t < b−t+ 1 < t−1 < t and the latter one that the word w consists of three distinct letters b− t < t− 1 < t. If we choose t = b = 3 and 868 http://dx.doi.org/10.14311/AP.2013.53.0868 http://ojs.cvut.cz/ojs/index.php/ap vol. 53 no. 6/2013 Factor and Palindromic Complexity of Thue-Morse’s Avatars t = b = 2 respectively, all the other words given by (1) are (after renaming the letters) equal to the words corresponding to these two choices of parameters b and t. Thus, we can simplify the definition of the infinite words we study as follows. Definition 1. For a = 1, 2, the infinite word wa = m0m1m2 · · · is defined by mn = εn+1 −aεn + a = εn+1 + a(1 −εn). (2) Hence, we get w1 = 210201210120 · · · w2 = 310302310230 · · · As we will see, the factor and palindromic complex- ity of the word wa will be expressed using the factor and palindromic complexity of the Thue-Morse word uTM. Therefore we recall the following two theorems. Theorem 2 [7], [8]. For the Thue-Morse sequence, CuTM (1) = 2, CuTM (2) = 4 and, for n ≥ 3, if n = 2r + q + 1, r ≥ 0, 0 ≤ q < 2r, then CuTM (n) = { 6 · 2r−1 + 4q if 0 ≤ q ≤ 2r−1, 2r+2 + 2q if 2r−1 < q < 2r. Theorem 3 [9]. Let n ≥ 3 and n = 2 · 4k + q, k ∈ N, 0 ≤ q < 6 · 4k, then PuTM (2n) = { 4 if 0 < q ≤ 3 · 4k, 2 if 3 · 4k < q < 3 · 4k or q = 0. Furthermore, PuTM (1) = PuTM (2) = PuTM (3) = PuTM (4) = 2 and there are no palindromes of odd length greater than 3. 3. Factor complexity The following lemma points out the similarity between the languages of the words uTM and wa. Lemma 4. There exists a bijective mapping from LuTM (n + 1) to Lwa (n) for all n ≥ 2. Proof. The mapping is defined by (2). We just have to prove that it is injective. Let mq · · ·mq+k and mp · · ·mp+k be two occurrences of the same factor of wa, k ≥ 1, q 6= p. We prove that the factors εqεq+1 · · ·εq+k+1 and εpεp+1 · · ·εp+k+1 are the same as well. Obviously, it suffices to prove it for the case of k = 1. Let mq = εq+1 + a(1 −εq ) = mp = εp+1 + a(1 −εp) and mq+1 = εq+2 + a(1 −εq+1) = mp+1 = εp+2 + a(1 −εp+1). Since there are only 8 possible three-letter binary words εpεp+1εp+2 and εqεq+1εq+2, it is easy to find all solutions of these two equations. If a = 2, then εpεp+1εp+2 = εqεq+1εq+2 is the unique solution of this system of two equations. If a = 1, εq = εq+1 = εq+2 6= εp = εp+1 = εp+2 is the only other solution, but it is not admissible since neither 000 nor 111 are factors of uTM. This lemma allows us to determine the factor com- plexity Cwa (n) for n ≥ 2. The case n = 1 is trivial, Cwa (1) is equal to the number of letters occurring in wa. Corollary 5. For both a = 1 and a = 2 and for all n ≥ 2, it holds Cwa (n) = CuTM (n + 1). Furthermore, Cw1 (1) = 3 and Cw2 (1) = 4. Corollary 6. For both a = 1 and a = 2, wa is square-free. Proof. Let ww be a factor of wa, w is of length n, and let ww = mi · · ·mi+2n−1. Then, according to the previous lemma, there exists a unique factor v of length n having b as its first letter such that vvb = εi · · ·εi+2n is a factor of uTM. But this is not possible since uTM is overlap-free (see e.g. [10]), which means exactly that it does not contain factors of this form. 4. Palindromic complexity As for the palindromic complexity, the difference be- tween the cases a = 1 and a = 2 is more significant than it is for the factor complexity. However, the result still remains strongly related to the palindromic complexity of uTM. First simple observation is that, since wa is square-free for both values of a, it cannot contain palindromes of even length since such palin- drome contains the square of a letter in its middle. Definition 7. Let A = {0, 1, . . . ,n},a ∈A and v = v1 · · ·vm ∈ A∗,n,m ≥ 1. Set ā = n − a and v̄ = v̄1 · · · v̄m. Lemma 8. Let p ≥ 2 be even. • A word mnmn+1 . . .mn+p is a palindrome of w2 if and only if εn = εn+2 = · · · = εn+p−2 = εn+p, εn+1 = εn+3 = · · · = εn+p−1 = εn+p+1, (3) where εn+1 6= εn. • A word mnmn+1 . . .mn+p is a palindrome of w1 if and only if εn = εn+p+1 ... εn+ p2 = εn+ p2 +1. (4) 869 Ch. Frougny, K. Klouda Acta Polytechnica Proof. We have for all i = 0, 1, . . . , p2 − 1 mn+i = εn+i+1 + a(1 −εn+i) = mn+p−i = εn+p−i+1 + a(1 −εn+p−i), mn+i+1 = εn+i+2 + a(1 −εn+i+1) = mn+p−i−1 = εn+p−i + a(1 −εn+p−i−1), (5) where mn+i 6= mn+i+1 due to the square-freeness of wa. These two equations have a trivial solution εn+i = εn+i+2 = εn+p−i 6= εn+i+1 = εn+p−i+1 = εn+p−i−1 for i = 0, 1, . . . , p2 − 2. For the case a = 2, it is the only solution. If a = 1, we can rewrite (5) as εn+1 + εn+p = εn + εn+p+1 εn+2 + εn+p−1 = εn+1 + εn+p ... εn+ p2 + εn+ p2 +1 = εn+ p2−1 + εn+ p2 +2. Now, considering that εn = εn+p+1 leads to inadmis- sible solution εn = εn+1 = · · · = εn+p+1, therefore, the factor εnεn+1 · · ·εn+p+1 is a solution if and only if (4) is satisfied. Thus, in the case of a = 2, the existence of a palin- drome of odd length p + 1,p ≥ 2 is equivalent to the existence of the factors 1010 · · ·10 or 0101 · · ·01 in uTM of length p + 2. But such words are factors of uTM only for p = 2. Theorem 9. It holds Pw2 (n) =   4 if n = 1, 2 if n = 3, 0 otherwise. In order to describe the relation between the palin- dromic complexities of w1 and uTM, we need to intro- duce the following definition. Definition 10. A factor v of an infinite word u is said to be a C-palindrome if v = ṽ. Denote CPu(n) the number of C-palindromes of length n in u. Lemma 8 says that there exists a bijective mapping between the set of palindromes in w1 of odd length p + 1, p ≥ 2, and the set of C-palindromes in uTM of length p + 2. Corollary 11. For n ≥ 1 it holds Pw1 (2n + 1) = CPuTM (2n + 2). Lemma 12. For all positive integers n it holds that CPuTM (2n) = PuTM (4n). Proof. It is readily seen that if v is a C-palindrome in uTM of length 2n , then ϕTM(v) is a palindrome of length 4n. Similarly, if v′ is a palindrome of length 4n, then there exists a unique C-palindrome v of length 2n such that ϕTM(v) = v′. Theorem 13. For n ≥ 1 Pw1 (2n + 1) = PuTM (4n + 4), Pw1 (1) = 3. There are no palindromes of even length in w1. 5. Remarks As remarked in [1, Remark 5], w1 = 210201210120 · · · is exactly the square-free Braunholtz sequence on three letters given in [11]. Moreover, this sequence is in fact the sequence uI which can be defined as the fixed point of Istrail’s substitution 1 7→ 102, 0 7→ 12, 2 7→ 0 [12], thus we obtain w1 from uI by exchanging letters 1 ↔ 2, 2 ↔ 0, 0 ↔ 1. Then, of course, the factor complexity of uI and w1 is the same. The word uI was studied in [13], where its factor complexity is computed using the notion of (right) special factors. In [13] the sequence uI is referred to as the Thue- Morse word on three symbols and as it is recalled there it was originally defined by Thue [14, 15] and later on rediscovered in various contexts by several authors, such as Morse [16]. Another relation between uI and uTM is also pointed out there: if we define a (non-primitive) substitution δ(1) 7→ 011,δ(0) 7→ 01,δ(2) 7→ 0, we have δ(uI) = uTM. Consequently, δ′(w1) = uTM for δ′(2) 7→ 011,δ′(1) 7→ 01,δ′(0) 7→ 0. Acknowledgements This work was supported by the Czech Science Foundation grant GAČR 13-35273P. References [1] J.-P. Allouche, et al. Univoque numbers and an avatar of Thue-Morse. Acta Arith 136:319–329, 2009. [2] V. Komornik, et al. Unique developments in non- integer bases. Amer Math Monthly 105:636–639, 1998. [3] J.-P. Allouche, et al. The Komornik-Loreti constant is transcendental. Amer Math Monthly 107:448–449, 2000. [4] V. Komornik, et al. Subexpansions, superexpansions and uniqueness properties in non-integer bases. Period Math Hungar 44:197–218, 2002. [5] M. de Vries, et al. Unique expansions of real numbers. Adv Math 221(2):390–427, 2009. [6] J. Cassaigne. Special factors of sequences with linear subword complexity. In Developments in Language Theory, pp. 25–34. World Scientific, 1996. [7] A. De Luca. On some combinatorial problems in free monoids. Discrete Math 38:207–225, 1982. [8] S. Brlek. Enumeration of factors in the Thue-Morse word. Discrete Appl Math 24:83–96, 1989. [9] A. Blondin-Massé, et al. Palindromic lacunas of the Thue-Morse word. Proc GASCOM 2008 pp. 53–67, 2008. 870 vol. 53 no. 6/2013 Factor and Palindromic Complexity of Thue-Morse’s Avatars [10] J.-P. Allouche, et al. Palindrome complexity. Theor Comput Sci 292:9–31, 2003. [11] C. H. Braunholtz. An infinite sequence on 3 symbols with no adjacent repeats, (Solution to Problem 439 posed by H. Noland). Amer Math Monthly 70:675–676, 1963. [12] S. Istrail. On irreducible languages and nonrational numbers. Bull Math Soc Sci Math R S Roumanie 21:301–308., 1977. [13] A. De Luca, et al. On the factors of the Thue-Morse word on three symbols. Inform Process Lett 27(6):281–285, 1988. [14] A. Thue. Über unendliche Zeichenreihen. Norske Vid Skrifter I Mat-Nat Kl Chris 7:1–22, 1906. [15] A. Thue. Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske Vid Skrifter I Mat-Nat Kl Chris 8:1–67, 1912. [16] M. Morse, et al. Unending chess, symbolic dynamics and a problem in semigroups. Duke Math J 11:1–7, 1944. 871 Acta Polytechnica 53(6):868–871, 2013 1 Introduction 2 Preliminaries 3 Factor complexity 4 Palindromic complexity 5 Remarks Acknowledgements References