James Currie
email: j.currie@uwinnipeg.ca.

L ' Ubomíra Dvořáková
email: lubomira.dvorakova@fjfi.cvut.cz.

Pascal Ochem
email: ochem@lirmm.fr.

Daniela Opočenská

Narad Rampersad
email: n.rampersad@uwinnipeg.ca.

Jeffrey Shallit
email: shallit@uwaterloo.ca.

Complement Avoidance in Binary Words

The complement x of a binary word x is obtained by changing each 0 in x to 1 and vice versa. We study infinite binary words w that avoid sufficiently large complementary factors; that is, if x is a factor of w, then x is not a factor of w. In particular, we classify such words according to their critical exponents.

Introduction

Let x be a finite nonempty binary word. We write x for the complementary word, image of the morphism that maps 0 → 1 and 1 → 0, and we write x R for the reversal (mirror image) of x. We say y is a factor of a (one-sided) infinite word w if w = xyz for a finite word x and an infinite word z. In this paper, we are interested in the construction of and properties of infinite binary words w avoiding complementary factors: that is, if x is a nonempty factor of w, then x is not. This is not a new notion; for example, complement avoidance in de Bruijn words was studied by Sawada et al. [START_REF] Sawada | De Bruijn sequences for the binary strings with maximum density[END_REF].

Evidently it is impossible for an infinite word to avoid complementary factors of all lengths, except in the trivial cases 0 ω = 000 • • • and 1 ω = 111 • • • . A natural question then poses itself: are there such infinite words if the set of exceptions is restricted in some way, say by length or by cardinality? And what is the repetition threshold of such infinite words? We now turn to repetitions.

We say that a finite word w = w [1..n] has period p ≥ 1 if w[i] = w[i + p] for 1 ≤ i ≤ n -p. The smallest period of a word w is called the period, and we write it as per(w). The exponent of a finite word w, written exp(w) is defined to be |w|/ per(w). For a real number α, we say a word (finite or infinite) is α-free if the exponent of all its nonempty factors is < α. We say a word is α + -free if the exponent of all its nonempty factors is ≤ α. A word that is 2-free is also called squarefree, and a word that is 3-free is also called cubefree. A word that is 2 + -free is also called overlap-free.

The critical exponent of a finite or infinite word x is the supremum, over all nonempty finite factors w of x, of exp(w); it is written ce(x). The repetition threshold for a language L of infinite words is defined to be the infimum, over all x ∈ L, of ce(x).

The repetition thresholds for various classes of words have been studied extensively. To name just a few classes, Dejean [START_REF] Dejean | Sur un théorème de Thue[END_REF] determined the repetition threshold for all words over a 3-letter alphabet, and conjectured its value for larger alphabets. Her conjecture attracted a lot of attention, and was finally resolved by Rao [START_REF] Rao | Last cases of Dejean's conjecture[END_REF] and Currie and Rampersad [START_REF] Currie | A proof of Dejean's conjecture[END_REF], independently.

Other classes that have been studied include the Sturmian words, studied by Carpi and de Luca [START_REF] Carpi | Special factors, periodicity, and an application to Sturmian words[END_REF]Prop. 15]; the palindromes, studied in [START_REF] Shallit | Minimal critical exponents for palindromes[END_REF]; the rich words, studied by Currie et al. [START_REF] Currie | The repetition threshold for binary rich words[END_REF]; the balanced words, studied by Rampersad et al. [START_REF] Rampersad | Critical exponents of infinite balanced words[END_REF] and Dvořáková et al. [START_REF] Dvořáková | On minimal critical exponent of balanced sequences[END_REF]; and the complementary symmetric Rote words, studied by Dvořáková et al. [START_REF] Dvořáková | Complementary symmetric Rote sequences: the critical exponent and the recurrence function[END_REF]. Other related works include [START_REF] Ilie | A generalization of repetition threshold[END_REF][START_REF] Badkobeh | Finite-repetition threshold for infinite ternary words[END_REF][START_REF] Fiorenzi | Bounds for the generalized repetition threshold[END_REF][START_REF] Samsonov | On Abelian repetition threshold[END_REF][START_REF] Mousavi | Repetition avoidance in circular factors[END_REF].

In this paper we study the repetition threshold for two classes of infinite words:

• CAL ℓ , the binary words for which there is no length-ℓ word x such that both x and x appear as factors;

• CAN n , the binary words for which there are at most n distinct words x such that both x and x appear as factors.

It turns out that there is an interesting and subtle hierarchy, depending on the values of ℓ and n.

Our work is very similar in flavor to that of [START_REF] Shallit | Simultaneous avoidance of large squares and fractional powers in infinite binary words[END_REF], which found a similar hierarchy concerning critical exponents and sizes of squares avoided. The hierarchy for complementary factors, as we will see, however, is significantly more complex.

We will need the following famous infinite words.

• The Fibonacci word f = 0100101001001010010100100 • • • , fixed point of the morphism 0 → 01, 1 → 0. See, for example, [START_REF] Berstel | Fibonacci words-a survey[END_REF].

• The word p = 0121021010210121010210121 • • • , fixed point of the morphism ϕ sending 0 → 01, 1 → 21, 2 → 0. This is sequence A287072 in the OEIS. Its properties were recently studied in [START_REF] Currie | Properties of a ternary infinite word[END_REF].

The paper is organized as follows. In Section 2, we introduce the class CAL ℓ mentioned above and we establish the hierarchy alluded to previously. Section 3 does the same thing for the class CAN n . In both cases we need some critical exponent calculations, which are carried out in Section 4. Finally, in Section 5 we study finite words avoiding complementary factors and determine under what conditions there are exponentially many such words.

The class CAL ℓ

In this section, we investigate the repetition threshold for the class CAL ℓ , the binary words w with the property that if x is a length-ℓ factor of w, then x is not. We will need two additional morphisms: the Thue-Morse morphism µ, which maps 0 → 01 and 1 → 10, and the morphism ψ, defined as follows:

0 → 011001 1 → 0 2 → 01101.
Lemma 1. Suppose x is an infinite binary word avoiding (7/3)-powers. Then x contains infinitely many (and hence, arbitrarily large) complementary factors.

Proof. By a result of Karhumäki and Shallit [START_REF] Karhumäki | Polynomial versus exponential growth in repetition-free binary words[END_REF], every infinite binary word avoiding e-powers for e ≤ 7 3 contains µ n (0) as a factor for all n ≥ 1. Such a word is of the form µ n-1 (01) = µ n-1 (0)µ n-1 (1), and these two terms are complementary factors of length 2 n-1 .

By Lemma 1, the lower limit on the repetition threshold is 7 3 . For ℓ = 1 the only such words are 0 ω and 1 ω . For ℓ = 2 the only such words are 0 ω , 1 ω , 10 ω , and 01 ω . Larger ℓ are handled in Theorem 3 below, but to prove it we first need to provide some terminology and a lemma from [START_REF] Mol | Extremal overlap-free and extremal β-free binary words[END_REF]. A morphism f : Σ * → ∆ * is called q-uniform if |f (a)| = q for all a ∈ Σ, and is called synchronizing if for all a, b, c ∈ Σ and u, v ∈ ∆ * , if f (ab) = uf (c)v, then either u = ε and a = c, or v = ε and b = c. The following result is quoted almost verbatim from [START_REF] Mol | Extremal overlap-free and extremal β-free binary words[END_REF]Lemma 23]:

Lemma 2. Let a, b ∈ R satisfy 1 < a < b. Let α ∈ {a, a + } and β ∈ {b, b + }. Let h : Σ * → ∆ * be a synchronizing q-uniform morphism. Set t = max 2b b -a , 2(q -1)(2b -1) q(b -1) .
If h(w) is β-free for every α-free word w with |w| ≤ t, then h(z) is β-free for every α-free word z ∈ Σ * .

We will use this lemma as follows: through an exhaustive search, we find an appropriate uniform morphism from {0, 1, 2} * → {0, 1} * , and then we apply this morphism to an arbitrary ternary squarefree word. Then we use the fact that there are uncountably many infinite ternary squarefree words, and exponentially many finite ternary squarefree words [START_REF] Shur | Growth properties of power-free languages[END_REF].

We are now ready to state and prove our result on avoiding complementary factors.

Theorem 3. There exists an infinite β + -free binary word containing no complementary factors of length ≥ ℓ, for the following pairs (ℓ, β). Moreover, this list of pairs is optimal.

(a) (3, 2 + α), where α = (1 + √ 5)/2.

(b) (5, 3)

(c) (7, 8
3 ) (d) (8, 5 2 ) (e) (11, γ ′ ), where γ ′ .

= 2.4808627161472369 is the critical exponent of p.

(f ) (13, 7 3 ).

Proof.

(a) (3, 2 + α) is achieved by any Sturmian word x with slope [0, 3, 1, 1, 1, 1, . . .] = (5 -√ 5)/10. As is well-known, a Sturmian word has exactly n + 1 factors of length n, and these factors are independent of the intercept of the Sturmian word. For intercept 0, the first 6 symbols are 001000, and so the four factors of x of length 3 are 001, 010, 100, 000, and no complement of these words appears as a factor of x.

On the other hand, we know from the proof of Proposition 15 of [START_REF] Carpi | Special factors, periodicity, and an application to Sturmian words[END_REF] that the critical exponent of x is 2 + α. Thus, since we can choose the intercept of a Sturmian word to be any real in [0, 1], there are uncountably many binary words in CAL 3 with critical exponent 2 + α. This is best possible, as shown in Theorem 16.

(b) [START_REF] Currie | The repetition threshold for binary rich words[END_REF][START_REF] Berstel | Fibonacci words-a survey[END_REF] is achieved by applying the 17-uniform morphism h 1 defined by 0 → 01000101000101001 1 → 01000101000100100 2 → 01000101000100010, to any ternary squarefree word w. It is easy, by checking all squarefree words of length 5, to ensure that h 1 (w) contains no complementary factors of length ≥ 6. To verify the 3 + -freeness of these words, we use Lemma 2 with α = 2, β = 3 + , q = 17, t = 6, and check that the morphism is indeed synchronizing and that the image of every ternary squarefree word of length ≤ 6 is 3 + -free. This gives uncountably many infinite binary words and exponentially many finite binary words with the desired avoidance property.

We use this same technique to verify the β + -freeness of every word in this paper that is obtained with a uniform morphism.

To see that this result is optimal, backtracking easily shows that the longest word that contains no complementary factors of length ≥ 6 and no cubes is of length 50, and one example is 00101001001101001001101001101001001101001101001001.

(c) (7, 8 3 ) is achieved by applying the 36-uniform morphism 0 → 001001010011001010010011001001010011 1 → 001001010010011001010011001010010011 2 → 001001010010011001001010011001010011, to any ternary squarefree word. This gives uncountably many infinite binary words and exponentially many finite binary words.

The longest word that contains no complementary factors of length ≥ 7 and no 8 3powers is of length 51 and one example is 001001100100110010100110010011001010011001010010100.

(d) (8, 5
2 ) is achieved by applying the morphism ξ, defined as follows

0 → 01 1 → 0110 2 → 1,
to the infinite word p mentioned above.

The proof that the critical exponent of ξ(p) is 5/2 is given in Section 4 starting from Section 4.6.

The longest binary word containing no complementary factors of length ≥ 10 and no 5 2 -powers is of length 75 and one example is 001011010011001011010011011001011010011001011010011011001011010011011001100.

(e) (11, γ ′ ) is achieved by the word ψ(p). In Section 4 we show that the critical exponent of ψ(p) is the same as that for p.

For ℓ = 12 and e = γ ′ , the optimality is proved as follows. Let z = 1001011001. We can check that ψ(p) avoids z and contains z, z R , and z R . Let x be the prefix of length 40 of ψ(p). A computer check shows that there is no infinite 5 2 -free binary word with ℓ ≤ 12 that avoids simultaneously x, x, x R , and x R .

By symmetry, we consider a bi-infinite 5 2 -free binary word w with ℓ ≤ 12 that contains x. Let X be the set containing the complements of the factors of length 12 of x. Thus ℓ ≤ 12 means that w avoids X.

We compute the set S of factors f such that ef g is Also, v is cube-free since w is 5 2 -free. By [6, Theorem 14], we know that v has the same set of factors as p. Thus w has the same set of factors as ψ(p). So, the critical exponent of ψ(p) is optimal for ℓ = 12.

(f) (13, 7 3 ) is achieved by applying the 69-uniform morphism 0 → 001001100101101001100101100100110100110010110100110010011010011001011 1 → 001001100101101001100100110100110010110100110010110010011010011001011 2 → 001001100101101001100100110100110010110010011010011001011010011001011 to any ternary squarefree word. This gives uncountably many infinite binary words and exponentially many finite binary words.

By Proposition 1, if e = 7 3 , then there are arbitrarily long complemented words.

The class CAN n

One could also try to minimize the total number n of complemented words that appear.

Obviously n has to be even. Recall that CAN n denotes the set of binary words w for which there are at most n distinct words x such that both x and x appear as factors of w. For n = 0 the only such infinite words are 0 ω and 1 ω . For n = 2 the only such infinite words are 0 ω , 1 ω , 01 ω , and 10 ω . For larger n the situation is summed up in the following theorem:

Theorem 4. There exists an infinite β + -free binary word having at most n complemented words, for the following pairs (n, β). Moreover, this list of pairs is optimal.

(a) (4, 2 + α)

(b) (8, 3) (c) (24, 8
3 ) (d) (36, 5 2 ) (e) (64, γ ′ ), where γ ′ .

= 2.4808627161472369 is the critical exponent of p.

(f ) (90, 7 3 ). Proof. For the positive part, we use the same words as in Theorem 3. That is, for every β ∈ {2 + α, 3, 8 3 , 5 2 , γ ′ , 7 3 }, the infinite β + -free binary words given in Theorem 3 to achieve the pair (ℓ, β) also achieve the pair (n, β) in Theorem 4. It is not hard to count the complemented factors in such words since their length is less than ℓ. Now let us consider the negative part.

(a) For 4 ≤ t ≤ 6 the optimal exponent we can avoid is 2 + α. To see this note that any such word must avoid having both x and x as factors if |x| ≥ 4, since taking non-empty prefixes of x and x gives at least 8 complemented factors. Hence, the smallest exponent that can be avoided is 2 + α by Theorem 16.

(b) For 8 ≤ t ≤ 22 one can avoid 3 + -powers, and this is optimal. The longest word having at most 22 complemented words, and no cubes is of length 50 and one example is 00101001001101001001101001101001001101001101001001.

(c) For 24 ≤ t ≤ 34 one can avoid 8 3 + -powers, and this is optimal. The longest word having at most 34 complemented words and no 8 3 -powers is of length 51 and one example is 001001100100110010100110010011001010011001010010100.

(d) For 36 ≤ t ≤ 62 one can avoid 5 2 + -powers and this is optimal. The longest word having at most 62 complemented words and no 5 2 -powers is of length 73 and one example is 0010110100110010110100110110010110100110010110100110110010110100110110010.

(e) For 64 ≤ t ≤ 88 the optimal exponent that can be avoided is γ ′ . We use the proof of optimality of Theorem 3 (e) and replace the condition ℓ ≤ 12 by t ≤ 88.

(f) For 90 ≤ t < ∞, the optimal exponent that can be avoided is

7 3 + . By Proposition 1, if e = 7 3
, then there are arbitrarily many complemented words.

Critical exponent of ξ(p) and ψ(p)

The infinite word p is the fixed point of the morphism ϕ, where

ϕ(0) = 01, ϕ(1) = 21, ϕ(2) = 0. (1)
Therefore, p = 01210210102101210102101210210121010 • • • The following characteristics of p are known (see [START_REF] Currie | Properties of a ternary infinite word[END_REF]):

• The factor complexity (number of distinct length-n factors) of p is 2n + 1.

• The word p is not closed under reversal because 02 is a factor of p, but 20 is not.

• The word p is uniformly recurrent because the morphism ϕ is primitive.

The morphism ψ is defined by

ψ(0) = 011001, ψ(1) = 0, ψ(2) = 01101. (2)
Therefore,

ψ(p) = 0110010011010011001011010 • • •
The morphism ξ is defined by

ξ(0) = 01, ξ(1) = 0110, ξ(2) = 1. (3)
Hence, ξ(p) = 0101101011001101100101100110110 • • • In this section, we compute the critical exponents of ψ(p) and ξ(p) using the lengths of their bispecial factors and their shortest return words.

First recall the definitions of bispecial and return word. Let u be an infinite word and let L(u) denote the language of all finite factors of u. Then w ∈ L(u) is called left special if aw, bw ∈ L(u) for two distinct letters a, b. A right special factor is defined analogously. The factor w is called bispecial if it is both left special and right special. A factor r of u is a return word to the factor w if rw ∈ L(u) and rw contains w exactly twice -once as a prefix and once as a suffix.

For a word u over an ordered d-letter alphabet Σ, we define its Parikh vector to be the vector of number of occurrences of each letter in u.

Theorem 5 ([9]

). Let u be a uniformly recurrent aperiodic sequence. Let (w n ) be a sequence of all bispecial factors ordered by their length. For every n ∈ N, let r n be a shortest return word to w n in u. Then

ce(u) = 1 + sup n∈N |w n | |r n | .

Bispecial factors in p

In order to determine bispecial factors in ψ(p) and in ξ(p), we need to explore bispecial factors in p. First, we will look at the left special factors (LS). Observing the form of ϕ, we can see that every LS has left extensions either {0, 2}, or {0, 1}.

Observation 6. Let v ∈ L(p), v = ε. Then • v is LS such that 0v, 2v ∈ L(p) if and only if v is a prefix of 1ϕ(w)
, where w is LS such that 0w, 1w ∈ L(p).

• v is LS such that 0v, 1v ∈ L(p) if and only if v is a prefix of ϕ(w), where w is LS such that 0w, 2w ∈ L(p).

Second, we will look at the right special factors (RS). By the definition of ϕ, every RS has right extensions either {1, 2}, or {0, 2}.

Observation 7. Let v ∈ L(p), v = ε. Then • v is RS such that v1, v2 ∈ L(p) if and only if v is a suffix of ϕ(w)0, where w is RS such that w0, w2 ∈ L(p).
• v is RS such that v0, v2 ∈ L(p) if and only if v is a suffix of ϕ(w), where w is RS such that w1, w2 ∈ L(p).

It follows from the form of left and right special factors that we have at most 4 possible kinds of nonempty bispecial factors in p. The following statements are obtained when combining Observations 6 and 7.

Corollary 8. Let v ∈ L(p) \ {ε} be a bispecial factor in p.

1. If 0v, 2v, v0, v2 ∈ L(p), there exists w such that v = 1ϕ(w) and 0w, 1w, w1, w2 ∈ L(p).

2. If 0v, 1v, v1, v2 ∈ L(p), there exists w such that v = ϕ(w)0 and 0w, 2w, w0, w2 ∈ L(p).

3. If 0v, 2v, v1, v2 ∈ L(p), there exists w such that v = 1ϕ(w)0 and 0w, 1w, w0, w2 ∈ L(p).

4. If 0v, 1v, v0, v2 ∈ L(p), there exists w such that v = ϕ(w) and 0w, 2w, w1, w2 ∈ L(p).

It follows from Corollary 8 that all bispecial factors may be constructed starting from the shortest ones in the following way: 1 is the shortest bispecial factor with left extensions {0, 2} and right extensions {0, 2}. Applying the morphism ϕ, we obtain the bispecial factor ϕ(1)0 with left extensions {0, 1} and right extensions {1, 2}. The second application of ϕ gives us the bispecial factor 1ϕ 2 (1)ϕ(0) with left extensions {0, 2} and right extensions {0, 2}. This process can be iterated infinitely many times

1 → ϕ(1)0 → 1ϕ 2 (1)ϕ(0) → ϕ(1)ϕ 3 (1)ϕ 2 (0)0 → 1ϕ 2 (1)ϕ 4 (1)ϕ 3 (0)ϕ(0) → • • •
Similarly, when starting with the bispecial factor 10 with left extensions {0, 2} and right extensions {1, 2}, we obtain after application of ϕ the bispecial factor ϕ(10) with left extensions {0, 1} and right extensions {0, 2}. After the second application of ϕ, we have the bispecial factor 1ϕ 2 (10)0 with left extensions {0, 2} and right extensions {1, 2}. We continue analogously and complete thus the list of all bispecial factors 10 → ϕ(10) → 1ϕ 2 (10)0 → ϕ(1)ϕ 3 [START_REF] Dvořáková | Complementary symmetric Rote sequences: the critical exponent and the recurrence function[END_REF]

ϕ(0) → 1ϕ 2 (1)ϕ 4 (10)ϕ 2 (0)0 → • • •
The following statement is an immediate consequence of Corollary 8. Proposition 9. Let w ∈ L(p)\{ε}. If w is a bispecial factor, then w has one of the following forms:

A) w (n) A = 1ϕ 2 (1)ϕ 4 (1) • • • ϕ 2n (1)ϕ 2n-1 (0)ϕ 2n-3 (0) • • • ϕ(0) for n ≥ 1.
If n = 0, then we set w (0)

A = 1.

The Parikh vector of w (n)

A is the same as of the factor 1ϕ(012)ϕ 3 (012)

• • • ϕ 2n-1 (012). B) w (n) B = ϕ(1)ϕ 3 (1) • • • ϕ 2n+1 (1)ϕ 2n (0)ϕ 2n-2 (0) • • • ϕ 2 (0)0 for n ≥ 0.

The Parikh vector of w (n)

B is the same as of the factor 012ϕ 2 (012)ϕ 4 (012)

• • • ϕ 2n (012). C) w (n) C = 1ϕ 2 (1)ϕ 4 (1) • • • ϕ 2n (1)ϕ 2n (0)ϕ 2n-2 (0) • • • ϕ 2 (0)0 for n ≥ 0.

The Parikh vector of w (n)

C is the same as of the factor 01ϕ 2 (01)ϕ 4 (01) • • • ϕ 2n (01).

D) w

(n)

D = ϕ(1)ϕ 3 (1) • • • ϕ 2n+1 (1)ϕ 2n+1 (0)ϕ 2n-1 (0) • • • ϕ(0)
for n ≥ 0.

The Parikh vector of w

The shortest return words in p

Let us derive the form of the shortest return words to all bispecial factors in p. We will make use of them when solving the same problem for ψ(p) and ξ(p).

• The return words to ε are 0, 1, 2.

• The return words to 1 are 12, 102, 10.

• The return words to 10 are 10, 102, 1012. The shortest one is 10 and it is a prefix of all of them.

• The return words to ϕ(1)0 are 210 = ϕ(1)0, 21010, 2101. The shortest one is 210 and it is a prefix of all of them.

Using this knowledge and the knowledge of how the bispecial factors can be constructed, we obtain the following observation for the shortest return words:

A) The shortest return words to w

Bispecial factors in ψ(p)

Let us start with some simple observations. If a factor v ∈ L(ψ(p)) contains the factor 11001 or 1101, then we are able to write v = xψ(w)y uniquely, where w ∈ L(p), and x (resp., y) is a proper suffix (resp., proper prefix) of the image of some letter. Moreover, if v is a bispecial factor in ψ(p), then w is a bispecial factor in p.

Observation 10. Let v ∈ L(ψ(p)) be a bispecial factor in ψ(p) such that it contains 11001 or 1101. Then one of the following items is true.

1. There exists w ∈ L(p) such that v = 01ψ(w)0110 and 0w, 2w, w0, w2 ∈ L(p).

2. There exists w ∈ L(p) such that v = ψ(w)0 and 0w, 1w, w1, w2 ∈ L(p).

3. There exists w ∈ L(p) such that v = 01ψ(w)0 and 0w, 2w, w1, w2 ∈ L(p).

A) v (n) A = 01ψ(1ϕ 2 (1)ϕ 4 (1) • • • ϕ 2n (1)ϕ 2n-1 (0)ϕ 2n-3 (0) • • • ϕ(0))0110
for n ≥ 1.

The Parikh vector of v (n)

A is the same as that of the factor 000111ψ(1ϕ(012)ϕ 3 (012) • • • ϕ 2n-1 (012)).

B) v

(n)

B = ψ(ϕ(1)ϕ 3 (1) • • • ϕ 2n+1 (1)ϕ 2n (0)ϕ 2n-2 (0) • • • ϕ 2 (0)0)0 for n ≥ 0.

The Parikh vector of v (n)

B is the same as that of the factor

0ψ(012ϕ 2 (012)ϕ 4 (012) • • • ϕ 2n (012)). C) v (n) C = 01ψ(1ϕ 2 (1)ϕ 4 (1) • • • ϕ 2n (1)ϕ 2n (0)ϕ 2n-2 (0) • • • ϕ 2 (0)0)0 for n ≥ 0.

The Parikh vector of v (n)

C is the same as of the factor 001ψ(01ϕ 2 (01)ϕ 4 (01)

• • • ϕ 2n (01)). D) v (n) D = ψ(ϕ(1)ϕ 3 (1) • • • ϕ 2n+1 (1)ϕ 2n+1 (0)ϕ 2n-1 (0) • • • ϕ(0))0110
for n ≥ 0.

The Parikh vector of v (n)

D is the same as of the factor 0011ψ(ϕ(01)ϕ 3 (01) • • • ϕ 2n+1 (01)).

The shortest return words in ψ(p)

Knowing the Parikh vectors of the shortest return words to bispecial factors in p and using the unambiguous reconstruction of w from ψ(w) when ψ(w) contains 11001 or 1101, we obtain the following observation for the shortest return words:

A) The shortest return word r

(n) A to v (n)
A , n ≥ 1, has the same Parikh vector as the factor ψ(ϕ 2n-1 (012)).

B) The shortest return word r

(n) B to v (n)
B , n ≥ 0, has the same Parikh vector as the factor ψ(ϕ 2n (012)).

C) The shortest return word r

(n) C to v (n)
C , n ≥ 0, has the same Parikh vector as the factor ψ(ϕ 2n (01)).

D)

The shortest return word r

(n) D to v (n)
D , n ≥ 0, has the same Parikh vector as the factor ψ(ϕ 2n+1 (01)).

Critical exponent of ψ(p)

Having determined the lengths of bispecial factors and of their shortest return words in ψ(p), we can use Theorem 5 to compute the critical exponent of ψ(p):

ce(ψ(p)) = 1 + max {A, B, C, D, E} A = sup |v (n) A | |r (n) A | : n ≥ 1 = sup |000111ψ(1ϕ(012)ϕ 3 (012) • • • ϕ 2n-1 (012))| |ψ(ϕ 2n-1 (012))| : n ≥ 1 ; B = sup |v (n) B | |r (n) B | : n ≥ 0 = sup |0ψ(012ϕ 2 (012)ϕ 4 (012) • • • ϕ 2n (012))| |ψ(ϕ 2n (012))| : n ≥ 0 ; C = sup |v (n) C | |r (n) C | : n ≥ 0 = sup |001ψ(01ϕ 2 (01)ϕ 4 (01) • • • ϕ 2n (01))| |ψ(ϕ 2n (01))| : n ≥ 0 ; D = sup |v (n) D | |r (n) D | : n ≥ 0 = sup |0011ψ(ϕ(01)ϕ 3 (01) • • • ϕ 2n+1 (01))| |ψ(ϕ 2n+1 (01))| : n ≥ 0 ; E = |w| |r|
: w bispecial not containing 11001 or 1101, r the shortest return word to w .

Computation of E

As summarized in Table 4.5.1, for each bispecial w that does not contain 11001 and 1101 and its shortest return word r, we have This recurrence relation may be solved and we obtain

a n = A 1 β n 1 + B 1 λ n 1 + C 1 λ n 2 ,
where

β 1 . = 1.75488, λ 1 . = 0.12256 + 0.74486i, λ 2 = λ 1
are the roots of the polynomial t 3 -2t 2 + t -1, and

A 1 = 12|λ 1 | 2 -38 Re(λ 1 ) + 32 |β 1 -λ 1 | 2 . = 10
.6175 ;

B 1 = 12β 1 λ 2 -19(β 1 + λ 2 ) + 32 (β 1 -λ 1 )(λ 2 -λ 1 )
. = 0.6912 -0.1330i ;

C 1 = B 1 .

Let us first determine

A ′ := lim sup n→+∞ |v (n) A | |r (n) A | = lim sup n→+∞ |000111ψ(1ϕ(012)ϕ 3 (012) • • • ϕ 2n-1 (012))| |ψ(ϕ 2n-1 (012))| .
We have

A ′ = lim sup n→+∞ 6 + 1 + n k=1 a 2k-1 a 2n-1 = lim sup n→+∞ 7 + A 1 n k=1 β 2k-1 1 + B 1 n k=1 λ 2k-1 1 + C 1 n k=1 λ 2k-1 2 A 1 β 2n-1 1 + B 1 λ 2n-1 1 + C 1 λ 2n-1 2 = lim n→+∞ 7 + A 1 β 1 β 2n 1 -1 β 2 1 -1 + B 1 λ 1 λ 2n 1 -1 λ 2 1 -1 + C 1 λ 2 λ 2n 2 -1 λ 2 2 -1 A 1 β 2n-1 1 + B 1 λ 2n-1 1 + C 1 λ 2n-1 2 = β 2 1 β 2 1 -1 . = 2.4809 . n k=1 β 2k-1 1 + B 1 n k=1 λ 2k-1 1 + C 1 n k=1 λ 2k-1 2 A 1 β 2n-1 1 + B 1 λ 2n-1 1 + C 1 λ 2n-1 2 ≤ ? β 2 1 β 2 1 -1 (β 2 1 -1) 7 + 2 Re B 1 λ 1 λ 2n 1 -1 λ 2 1 -1 + A 1 β 2n+1 1 -A 1 β 1 ≤ ? 2β 2 1 Re(B 1 λ 2n-1 1 ) + A 1 β 2n+1 1 (β 2 1 -1) 7 + 2 Re B 1 λ 1 λ 2n 1 -1 λ 2 1 -1 ≤ ? 2β 2 1 Re(B 1 λ 2n-1 1 ) + A 1 β 1 .
Now, on the one hand, for n ≥ 2, we have

(β 2 1 -1) 7 + 2 Re B 1 λ 1 λ 2n 1 -1 λ 2 1 -1 ≤ (β 2 1 -1) 7 + 2|B 1 ||λ 1 | |λ 1 | 2n + 1 |λ 2 1 -1| ≤ (β 2 1 -1) 7 + 2|B 1 ||λ 1 | |λ 1 | 4 + 1 |λ 2 1 -1|
.

On the other hand,

2β 2 1 Re(B 1 λ 2n-1 1 ) + A 1 β 1 ≥ A 1 β 1 -2β 2 1 |B 1 ||λ 1 | 2n-1 ≥ A 1 β 1 -2β 2 1 |B 1 ||λ 1 | 3 .
And if we substitute the values, we get

(β 2 1 -1) 7 + 2|B 1 ||λ 1 | |λ 1 | 4 + 1 |λ 2 1 -1| ≤ A 1 β 1 -2β 2 1 |B 1 ||λ 1 | 3 .
For n = 1, we get 7+a 1 a 1 = 1 + 7 19 < A ′ . Therefore

A = A ′ = β 2 1 β 2 1 -1 .
Next, we will use the same procedure for B.

B ′ := lim sup n→+∞ |v (n) B | |r (n) B | = lim sup n→+∞ |0ψ(012ϕ 2 (012)ϕ 4 (012) • • • ϕ 2n (012))| |ψ(ϕ 2n (012))| = lim sup n→+∞ 1 + n k=0 a 2k a 2n = lim sup n→+∞ 1 + A 1 n k=0 β 2k 1 + B 1 n k=0 λ 2k 1 + C 1 n k=0 λ 2k 2 A 1 β 2n 1 + B 1 λ 2n 1 + C 1 λ 2n 2 = β 2 1 β 2 1 -1
. Now we will show that B = B ′ , because for all n ≥ 0 we have

1 + A 1 n k=0 β 2k 1 + B 1 n k=0 λ 2k 1 + C 1 n k=0 λ 2k 2 A 1 β 2n 1 + B 1 λ 2n 1 + C 1 λ 2n 2 ≤ ? β 2 1 β 2 1 -1 (β 2 1 -1) 1 + 2 Re B 1 λ 2n+2 1 -1 λ 2 1 -1 + A 1 β 2n+2 1 -A 1 ≤ ? 2β 2 1 Re(B 1 λ 2n 1 ) + A 1 β 2n+2 1 (β 2 1 -1) 1 + 2 Re B 1 λ 2n+2 1 -1 λ 2 1 -1 ≤ ? 2β 2 1 Re(B 1 λ 2n 1 ) + A 1 .
Now, on the one hand, for all n ≥ 2, we have

(β 2 1 -1) 1 + 2 Re B 1 λ 2n+2 1 -1 λ 2 1 -1 ≤ (β 2 1 -1) 1 + 2 Re B 1 1 -λ 2 1 -2 Re B 1 λ 2n+2 1 1 -λ 2 1 ≤ (β 2 1 -1) 1 + 2 Re B 1 1 -λ 2 1 + 2|B 1 | |λ 2n+2 1 | |1 -λ 2 1 | ≤ (β 2 1 -1) 1 + 2 Re B 1 1 -λ 2 1 + 2|B 1 | |λ 1 | 6 |1 -λ 2 1 |
.

On the other hand,

2β 2 1 Re(B 1 λ 2n 1 ) + A 1 ≥ A 1 -2β 2 1 |B 1 ||λ 1 | 4 . Substituting the values proves that (β 2 1 -1) 1 + 2 Re B 1 1 -λ 2 1 + 2|B 1 | |λ 1 | 6 |1 -λ 2 1 | < A 1 -2β 2 1 |B 1 ||λ 1 | 4 .
For n = 0, we get 1+a 0 a 0 = 1+12 12 < B ′ . For n = 1, we get 1+a 0 +a 2 This recurrence relation can be solved and we obtain

c n = A 2 β n 1 + B 2 λ n 1 + C 2 λ n 2 , where β 1 . = 1.75488, λ 1 . = 0.12256 + 0.74486i, λ 2 = λ 1
are the roots of the polynomial t 3 -2t 2 + t -1, and

A 2 = 7|λ 1 | 2 -13 Re(λ 1 ) + 25 |β 1 -λ 1 | 2 . = 8.0149 ; B 2 = 7β 1 λ 2 -13(β 1 + λ 2 ) + 25 (β 1 -λ 1 )(λ 2 -λ 1 )
. = -0.5075 + 0.6315i ;

C 2 = B 2 . The proof of C ′ = D ′ = β 2 1 β 2
1 -1 proceeds in a similar fashion as that for B ′ (resp., A ′ ). To complete the proof, we need to show firstly C ≤ C ′ , i.e., for all n ≥ 0 that

3 + A 2 n k=0 β 2k 1 + B 2 n k=0 λ 2k 1 + C 2 n k=0 λ 2k 2 A 2 β 2n 1 + B 2 λ 2n 1 + C 2 λ 2n 2 ≤ ? β 2 1 β 2 1 -1 (β 2 1 -1) 3 + 2 Re B 2 λ 2n+2 1 -1 λ 2 1 -1 ≤ ? 2β 2 1 Re(B 2 λ 2n 1 ) + A 2 . Now, we have for all n ≥ 2 (β 2 1 -1) 3 + 2 Re B 2 λ 2n+2 1 -1 λ 2 1 -1 ≤ (β 2 1 -1) 3 + 2 Re B 2 1 -λ 2 1 + 2|B 2 | |λ 1 | 6 |1 -λ 2 1 | ; 2β 2 1 Re(B 2 λ 2n 1 ) + A 2 ≥ A 2 -2β 2 1 |B 2 ||λ 1 | 4 .
Substituting the values proves that

(β 2 1 -1) 3 + 2 Re B 2 1 -λ 2 1 + 2|B 2 | |λ 1 | 6 |1 -λ 2 1 | < A 2 -2β 2 1 |B 2 ||λ 1 | 4 .
For n = 0, we get 3+c 0

c 0 = 1 + 3 7 < C ′ . For n = 1, we get 3+c 0 +c 2 c 2 = 1 + 3+7 25 < C ′ . The inequality C ≤ C ′ is proven. Hence C = C ′ = β 2 1 β 2 1 -1 .
Finally, we need to prove D ≤ D ′ , i.e., for all n ≥ 1, that

4 + A 2 n k=1 β 2k-1 1 + B 2 n k=1 λ 2k-1 1 + C 2 n k=1 λ 2k-1 2 A 2 β 2n-1 1 + B 2 λ 2n-1 1 + C 2 λ 2n-1 2 ≤ ? β 2 1 β 2 1 -1 (β 2 1 -1) 4 + 2 Re B 2 λ 1 λ 2n 1 -1 λ 2 1 -1 ≤ ? 2β 2 1 Re(B 2 λ 2n-1 1 ) + A 2 β 1 .
Using the same estimates as for A and n ≥ 2, it remains to check the following inequality

(β 2 1 -1) 4 + 2|B 2 ||λ 1 | |λ 1 | 4 + 1 |λ 2 1 -1| ≤ A 2 β 1 -2β 2 1 |B 2 ||λ 1 | 3 .
The inequality holds for given values. For n = 1, we get

4+c 1 c 1 = 1 + 4 13 < D ′ . Consequently, D = D ′ .
We have shown that

A = B = C = D = β 2 1 β 2
1 -1 and E = 1 + 1 3 < A. In other words, we have proved the following theorem.

)) = 1 + β 2 1 β 2 1 -1 = 2 + 1 β 2 1 -1 . = 2.4808627161472369.
Let us emphasize that the critical exponents of p and ψ(p) are the same [START_REF] Currie | Properties of a ternary infinite word[END_REF].

Bispecial factors in ξ(p)

Now we turn to ξ(p). Let us start with some simple observations. If a factor v ∈ L(ξ(p)) contains the factor 00 or 1011 or 11010, then we are able to express v = xξ(w)y uniquely, where w ∈ L(p) and x (resp., y) is a proper suffix (resp., proper prefix) of an image of some letter. Moreover, if v is a bispecial factor in ξ(p), then w is a bispecial factor in p. Thus, we have E = 3 2 .

Computation of A, B, C, D

If we consider x n := |ξ(ϕ n (012))|, then we can see that x n satisfies the recurrence relation x n+1 = 2x n -x n-1 + x n-2 with initial conditions x 0 = 7, x 1 = 13, and x 2 = 24. This recurrence relation may be solved and we obtain

x n = X 1 β n 1 + Y 1 λ n 1 + Z 1 λ n 2 ,
where β 1 . = 1.75488, λ 1 . = 0.12256 + 0.74486i, λ 2 = λ 1 are the roots of the polynomial t 3 -2t 2 + t -1, and

X 1 = 7|λ 1 | 2 -
Z 1 = Y 1 .
We want to show for all n ≥ 1 that

6 + X 1 n k=1 β 2k-1 1 + Y 1 n k=1 λ 2k-1 1 + Z 1 n k=1 λ 2k-1 2 X 1 β 2n-1 1 + Y 1 λ 2n-1 1 + Z 1 λ 2n-1 2 ≤ ? β 2 1 β 2 1 -1 < 3 2 .
(β

5 2 -

 2 free and avoids X and |e| = |f | = |g| = 100. We compute the set S ′ of factors of ψ(p) of length 100. We verify that S = S ′ . This means that w = ψ(v) for some bi-infinite ternary word v. Moreover, by considering the pre-images by ψ of w = ψ(v) and ψ(p), this implies that v and p have the same set of factors of length 100/ max(|ψ(0)|, |ψ(1)|, |ψ(2)|) = 16. In particular, v avoids the set {00, 11, 22, 20, 212, 0101, 02102, 121012, 01021010, 21021012102} mentioned in [6, Theorem 14].

D

  is the same as of the factor ϕ(01)ϕ 3 (01) • • • ϕ 2n+1 (01).

A

  = 1 are 12 and 10. The shortest return word to w (n) A , n ≥ 1, has the same Parikh vector as the factor ϕ 2n-1 (012). B) The shortest return word to w (n) B , n ≥ 0, has the same Parikh vector as the factor ϕ 2n (012). C) The shortest return word to w (n) C , n ≥ 0, has the same Parikh vector as the factor ϕ 2n (01). D) The shortest return word to w (n) D , n ≥ 0, has the same Parikh vector as the factor ϕ 2n+1 (01).

4 .

 4 There exists w ∈ L(p) such that v = ψ(w)0110 and 0w, 1w, w0, w2 ∈ L(p). Corollary 11. Let v ∈ L(ψ(p)). If v is a bispecial factor containing 11001 or 1101, then v has one of the following forms:

|w| |r| ≤ 4 3 . 3 .Table 1 :

 331 = 1.333, therefore E = 1 + 1 Short bispecial factors w and their return words r 4.5.2 Computation of A and B If we consider a n := |ψ(ϕ n (012))|, then we can see that a n satisfies the recurrence relation a n+1 = 2a n -a n-1 + a n-2 with initial conditions a 0 = 12, a 1 = 19, and a 2 = 32.

a 2 = 1 + 1 β 2 1 - 1 . 4 . 5 . 3

 21121453 1+12 32 < B ′ . The inequality B ≤ B ′ is proven, and therefore B = B ′ = β 2 Computation of C and D If we consider c n := |ψ(ϕ n (01))|, then we can see that c n satisfies the same recurrence relation as a n , i.e., c n+1 = 2c n -c n-1 + c n-2 with initial conditions c 0 = 7, c 1 = 13, and c 2 = 25.

Theorem 12 .

 12 The critical exponent of ψ(p) equals ce(ψ(p

Observation 13 .

 13 Let v ∈ L(ξ(p)) be a bispecial factor such that it contains 00 or 1011 or 11010. Assume v = 1ξ(1) = 10110 and v = 1ξ(10) = 1011001. Then there exists w ∈ L(p) such that either v = ξ(w) and w is a bispecial factor with left extensions {0, 1}, or v = 01ξ(w) and w is a bispecial factor with left extensions {0, 2}. Moreover, the length of the shortest return word to v in ξ(p) equals |ξ(r)|, where r is the shortest return word to w in p.4.7 Critical exponent of ξ(p)Using Observation 13, the lengths of bispecial factors and their shortest return words in ξ(p) may be derived in an analogous way as in the case of ψ(p). Next, we can use Theorem 5 to compute the critical exponent of ξ(p):ce(ξ(p)) = 1 + max {A, B, C, D, E} A = sup |01ξ(1ϕ(012)ϕ 3 (012) • • • ϕ 2n-1 (012))| |ξ(ϕ 2n-1 (012))| : n ≥ 1 ; B = sup |ξ(012ϕ 2 (012)ϕ 4 (012) • • • ϕ 2n (012))| |ξ(ϕ 2n(012))| : n ≥ 0 ; C = sup |01ξ(01ϕ 2 (01)ϕ 4 (01) • • • ϕ 2n (01))| |ξ(ϕ 2n (01))| : n ≥ 0 ; D = sup |ξ(ϕ(01)ϕ 3 (01) • • • ϕ 2n+1 (01))| |ξ(ϕ 2n+1 (01))| : n ≥ 0 ; E = max |w| |r| : w short bispecial and r the shortest return word to w ,where we say that w is a short bispecial factor if w does not contain 00, 1011, 11010 or w = 1ξ(1) or w = 1ξ[START_REF] Dvořáková | Complementary symmetric Rote sequences: the critical exponent and the recurrence function[END_REF].

4. 7 . 1

 71 Computation of E w 0 1 01 10 101 0110 01101 1ξ(1) 1ξ(10) r 0 1 01 10 10 011 011010110 1ξ(1) 1ξ(10)1 -1

  26 Re(λ 1 ) + 24|β 1 -λ 1 | 2 Y 1 = 7β 1 λ 2 -13(β 1 + λ 2 ) + 24 (β 1 -λ 1 )(λ 2 -λ 1 )

	. = 7.704 ;
	. = -0.352 + 0.291i ;

  2 1 -1) 6 + 2 Re Y 1 λ 1 X 1 β 1 ≥ X 1 β 1 -2β 2 1 |Y 1 ||λ 1 | 13 .And if we substitute the values, we get(β 2 1 -1) 6 + 2|Y 1 ||λ 1 | |λ 1 | 14 + 1 |λ 2 1 -1| ≤ X 1 β 1 -2β 2 1 |Y 1 ||λ 1 | 13 .

	λ 2n 1 -1 λ 2 1 -1 1 -1) 6 + 2 Re Y 1 λ 1 + X 1 β 2n+1 1 (β 2 λ 2n 1 -1 -X 1 β 1 ≤ ? 2β 2 1 Re(Y 1 λ 2n-1 1 λ 2 1 -1 ≤ ? 2β 2 1 Re(Y 1 λ 2n-1 1	) + X 1 β 2n+1 1 ) + X 1 β 1 .
	Now, on one hand, for n ≥ 7 we have
	(β 2 1 -1) 6 + 2 Re Y 1 λ 1	λ 2n 1 -1 λ 2 1 -1	≤ (β 2 1 -1) 6 + 2|Y 1 ||λ 1 |	|λ 1 | 14 + 1 |λ 2 1 -1|	.
	On the other hand, we have
	2β 2 1 Re(Y 1 λ 2n-1 1	) +

The first 6 values from the set A are given in Table 2. We can see that they are all smaller than 3 2 . The inequality therefore holds for all n ≥ 1. We have shown that A < 3 2 = E. Using the same estimates, we can show that also the remaining values B, C, D are smaller than 3 2 . In other words, we have proved the following theorem.

Theorem 14. The critical exponent of ξ(p) equals 5 2 .

Complexity threshold

Notice that we used two different constructions of infinite words in the proof of Theorem 3.

When possible, that is in cases (b), (c), and (f ), we use morphic images of arbitrary ternary square-free words, thus showing that exponentially many binary words have the considered property. Otherwise, in cases (a), (d), and (e), every bi-infinite binary word with the considered property has the same set of factors as one or a few morphic words.

In this section, we consider the latter case and we relax the constraints on the critical exponent or the complementary factors in order to get exponential factor complexity.

Let h be the morphism that maps 0 → 0 and 1 → 01.

Lemma 15. Every bi-infinite binary 4-free word avoiding pairs of complementary factors of length 4 and {1001001, 0110110} has the same set of factors as either h(f) or h(f).

Proof. We compute the set S of factors y such that there exists a binary 4-free word xyz avoiding pairs of complementary factors of length 4 and {1001001, 0110110} and such that |x| = |y| = |z| = 100. We observe that S consists of the (disjoint) union of the factors of length 100 of h(f) and h(f). Let w be a bi-infinite binary 4-free word avoiding pairs of complementary factors of length 4 and {1001001, 0110110}. By symmetry, we suppose that w contains 00, so that w has the same factors of length 100 as h(f). So w ∈ {0, 01} ω , that is, w = h(v) for some bi-infinite binary word v. Since w is 4-free, so is v. Moreover, by considering the pre-images by h of w = h(v) and h(f), this implies that v and f have the same set of factors of length 100/ max(|h(0)|, |h(1)|) = 50. In particular, v avoids {11, 000, 10101}. By [2, Thm. 8], v has the same set of factors as f. Thus w has the same set of factors as h(f).

Theorem 16. Every bi-infinite binary 11 3 -free word that contains no pair of complementary factors of length 4 has the same set of factors as h(f) or the same set of factors as h(f).

Proof. Suppose that such a word w contains 1001001.

First, suppose that w contains 11. Since w avoids 0110 = 1001, w contains 111. Since w avoids the 4-power 1111, w contains 01110. Since w avoids 1101 = 0010, w contains 011100. Symmetrically, since w avoids 1011 = 0100, w contains 0011100. So w contains both 0011 and 1100, a contradiction. Thus, w avoids 11. Now, suppose that w contains 101. Since w avoids 11, w contains 01010. So w contains both 0101 and 1010, a contradiction. Thus, w avoids 101.

Since w contains 1001001 and avoids 11, w contains 010010010. Since w contains 010010010 and avoids 101, w contains 00100100100. This is a contradiction, since 00100100100 = (001)

Proof. First, we show the following. If w is a bi-infinite cube-free binary word and every factor of length 21 of w is also a factor of ξ(p), then w has the same set of factors as ξ(p).

We compute the set S of factors f such that there exists u = ef g, where u is cube-free, every factor of length 21 of u is a factor of ξ(p), and |e| = |f | = |g| = 500. We verify that every factor f ∈ S is a factor of ξ(p).

This means that w = ξ(v) for some bi-infinite ternary word v. Moreover, by considering the pre-images by ξ of w = ξ(v) and ξ(p), this implies that v and p have the same set of factors of length 500/ max(|ξ(0)|, |ξ(1)|, |ξ(2)|) = 125. In particular, v has the same set of factors as p by [START_REF] Currie | Properties of a ternary infinite word[END_REF]Theorem 14].

Similarly, we show that if w is a bi-infinite cube-free binary word and every factor of length 63 of w is also a factor of ρ(p), then w has the same set of factors as ρ(p).

Finally, we compute the set X of factors f such that there exists u = ef g, where u is