Matthieu Rosenfeld

Avoiding squares over words with lists of size three amongst four symbols

In 2007, Grytczuk conjecture that for any sequence (ℓi) i≥1 of alphabets of size 3 there exists a square-free infinite word w such that for all i, the ith letter of w belongs to ℓi. The result of Thue of 1906 implies that there is an infinite square-free word if all the ℓi are identical. On the other, hand Grytczuk, Przyby lo and Zhu showed in 2011 that it also holds if the ℓi are of size 4 instead of 3.

In this article, we first show that if the lists are of size 4, the number of square-free words is at least 2.45 n (the previous similar bound was 2 n ). We then show our main result: we can construct such a square-free word if the lists are subsets of size 3 of the same alphabet of size 4. Our proof also implies that there are at least 1.25 n square-free words of length n for any such list assignment. This proof relies on the existence of a set of coefficients verified with a computer. We suspect that the full conjecture could be resolved by this method with a much more powerful computer (but we might need to wait a few decades for such a computer to be available).

Introduction

A square is a word of the form uu where u is a non-empty word. We say that a word is square-free (or avoids squares) if none of its factors is a square. For instance, hotshots is a square while minimize is square-free. In 1906, Thue showed that there are arbitrarily long ternary words avoiding squares [START_REF] Thue | Über unendliche Zeichenreihen[END_REF][START_REF] Thue | Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen[END_REF]. This result is often regarded as the starting point of combinatorics on words, and the generalizations of this particular question received a lot of attention.

Nonrepetitive colorings of graphs were introduced by Alon et al. [START_REF] Alon | Nonrepetitive colorings of graphs[END_REF]. A coloring of the vertices (or of the edges) of a graph is said to be nonrepetitive if there is no path of the graph whose color sequence is a square. The nonrepetitive chromatic number (resp. nonrepetitive chromatic index ) of a graph is the minimal number of colors in a nonrepetitive coloring of the vertices (resp. the edges) of the graph. Alon et al. showed that nonrepetitive chromatic index is as most O(∆ 2 ) where ∆ is the maximum degree of G [START_REF] Alon | Nonrepetitive colorings of graphs[END_REF]. Different authors successively improved the upper bounds on the nonrepetitive chromatic number and the nonrepetitive chromatic index and the best known bound for the nonrepetitive chromatic number is also in O(∆ 2 ) [START_REF] Dujmović | Nonrepetitive colouring via entropy compression[END_REF][START_REF] Gonçalves | Entropy compression method applied to graph colorings[END_REF][START_REF] Harant | Nonrepetitive vertex colorings of graphs[END_REF][START_REF] Rosenfeld | Another approach to non-repetitive colorings of graphs of bounded degree[END_REF]. Non-repetitive colorings have since been studied in many other contexts (see for instance [START_REF] Wood | Nonrepetitive Graph Colouring[END_REF] for a recent survey on this topic).

Most results regarding non-repetitive colorings of graphs of bounded maximal degree are based on the Lovász Local Lemma, entropy-compression, or related methods and they naturally hold in the stronger setting of list coloring. In this setting, each vertex is assigned a list of colors and the colorings of the graph must assign to each vertex a color from its list. The nonrepetitive list chromatic number is the smallest integer n such that the graph is nonrepetitively colorable as soon as all the lists contain at least n colors. This notion was studied in relation to many notions of colorings and contrary to the first intuition it is often not the case that the worst possible list assignment is the one that gives the same list to every vertex. For instance, every planar graph has nonrepetitive chromatic number at most 768, but can have an arbitrarily large nonrepetitive list chromatic number [START_REF] Dujmović | Planar graphs have bounded nonrepetitive chromatic number[END_REF]. However, the best known bound on the nonrepetitive chromatic number in terms of the maximal degree also holds for the nonrepetititive list chromatic number [START_REF] Wood | Nonrepetitive Graph Colouring[END_REF]. It is unknown whether the optimal bounds in terms of the maximal degree also holds for the nonrepetititive list chromatic number are indeed identical or not. The simplest graph for which the question is non-trivial is the path. The result of Thue implies that the nonrepetitive chromatic number of any path over at least four vertices is 3 [START_REF] Thue | Über unendliche Zeichenreihen[END_REF]. There are various simple proofs that the nonrepetitive list chromatic number of any path is at most 4 (see [START_REF] Grytczuk | Nonrepetitive list colourings of paths[END_REF] for a proof based on the Lefthanded Local Lemma, [START_REF] Grytczuk | New approach to nonrepetitive sequences[END_REF] for a proof based on entropy compression and [START_REF] Rosenfeld | Another approach to non-repetitive colorings of graphs of bounded degree[END_REF] for a proof based on a simple counting argument). It was first conjectured by Grytczuk [6] that the nonrepetitive list chromatic number of any path is in fact at most 3. This conjecture has been mentioned many times, but not much progress has been made in the direction of proving or disproving it (see for instance [START_REF] Gagol | Micek Pathwidth and Nonrepetitive List Coloring[END_REF][START_REF] Grytczuk | Nonrepetitive colorings of graphs -A survey[END_REF][START_REF] Czerwiński | Nonrepetitive colorings of graphs[END_REF][START_REF] Grytczuk | New approach to nonrepetitive sequences[END_REF][START_REF] Rosenfeld | Another approach to non-repetitive colorings of graphs of bounded degree[END_REF][START_REF] Škrabu | The Thue choice number versus the Thue chromatic number of graphs[END_REF][START_REF] Wood | Nonrepetitive Graph Colouring[END_REF][START_REF] Zhao | 2 + ε)-nonrepetitive list colouring of paths[END_REF] for some of the occurences of this problem).

The question can be reformulated in terms of combinatorics on words.

Question 1. Let A be an infinite alphabet. Is it true that for any sequence (ℓ i ) i≥1 of subsets of A of size 3 there exists an infinite square-free word w such that for all i, the i-th letter of w belongs to ℓ i ?

As already mentioned the answer is positive if 3 is replaced by 4. It was even shown in [START_REF] Rosenfeld | Another approach to non-repetitive colorings of graphs of bounded degree[END_REF] that there are at least 2 n such words of length n for any list assignment. We first show in this article, that there are at least 2.45 n such words. We then show our main result: if A is of size 4 then there is such a word. Our approach is similar to the idea of [START_REF] Rosenfeld | Another approach to non-repetitive colorings of graphs of bounded degree[END_REF], that is, we show some strong bounds on the number of such words using an inductive argument. Our approach also relies on ideas of an approach of Shur to bounds the number of words power-free languages [START_REF] Shur | Two-Sided Bounds for the Growth Rates of Power-Free Languages[END_REF] (this improves an older technique introduced by Kolpakov [START_REF] Kolpakov | On the number of repetition-free words[END_REF]). This idea is that instead of directly counting the words we associate a weight to each word and we count the total weight of the set of valid words. In the approach of Kolpakov, he had to deal with three different kinds of squares (short squares, long squares, and mid-length squares) and we borrow a trick from Shur that allows dealing with only two kinds of squares (i.e., the mid-length squares do not need to be dealt with separately). In fact, the main difference between our proof and the approach of Shur is that eigenvectors and eigenvalues are replaced by a more complicated notion (which does not seems to be well studied or even named in the litterature). For our main result, we use a computer to verify the existence of a set of weights with the right property. This approach could probably be applied if A is of size larger than 4 (and even for infinite A), but the computational power required is larger than what modern computers offer. In particular, we suspect that this approach would work if A was of size 21 and that would imply the conjecture.

The article is organized as follows. We first provide some notations and definitions in Section 2. In Section 3, we show that for any list assignment with lists of size 4, there are at least 2.45 n square-free words of size n. We use this proof to introduce our technique. In section 4, we use this technique to show our main result. In Section 5, we detail how we use the computer to verify the existence of the set of weights needed for our result. We conclude this article, in Section 6, by explaining why we suspect that the same approach could solve Question 1.

Definitions and notations

We use the standard definitions and notations of combinatorics on words introduced in Chapter 1 of [START_REF] Lothaire | Algebraic combinatorics on words[END_REF].

For the sake of notations, all our alphabets are sets of integers. For any fixed alphabet A, the set of extensions of a word w is the set of words {wa : a ∈ A}. That is, a word u is an extension of another word w is u can be obtained by the concatenation of a letter at the end of w. For any words w = w 1 w 2 . . . w n and any i, j such that 1 ≤ i ≤ j ≤ n, we write w[i, j] = w i w i+1 . . . w j .

A square is a word of the form uu with u a non-empty word. The period of the square uu is u and by abuse of notation we also call the length |u| of u the period of uu. A word is square-free (or avoids squares) if none of its factors is a square.

A list assignement is a sequence (ℓ i ) i≥1 of subsets of the integers. A k-list assignement is a list assignement (ℓ i ) i≥1 such that each list is of size 4, i.e. for all i ≥ 1, |ℓ i | = 4. We say that a word w = w 1 . . . w n respects a list assignement (ℓ i ) i≥1 if for all i ∈ {1, . . . , n}, w i ∈ ℓ i .

The number of square-free words over 4 letters

We say that a word of length at least 3 is perfect if its suffix of length 3 contains 3 distinct letters (it is 012 up to a permutation of the alphabet). A word is nice if its suffix of length 3 is 010 up to a permutation of the alphabet. A square-free word is either nice or perfect. The idea is that since nice words are intuitively easier to extend than nice words it is better to count them separately. However, since it is complicated to count them separately, we will count them together by weighting them. For any set of words S, S is the quantity obtained by summing the number of perfect words in S together with √ 3 -1 times the number of nice words in S. For instance, if S = {021, 010, 101, 212} then S = 3 √ 3 -2.

Lemma 2. Let ℓ = (ℓ i ) i≥1 be a 4-list assignement and let T n be the number of square-free words of length n that respect ℓ. Let β > 1 be a real such that

1 + √ 3 -1 β(β-1) ≥ β.
Then, for any n ≥ 3,

T n+1 ≥ β T n .
Proof. We proceed by induction on n. Suppose that for every i < n, T i+1 ≥ β T i .

Then, for all i,

T n ≥ β i T n-i . (1)
We need to show

T n+1 ≥ β T n . A word of length n + 1 is good if • it respects ℓ,
• its prefix of length n is in T n ,

• and it contains no square of period 1 or 2.

A word is wrong, if it is good, but not square-free (i.e., if one of its suffixes is a square of period longer than 2). Let G be the set of good words and F be the set of wrong words. Then T n+1 = G \ F and

T n+1 ≥ G -F . (2)
We will now lower bound G and then upper bound F to reach our result.

Let u be a perfect word from T n and let abc be the factor of size 3 at the end of u. Let us count the contributions to G of the extensions of u. Since u is perfect the only reason for a square of period 1 or 2 to appear when adding a letter to u is if this letter is c, so we need to forbid at most one letter of ℓ n+1 . Moreover, if b belongs to ℓ n+1 then there are at least 2 ways to extend u into a perfect word of G and one way to extend u to a nice word of G. In this case, the contribution of the extensions of u to G is at least 2 + ( √ 3 -1) = 1 + √ 3. If b does not belong to ℓ n+1 then there are at least 3 ways to extend u to a perfect word of G and the contribution of the extensions of u to G is at least 3. Thus the contribution to G of the extensions of any perfect word from T n is at least 1 + √ 3. So the contribution of the extensions of any perfect word to G is at least 1 + √ 3 times as large as its contribution to T n . For any value of the list ℓ n+1 , any nice word from T n can be extended in at least 2 perfect words of G. The contribution to G of the extensions of any nice word from T n is at least 2. Since the contribution of a nice word to T n is √ 3 -1, the contribution of the extensions of any nice word to G is at least

2 √ 3-1 = 1 +
√ 3 times as large as its contribution to T n .

Since the contribution of the extensions of any word to G is at least 1 + √ 3 times as large as its contribution to T n , we deduce

G ≥ (1 + √ 3) T n . (3)
Let us now bound F . For all i ≥ 1, let F i be the set of words from F that end with a square of period i. Clearly, F = ∪ i≥1 F i and

F ≤ i≥1 F i . (4)
By definition of G and F , |F 1 | = |F 2 | = 0. Let i ≥ 3 and u ∈ F i . Since u ends with a square of period i, the last i letters of u are uniquely determined by its prefix v of size n + 1 -i. Since v is a proper prefix of u, v ∈ T n+1-i . And moreover, the last 3 letters of v are identical to the last 3 letters of u. Thus the contribution of v to T n+1-i is the same as the contribution of u to F i . We deduce

F i = T n+1-i .
Using this last equation with ( 1) and ( 4) yields

F ≤ i≥3 F i ≤ i≥3 T n+1-i ≤ i≥3 T n β 1-i ≤ T n β(β -1)
.

We can use this bound and (3) in equation ( 8) to finally upper-bound T n+1 and we obtain

T n+1 ≥ 1 + √ 3 - 1 β(β -1) T n ≥ β T n
where the second inequality is a consequence of the theorem hypothesis.

Since β = 2.45 satisfies the condition of Lemma 2, we deduce the following theorem.

Theorem 3. Fix a 4-list assignement (ℓ i ) i≥1 and let T n be the set of square-free words of length n that respect this list assignement. Then for all n ≥ 1,

|T n | ≥ 1.45 n .
Proof. It is easy to verify that T 3 is not empty and thus T 3 > 0. One easily verifies that β = 2.45 satisfies the conditions of Theorem 5. Thus for all n ≥ 3,

T n ≥ T 3 2.45 3 × 2.45 n .
Since the weight of any words is at most 1, for any n ≥ 3,

|T n | ≥ T n ≥ T 3 2.45 3 × 2.45 n . (5)
For the sake of contradiction suppose that |T n | < 2.45 n for some n > 1. Then, there exists an integer i such that |T n | i < T3

2.45 3 × 2.45 ni . Any factor of a square-free word is square-free, so the sequence

(|T n |) n≥0 is submultiplicative, that is, for all i, j ≥ 1, |T i+j | ≤ |T i ||T j |. In particular, |T ni | ≤ |T n | i < T3
2.45 3 × 2.45 ni which contradicts equation [START_REF] Gagol | Micek Pathwidth and Nonrepetitive List Coloring[END_REF]. We deduce that for all n, |T n | ≥ 2.45 n , as desired.

Let us briefly explain why this value of 1 + √ 3 plays a particular role in this proof. If the lists are all identical then any perfect word can be extended in two ways into another perfect word and in one way into a nice word, while any nice word can only be extended in two ways into a perfect word. The matrix of the corresponding automaton is 2 1 2 0 .

The dominant eigenvalue of this matrix is 1 + √ 3 and one possible eigenvector is 1 √

3 -1 which also explains the choice of the weights. We do not need for our weights to be an eigenvector, but we require a property similar to the statement of Lemma 4. It happens to be the case that the vector that has this property is also the eigenvector of this matrix, which corresponds to the intuition that the worst choice of list assignment is the one where all the lists are identical.

Proof of the main result

We fix A = {0, 1, 2, 3}. An (A, 3)-list assignement is a sequence of subsets of size 3 of A. We also fix p = 21. A word is normalized if it is the smallest of all the words obtained by a permutation of the alphabet. Let Λ be the set of normalized prefixes of minimal squares of period at most p. For any w, we let Λ(w) be the longest word from Λ that is a suffix of w up to a permutation of the alphabet. For any set of words S, and any w ∈ Λ, we let S (w) be the set of words from S whose longest prefix that belongs to Λ up to a permutation of the alphabet is w, that is S (w) = {u ∈ S : Λ(u) = w}.

We denote the set of words that contain no square of period at most p by S ≤p f ree . We are now ready to state the following lemma. Lemma 4. There exist coefficients (C w ) w∈Λ such that C ε > 0 and for all v ∈ Λ,

αC v ≤ min l⊆A |l|=3 a∈l va∈S ≤p f ree C Λ(va) (6)
where α = 13948/10721 ≈ 1.301.

The proof of this lemma relies on a computer verification that we delay to section 5. For the rest of this section let us fix coefficients (C w ) w∈Λ and α that respect the conditions of Lemma 4. For each set S of words, we let

S = w∈Λ C w |S (w) | .
Whenever we mention the weight of a word w, we mean C Λ(w) .

The main idea of the proof of Theorem 5 is essentially the same as in Lemma 2, but we have a few more technicities to handle along the way. We are going to count inductively the total weight of the square-free words of size n that respect a fixed 3-list assignment. Intuitively, the set Λ plays the same role as {010, 012} and α plays the same role as 1 + √ 3. We are now ready to state our main Theorem. Theorem 5. Let ℓ = (ℓ i ) i≥1 be a (Σ, 3)-list assignement and for all n ≥ 0, let S n be the set of square-free words of length n that respect ℓ. Let β > 1 be a real number such that α -

β 1-p β -1 ≥ β .
Then for all n ≥ 0, S n+1 ≥ β S n .

Proof. We proceed by induction on n. Let n be an integer such that the lemma holds for any integer smaller than n and let us show that S n+1 ≥ β S n . By induction hypothesis, for all i,

S n ≥ β i S n-i . (7)
A word of length n + 1 is good if

• it respects ℓ,
• its prefix of length n is in S n ,

• and it contains no square of period at most p.

A word is wrong, if it is good, but not square-free (i.e., if one of its suffixes is a square of period longer than p). We let G be the set of good words and F be the set of wrong words. Then S n+1 = G \ F and

S n+1 ≥ G -F . (8)
Let us first lower-bound G = w∈Λ |G (w) |C w . By definition, Λ(v) is the longest suffix of v that is prefix of a square of period of length at most p (up to permutation of the alphabet). This implies that for any square-free word v and for any word u, vu ∈ S ≤p f ree if and only if Λ(v)u ∈ S ≤p f ree . For the same reason, for any square-free word v and letter a, Λ(va) = Λ(Λ(v)a). We then deduce that the contribution of the extentions of any word v ∈ S n to G is

a∈ℓn+1 va∈S ≤p f ree C Λ(va) = a∈ℓn+1 Λ(v)a∈S ≤p f ree C Λ(Λ(v)a) ≥ min l⊆A |l|=3 a∈l Λ(v)a∈S ≤p f ree C Λ(Λ(v)a) .
By Lemma 4, we deduce that the contribution of the extentions of any word v ∈ S n to G is at least αC Λ(v) . We sum the contributions over

S n G ≥ v∈Sn αC Λ(v) = u∈Λ αC u |S (u) n | = α S n . (9)
Let us now bound F . For all i, let F i be the set of words from F that end with a square of period i. Then F = ∪ i≥1 F i and

F ≤ i≥1 F i . ( 10
)
Let us now upper-bound the F i separately depending on i.

Case i ≤ p : By definition of G and F , any word from F avoids squares of period at most p. Hence, i ≤ p implies |F i | = 0 and F i = 0.

Case i > p : Let w ∈ Λ and u ∈ F (w) i

. For the sake of contradiction, suppose that |w| > i. Let v be the period of w. Then the factor of length i -|v| that ends a position n + 1 -|v| is identical to the last i -|v| letters of the word, that is

u[n + 2 -i, n + 1 -|v|] = u[n + 2 -i + |v|, n + 1] .
These two factors are well defined since |v| ≤ p < i. Moreover u ∈ F (w) i

, and the factor of length i -|v| that ends at position n + 1 -i is identical to the last i -|v| letters of the word, that is

u[n + 2 -2i + |v|, n + 1 -i] = u[n + 2 -i + |v|, n + 1] .
The resulting equality

u[n + 2 -i, n + 1 -|v|] = u[n + 2 -2i + |v|, n + 1 -i]
implies that there is a square of period i -|v| ≥ 1 in u. Since w is square free, we have 2|v| > |w| ≥ i and i -|v| < |v| ≤ p. So the square is of period at most p which is a contradiction. Hence if F (w) i is non-empty, then ≤ i. The suffix of length 2i of any word from F (w) i is a square, so the last i letters of any word of F (w) i are uniquely determined by the remaining prefix, and this prefix belongs to S (w) n+1-i (since |w| ≤ i). Hence,

F i ≤ S n+1-i ≤ S n β 1-i
where the second inequality comes from [START_REF] Czerwiński | Nonrepetitive colorings of graphs[END_REF]. This bound with [START_REF] Harant | Nonrepetitive vertex colorings of graphs[END_REF] yields

F ≤ i≥p+1 S n β 1-i ≤ S n β 1-p β -1 .
We use this bound and (9) in equation ( 8) to finally upper-bound S n+1 ,

S n+1 ≥ α - β 1-p β -1 S n ≥ β S n
where the second inequality is a consequence of the theorem hypothesis.

Since β = 1.25 satisfies the conditions of Theorem 5, we can deduce our main result. Theorem 6. Fix a (Σ, 3)-list assignement (ℓ i ) i≥1 and let S n be the set of squarefree words of length n that respect this list assignement. Then for all n ≥ 1,

|S n | ≥ 1.25 n .
Proof. By definition, S 0 = C ε . One easily verifies that β = 1.25 satisfies the conditions of Theorem 5. Thus for all n,

S n ≥ C ε × 1.25 n .
Hence,

|S n | ≥ S n max w∈Λ C w ≥ C ε max w∈Λ C w × 1.25 n . (11)
For the sake of contradiction suppose that |S n | < 1.25 n for some n > 1. By Lemma 4, C ε > 0 so there exists an integer i such that |S n | i < Cε maxw∈Λ Cw × 1.25 ni . Any factor of a square-free word is square-free, so the sequence [START_REF] Kolpakov | On the number of repetition-free words[END_REF]. We deduce that for all n, S n ≥ 1.25 n , as desired.

(|S n |) n≥0 is submultiplicative, that is, for all i, j ≥ 1, |S i+j | ≤ |S i ||S j |. In particular, |S ni | ≤ |S n | i < C ε × 1.25 ni which contradicts equation

Proof of Lemma 4

A classic procedure to compute Perron-Frobenius egeinvector (and eigenvalue) of a matrix is simply to iterate the matrix over some "random" starting vector. Our coefficients (C w ) w∈Λ plays a similar role to the role of an eigenvector and we use the same idea to compute the desired coefficients. In the case of Perron-Frobenius eigenvector, it is known that under general assumptions this procedure converges toward the desired vector. In our case, we suspect that the procedure is also convergent under rather general assumptions, but we did not try to prove anything in this direction. However, after enough iterations, we find a vector that respects the conditions of our Lemma. Before discussing the details of this procedure we restate the Lemma. Lemma 7. There exist coefficients (C w ) w∈Λ such that C ε > 0 and for all v ∈ Λ,

αC v ≤ min l⊆A |l|=3 a∈l va∈S ≤p f ree C Λ(va) (6)
where α = 13948/10721 ≈ 1.301.

It is enough to provide coefficients with the right property. Since |Λ| = 854683883, instead of providing the coefficients, it is more efficient to provide a computer program that computes the set Λ and the coefficients with the desired properties 1 . This also has the advantage that the same program directly verifies that the coefficients do indeed have the desired property.

The first step is to compute the set Λ of prefixes of minimal squares of period at most p. This set is stored inside a trie (also called prefix tree). It is efficient (in particular in terms of memory consumption) since the set Λ is prefixed closed (i.e. Λ contains any prefix of any word from Λ). Each word of Λ is given a unique integer as an identifier. In a second step, we compute the directed multi-graph G over the vertices {0, . . . , |Λ| -1} and such that there is an arc from i to j, if Λ(ua) is the word corresponding to j where u is the word corresponding to i and a is any letter. More precisely, if u is the word associated with the integer i and v is the word associated with j then the multiplicity of the number of arcs from i to j in our graph is given by |{a ∈ A : u = Λ(va)}|. There are not many arcs with multiplicity larger than 1, but because of the normalization, this may happen (for instance, there are three arcs from the vertex of the word 0 to the vertex of the word 01, since 01 is the normalization of 02 and 03 and similarly there are four arcs from the empty word to the word 0). This graph is useful to efficiently compute for any v ∈ Λ, the quantity min

l⊆A |l|=3 a∈l va∈S ≤p f ree C Λ(va) .
It is simply the sum of the weights of its out-neighbors minus the weight of the one of largest weight2 .

We considere the procedure that takes coefficients (C w ) w∈Λ as input and produces the coefficients (C ′ w ) w∈Λ such that for each v ∈ Λ

C ′ v = min l⊆A |l|=3 a∈l va∈S ≤p f ree C Λ(va) .
For every w, we call the quantity C ′ w /C w the growth associated to w. If we let α be the minimum of the growth over every w ∈ Λ then α and the set of coefficients C w respect the condition of equation 6. Our goal is then simply to find coefficients (C w ) w∈Λ that gives the largest value of α.

To find, our coefficient we simply start by setting all the C w to the same value (100000 in our implementation), and then we iterate our Between two iterations we renormalize the coefficients by dividing every coefficient by the same constant to keep the average value at some fixed value (100000 in our implementation). After 50 iterations, we find coefficients (C w ) w∈Λ and α = 13948/10721 ≈ 1.301 such that the conditions of the Lemma are verified.

We suspect that there are good reasons for which this procedure seems to converge toward the optimal. However, it is enough that we verified that after 50 iterations this deterministic procedure produces coefficients (C w ) w∈Λ with the desired property.

Let us finally mention that, every computation is carried out using integers (or pairs of integers for rational numbers) so that there are no issues of precision. It is important, since with α > 1.3 we can take p = 21 and β = 1.25 in Theorem 6, but with α = 1.295 there is no β that satisfy the condition of Theorem 5.

Conclusion

We showed something slightly stronger than Theorem 6. Indeed, our proof of Theorem 5 also holds if an adversary chooses each list only right before we chose the letter from the corresponding list (instead of fixing the lists from the start we have). Our proof of Theorem 3 also holds in this stronger setting. We suspect that the answer to Question 1 is positive in this stronger setting.

We showed that for any choice of lists of size 3 amongst {0, 1, 2, 3} the number of square-free word of length n is at least 1.25 n . By pushing the computation slightly further, we can replace 1.25 with 1.28. We suspect that the number of square-free words is minimal when all the lists are identical (the growth rate of the number of square-free word of length n is known to be approximatively 1.3017 [START_REF] Shur | Two-Sided Bounds for the Growth Rates of Power-Free Languages[END_REF]). This might even be true in the stronger context where an adversary chose the next list right after we chose the next letter. Note that, it is also really simple to use the same technique to improve the bounds of Theorem 3 by computing coefficients with the aid of a computer (although looking at suffixes of length 5 or 7 instead of 3 by hand is doable and would already improve the bounds).

Finally, let us conclude by mentioning that we believe that this approach could be used to answer positively Question 1. The size of the set Λ depends on the size of A. However, since we only consider normalized words for p = 21 the set Λ is the same for any A such that |A| ≥ 21. Let us provide a crude upper bound on the size of this set.

The number of square-free words of size n that use k (by that we mean that the k letters appear in the word) letters is less k × (k -1) n-1 (we forbid square of period 1). So the number of normalized words of size n that use k letters is less than k × (k -1) n-1 /k! = (k -1) n-2 /(k -2)!. The number of normalized minimal square of period n that use k letter is less than (k -1) n-2 /(k -2)! and the number of proper prefixes of length at least n of such words is then at most n × (k -1) n-2 /(k -2)!. By summing over n and k, the number of prefixes of minimal square-free words of period at most p over s letters is at most Evaluating this expression with p = 21 and s = 21 tells us that ,with |A| = 21, the set Λ has size at most 3.4 × 10 15 . This is less than 10 7 times larger than the set that required 70Go of RAM to be computed. Our bound being crude we suspect that Λ is in fact smaller than that (a more careful computation taking into account squares of period 2 divides this bounds by approximatively 4).

We might be able to solve this question with this approach in a few decades. It might also be possible to exploit some other symmetries of the problem to reduce the number of words considered. Let us finally mention that the base idea of the counting technique was recently used in more general context [START_REF] Rosenfeld | Another approach to non-repetitive colorings of graphs of bounded degree[END_REF][START_REF] Wanless | A general framework for hypergraph colouring[END_REF]. In particular, Wanless and Wood provided a general result based on a similar idea and applied it to graph colorings, hypergraph colorings and SAT-formula [START_REF] Wanless | A general framework for hypergraph colouring[END_REF]. It is not clear, how the more advanced argument used here (i.e., counting the total weights of the solutions instead of simply counting the number of solutions) can be used in a context more general than combinatorics on words or even whether it can be used in a framework similar to the one developed by Wanless and Wood.

  1) n-2 (k -2)!.

The C++ implementation can be found in the ancillary file on the arXiv. Running this program took approximately

hours of computation and occupied 76.4 Go of RAM.

A vertex u is said to be an out-neighbor of a vertex v if there is an arc from v to u.

* Supported by the ANR project CoCoGro (ANR-16-CE40-0005).


Golnaz Badkobeh
email: g.badkobeh@gold.ac.uk

Tero Harju
email: harju@utu.fi

Pascal Ochem
email: .ochem@lirmm.fr

Matthieu Rosenfeld
email: rosenfeld@lirmm.fr

Avoiding square-free words on free groups

We consider sets of factors that can be avoided in square-free words on two-generator free groups. The elements of the group are presented in terms of {0, 1, 2, 3} such that 0 and 2 (resp.,1 and 3) are inverses of each other so that 02, 20, 13 and 31 do not occur in a reduced word. A Dean word is a reduced word that does not contain occurrences of uu for any nonempty u. Dean showed in 1965 that there exist infinite square-free reduced words. We show that if w is a Dean word of length at least 59 then there are at most six reduced words of length 3 avoided by w. We construct an infinite Dean word avoiding six reduced words of length 3. We also construct infinite Dean words with low critical exponent and avoiding fewer reduced words of length 3. Finally, we show that the minimal frequency of a letter in a Dean word is 8 59 and the growth rate is close to 1.45818.

Introduction

Axel Thue [START_REF] Thue | Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen[END_REF] showed in 1912 that there exists an infinite square-free word m over the alphabet {0, 1, 2} that avoids occurrences of the words 010 and 212 of length 3. We shall consider a related question on the free group generated by two elements.

For the basic notions in combinatorics on words, we refer to Lothaire [START_REF] Lothaire | Combinatorics on Words[END_REF][START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF]. Let Σ k = {0, 1, . . . , k -1} be an alphabet of k letters. We denote by Σ * the set of all finite words over an alphabet Σ. We are interested solely in the words of Σ * 3 and Σ * 4 . The set of infinite words w : N → Σ over an alphabet Σ, represented here as infinite strings w(1)w(2) • • • , is denoted by Σ ω .

The length, i.e., the number of occurrences of letters, of a word w ∈ Σ * is denoted by |w|.

A factor v of w is right-special in w if there exist at least two distinct letters a and b such that va and vb both are factors of w.

A word w ∈ Σ * ∪ Σ ω is said to avoid another word v, if v is not a factor (i.e., a finite contiguous subword) of w. Furthermore, w is square-free if it avoids all nonempty words of the form vv. A morphism, i.e., a substitution of letters to words, h : Σ * → ∆ * is said to be square-free, if it preserves square-freeness, i.e., if h(w) is square-free for all square-free words w.

Example 1. The word w = 01210120210121021202101202120 of length 29 is, up to permutations of the letters, the longest ternary square-free word w ∈ Σ * 3 avoiding three square-free words of length 3. It avoids the words 010, 020, 201. There are infinite square-free ternary words that avoid two words of length 3; the Hall-Thue word m as defined below is an example of these.

The following result is due to Crochemore [START_REF] Crochemore | Sharp characterizations of squarefree morphisms[END_REF]. Theorem 1. A morphism α : Σ * 3 → ∆ * is square-free if and only if it preserves all square-free words of length 5.

The simplest square-free morphism is due to Thue [START_REF] Thue | Über unendliche Zeichenreihen[END_REF] ; see Lothaire [START_REF] Lothaire | Combinatorics on Words[END_REF],

h T (0) = 01201 , h T (1) = 020121 , h T (2) = 0212021 .

The Hall-Thue word m = τ ω (0), also known as a variation of Thue-Morse word [START_REF] Blanchet-Sadri | Abelian complexity of fixed point of morphism 0 → 012, 1 → 02, 2 → 1[END_REF], is obtained by iterating the (Hall) morphism [START_REF] Hall | Generators and relations in groups-The Burnside problem[END_REF]:

τ (0) = 012 , τ (1) = 02 , τ (2) = 1 .
Thus m = 0120210121 • • • The morphism τ is not square-free since τ (010) contains a square 2020. However, the Hall-Thue word m is square-free as was shown by Thue [START_REF] Thue | Über unendliche Zeichenreihen[END_REF] in 1906. The word m avoids the words 010 and 212 as is immediate from the form of τ .

Dean words

While considering reduced words of a free group on two generators, we work on the alphabet Σ 4 by considering 0 and 2 (resp. 1 and 3) as inverses of each other. Dean [START_REF] Dean | A sequence without repeats on x, x -1 , y, y -1[END_REF] proved in 1965 the existence of an infinite square-free reduced word.

Theorem 2. There exists an infinite Dean word.

We give here three simple proofs.

First Proof. As noticed by Baker, McNulty and Taylor [START_REF] Baker | Growth problems for avoidable words[END_REF], the construction of Dean [START_REF] Dean | A sequence without repeats on x, x -1 , y, y -1[END_REF] corresponds to the fixed point

f ω (0) = 01210321012303210121032301230321 • • • of the simple morphism f : Σ * 4 → Σ * 4 defined by f (0) = 01 , f (1) = 21 , f (2) = 03 , f (3) = 23 . (1)
Clearly, the iterated word f ω (0) is reduced. Its square-freeness can also be checked with the Walnut software [START_REF] Mousavi | Walnut software[END_REF], as communicated to us by Jeffrey Shallit [START_REF] Shallit | [END_REF]:

eval dean1 "Ei,n (n>=1) & At (t<n) => DE[i+t]=DE[i+n+t]"
Interestingly, f ω (0) is a complete shuffle of (02) ω and the paper folding sequence 1131133111331331 • • • (after renaming 0 to 3); see Davis and Knuth [START_REF] Davis | Number representations and dragon curves -I[END_REF] or Allouche and Shallit [START_REF] Allouche | Automatic Sequences. Theory, applications, generalizations[END_REF]. The latter claim was also verified by Shallit using Walnut, or by considering the substitution rules for the paper folding sequence: 11 → 1101 , 01 → 1001 , 10 → 1100 , 00 → 1000 .

We can modify (1) by combining the values f (1) and f (2) to obtain h : Σ * 3 → Σ * 4 from the three letter alphabet:

h(0) = 01 , h(1) = 23 , h(2) = 2103 .
The morphism h is not square-free, since h(212) = 210(3232)103 contains a square. However, we can check by Theorem 10 that h(m) is square-free.

Second Proof. Consider the morphism h : Σ * 3 → Σ * 4 given by the images of the letters, h(0) = 10 , h(1) = 32 , h(2) = 1230103012 .

It is not difficult to show directly that h is square-free, but Theorem 1 does it also quickly. Since the words h(ab), for different a, b ∈ Σ 3 , are reduced, the infinite word h(m) is a Dean word.

Third Proof. Let w ∈ Σ ω 3 be an infinite (ternary) square-free word. We construct a word w ∈ Σ ω 4 by adding the letter 3 in the middle of every occurrence of 02 and 20. Then also w is square-free. Indeed, if there were a square uu in w, the occurrences of 3 would be aligned (in the same positions) in the two instances of u, and deleting the occurrences of 3 would evoke a square uu into w; a contradiction. Clearly, w is reduced by its construction.

A morphism h : Σ * 3 → Σ * 4 that preserves Dean words, is called a Dean morphism. For h to be a Dean morphism, it suffices to check that h(w) is square-free for all square-free w of length 5 (Theorem 1) and checking that the words h(ab), for different a, b ∈ Σ 3 , are reduced.

One can apply the third proof of Theorem 2 to finite words. Then applying this operation to the Thue morphism h T , the images of which start with the letter 0, and end with 1, yields the following Dean morphism

h T (0) = 012301 , h T (1) = 03230121 , h T (2) = 0321230321 .
The reverse operation does not work; deleting the occurrences of 3 from a Dean word does not necessarily give a square-free ternary word.

Sets of avoided words

An avoided word is also called an absent word. Moreover, v is a minimal absent word of w if it is absent in w and all its proper prefixes and suffixes occur in w.

For a Dean word w ∈ Σ * 4 ∪ Σ ω 4 , let D l (w) denote the set of minimal absent words of length l of w and d l (w) = |D l (w)| (the size of D l (w)).

We are interested in the avoided (absent) words of length 3.

With the aid of a computer program, we find that the longest Dean word that avoids the word w = 10 of length 2 has length 58: 3230123032301232123032301230321230123212303230123212301232 By considering the permutations of Σ 4 that preserve reduced words, we have Lemma 3. Let w be a Dean word with |w| 59. Then d 2 (w) = 0.

We have already seen, by the third proof of Theorem 2, that every ternary square-free word w ∈ Σ * 3 gives rise to a Dean word w ∈ Σ * 4 . There are 15504 Dean words of length 20 divided into 709 different sets of avoided words including the empty set. Though up to the eight permutations of the letters that preserve reduced words (see the Appendix), there are 'just' 1938 Dean words of length 20.

The word w = 01030121012321230323 of length 20 is an example of a Dean word that accommodates all reduced words of length 3, i.e., d 3 (w) = 0. The length 20 is optimal: a Dean word of length 19 always avoids some word of length 3. Note that w is not 'de Bruijn -type' since both 012 and 123 occur twice in w. The following two simple lemmas deal with repetitions of the form abvab for a pair ab. They are verified by the aid of a computer. Up to permutations, the words 010321230 and 012303210 are the maximum length Dean words without repetitions of pairs.

Lemma 4. A Dean word that has no repetitions of pairs, has length at most 9.

A reduced word, w is extendable if there is at least a letter a ∈ Σ 4 , such that wa is a reduced word, wa ia called the extension of w. Clearly, any reduced word has two extentions. Proof. By the hypothesis, each of the eight reduced pairs ab has at least one extension in w. Hence d 3 (w) 8.

Suppose that d 3 (w) = 8. Then no reduced pair ab is a right-special factor in w. However, by Lemma 4, each Dean word of length 10 has a repetition of some pair abzab. By the uniqueness of the extensions, this would eventually result in a square abz•abz in the prefix of w of length 16.

The case d 3 (w) = 7 allows that exactly one pair is a right-special factor in w, and the other seven pairs are not right-special. By Lemma 5, |w| 23, and the claim follows.

The bound 24 in Lemma 6 is optimal as witnessed by Example 3. As expected, the family of the sets S i in Theorem 8 is closed under permutations that preserve reduced words. E.g., the third set S 3 can be obtained from S 1 by the permutation (0 1)(2 3), and (1 3) fixes S 1 . Moreover, each S i is closed under reversals of their elements. Remark 9. For the length 58, there are still 12 different sets of cardinality six of avoided words. The drop in the number between the lengths 58 to 59 is dramatic due to the fact that there are no longer any avoided words of length 2.

The next proof relies on a strong result due to Currie [START_REF] Currie | Finite test sets for morphisms that are squarefree on some of Thue's squarefree ternary words[END_REF].

Theorem 10. Let h : Σ * 3 → ∆ * be a morphism, and let w ∈ Σ ω 3 be an infinite word with {010, 212} ⊆ D 3 (w). Then h(w) is square-free if and only if h preserves square-freeness of the factors of w of length 7. Remark 14. The set S 1 is closed under the permutation (1 3), and thus the morphism g ′ , where 1 and 3 are interchanged, also satisfies Theorem 13. Also, besides permuting with (1 3), we can conjugate the images with respect to a common prefix: if g(a) = uv a , for all a ∈ Σ 3 then also g ′′ with g ′′ (a) = v a u satisfies Theorem 13 with only slight changes. We notice that the morphism g R where the images g(a) are reversed in order, is obtained from g by conjugation and the permutation (1 3).

Critical exponent VS number of factors of length 3

Theorem 12 exhibits a Dean word with critical exponent 2 that avoids 6 factors of length 3. In this section, we complement this result by considering the trade-off between the critical exponent of an infinite Dean word and the number of avoided factors of length 3. Negative results are obtained by standard backtracking. Positive results are proved by uniform morphisms that generate infinite Dean words with suitable properties using the method described in [START_REF] Ochem | A generator of morphisms for infinite words[END_REF].

Lemma 15. Let w be a 5 3 -free Dean word, then |w| < 62. The image of any

Letter frequencies

Theorem 29. The minimum frequency of a letter in an infinite Dean word is 8 59 . The image of every Dean word by the morphism f below is a Dean word such that the frequency of the letter 3 is 8 59 .

f (0) = 010 f (1) = 30121012321012103012101230121032101210 30121012321012103210123012101232101210 301210123012103210121030121012321012103 f (2) = 212 f (3) = 32101210301210123210121032101230121012
32101210301210123012103210121030121012 321012103210123012101232101210301210123 It is easy to see that the f -image of a Dean word is reduced. Let us check that it is also square free. A computer check rules out squares of period at most 500. Notice that |f (0)| = |f (2)| = 3 and |f (1)| = |f (3)| = 115. Moreover, the factor 010 (resp. 212) only appears as the f -image of 0 (resp. 2). So the period of a potential square in the f -image of a Dean word must be a multiple of |f (01)| = 118. Since the longest common prefix (resp. suffix) of f (1) and f (3) has length 1, our square implies the existence of a square with the same period and that contains the f -image of a letter as a prefix. This forces a square in the pre-image by f , which is a contradiction.

A computer check shows that every Dean word of length 118 and containing only 15 occurrences of the letter 3 is not extendable. Thus 8 59 is an optimal bound.

Growth rate

Let T n be the set of Dean words of length n. We use the same technique as in [START_REF] Rosenfeld | Avoiding squares over words with lists of size three amongst four symbols[END_REF] (which is really close to the technique introduced in [START_REF] Arseny | Two-sided bounds for the growth rates of power-free languages[END_REF] that was itself inspired by [START_REF] Kolpakov | On the number of repetition-free words[END_REF]) to show the following.

Theorem 30. For all n,

|T n | 1.4581846 n .
Let p = 36 and let F p be the set of reduced words that contain no squares of period at most p. Let Λ be the set of reduced words that are prefixes of minimal squares of period at most p. For any w, we let Λ(w) be the longest word from Λ that is a suffix of w. For any set of words S, and any w ∈ Λ, we let S (w) be the set of words from S whose longest prefix that belongs to Λ is w, that is

S (w) = {u ∈ S : Λ(u) = w}.
Lemma 31. There exist coefficients (C w ) w∈Λ such that C 0 > 0 and for all v ∈ Λ,

αC v a∈{0,1,2,3} va∈F p C Λ(va) (2)
where α = 33075185/22682414 ≈ 1.4581862847578.

The proof of this lemma relies on computer verifications. If one let M ∈ Z |Λ|×|Λ| be the matrix indexed over Λ such that for all u, v ∈ Λ,

M u,v = |{a ∈ {0, 1, 2, 3} : u = Λ(va)}| .
Then one can choose for the coefficients α the largest eigenvalue and for (C w ) w∈Λ any corresponding eigenvector. To find a vector close enough to this eigenvector, one can simply iterate the matrix (starting with the vector containing 1 everywhere) and renormalize the vector. One can then simply verify that the vector obtained after n iterations (say n = 100), has the desired property. We implemented this procedure in C++ 1 and it verifies Lemma 31 in less than 10 minutes and using 9GB of RAM on a laptop.

Notice, that this procedure to find the largest eigenvalue of a matrix converges quickly, so we know that α should be a really good approximation of this quantity. Since this matrix is the adjacency matrix of an automaton that recognizes reduced words without squares of period at most p, we deduce that there exists a constant C such that the number of such words of length n is as most C • 1.4581863 n . The same bound holds for |T n |, that is, for all n, |T n | < C • 1.4581863 n . We deduce that Theorem 30 is almost sharp.

For the rest of this section, let us fix coefficients (C w ) w∈Λ that respect the conditions given by Lemma 31. For each set S of words, we let

S = w∈Λ C w |S (w) | .
Whenever we mention the weight of a word w in informal definitions, we mean C Λ(w) . We are now ready to state our main Lemma.

Lemma 32. Let β > 1 be a real number such that

α - β 2-⌈ p+1 2 ⌉ β 2 -1 β .
Then for all n, T n+1 β T n .

Proof. We proceed by induction on n. Let n be an integer such that the lemma holds for any integer smaller than n and let us show that T n+1 β T n . By induction hypothesis, for all i,

T n β i T n-i (3)
A word of length n+1 is good, if its prefix of length n is in T n , if it is a reduced word and if it contains no square of period at most p. The set of good words is G. A word is wrong, if it is good, but contains a square of period larger than p. The set of wrong words is F . Then for any w, T n+1 = G \ F and

T n+1 G -F (4)
Let us first lower-bound G = w∈Λ |G(w)|C w .

The extensions of any word v ∈ S n that belongs to G are the words of the form va where a ∈ {0, 1, 2, 3} and such that va ∈ F p . By definition, Λ(v) is the longest suffix of v amongst prefixes of squares of period of length at most p. This implies that for any Dean word v and for any letter u, vu ∈ F p if and only if Λ(v)u ∈ F p . For the same reason, for any square-free word v and for any word u, Λ(vu) = Λ(Λ(v)u). We then deduce that the contribution of the extentions of any word

v ∈ T n to G is a∈{0,1,2,3} va∈F p C Λ(va) = a∈{0,1,2,3} Λ(v)a∈F p C Λ(Λ(v)a) a∈{0,1,2,3} Λ(v)a∈F p C Λ(Λ(v)a) .
By Lemma 31, we deduce that the contribution of the extentions of any word v ∈ T n to G is at least αC Λ(v) . We sum the contribution over

T n G v∈Tn αC Λ(v) = u∈Λ αC u |T (u) n | = α T n (5)
Let us now bound F . For all i, let F i be the set of words from F that end with a square of period i. Clearly, F = ∪ i 1 F i and

F i 1 F i . (6)
By definition of G and F , for every i p, |F i | = 0 and F i = 0. Moreover, since reduced words contain no square of odd period, for all i, |F 2i+1 | = 0 and F 2i+1 = 0.

Let us now upper-bound F i for any even i > p.

Let u ∈ F i be a word. For the sake of contradiction suppose, i Λ(u) and let v be the square of period i at the end of u and let k = |Λ(u)|. By hypothesis,

v 1 • • • v i = v i+1 • • • v 2i . There exists j p such that Λ(u) has period j, but since Λ(u) is the suffix of length k of v, v 2i+1-k • • • v 2i-j = v 2i+1+j-k • • • v 2i (
using that j p < i k one easily verifies that the indices are valid). So in particular, using the two previous equations together,

v j+1 • • • v i = v i+j+1 • • • v 2i = v i+1 • • • v 2i-j
(one easily verifies that all the indices are valid). So there is a square inside u which is not a suffix of u which is a contradiction, since by definition of F the only squares inside u are suffixes of u. Hence, i > Λ(u).

For any u ∈ F i , u ends with a square of period i so the last i letters are uniquely determined by the prefix v of length |u| -i. By definition, v ∈ T n+1-i . Moreover, by the previous paragraph the suffix of size |Λ(u)|+1 of u and v are the same which implies Λ(v) = Λ(u) and v ∈ T Together with (3) it yields, F i T n β 1-i .

We can now sum the F i to upper bound F using equation ( 6),

F i ⌈ p+1 2 ⌉ T n β 1-i = β 2-⌈ p+1 2 ⌉ β 2 -1 T n .
Using this bound and ( 5) with (4) yields

T n+1 T n α - β 2-⌈ p+1 2 ⌉ β 2 -1
.

By theorem hypothesis we deduce T n+1 β T n which concludes our proof.

One easily verifies that β = 1.4581846 satisfies the condtions of Lemma 32 and we deduce the following corollary.

Lemma 33. For all n, T n+1 1.4581846 T n .

It implies that for all n, T n 1.4581846 n-1 T 1 1.4581846 n-1 C 0 . There exists a constant C, such that |T n | C1.4581846 n . Using the fact that the set of Dean words is factorial, it is routine to deduce that for all n,

|T n | 1.4581846 n .
This proves Theorem 30.

Let us mention that, using the same technique, we were able to show that there exist at least 1.12 n 5 3 + -free Dean words of length n.

Problems

There are Dean words of length n 7 that do not occur in any infinite Dean words, i.e., they cannot be extended in any infinite Dean word (but a finite amount). One example of such a word is 0103010.

Due to minimality of D l (w), there is no obvious relation between d l (w) and d l+1 (w). If Problem 1 has a solution w then the (nonempty) sets D l (w) stabilise, i.e., for each l, there is a bound N l such that for any prefix v of w with |v| N l one has D l (v) = D l (w) (since always D l (w) ⊆ D l (v)). We conjecture that in such a case the integers d l (w) are very small.

As mentioned, there are Dean words that are non extendable. We formally define the set of extendable Dean worrds as following: Ω = {w | for all n, there is a Dean word u n wv n with |u n |, |v n | n}.

Example 2 .

 2 The Hall-Thue word m avoids 010 and 212. The corresponding Dean word m has D 3 (m) = {010, 030, 212, 232} simply since the letter 3 is never added between two 0's or two 2's.

Lemma 5 .Example 3 .Lemma 6 .

 536 Let w be a Dean word that has only one right-special factor of length 2. Then |w| 23. The word w = 01032301032123010323010 is a longest Dean word with only one right-special factor of length 2, v = 32. We have d 2 (w) = 0 and D 3 (w) = {012, 030, 101, 121, 210, 232, 303} of seven elements. A prefix v of w is proper if |v| < |w|. Let w be a Dean word of length |w| 24 such that every reduced pair occurs in a proper prefix of w. Then d 3 (w) 6.

Corollary 7 .

 7 If w is an infinite Dean word then d 3 (w) 6.By applying a computer search on all Dean words of length 59, we see that there are only four possible sets of avoided Dean words, as specified in Theorem 8. The claim of Theorem 8 for words |w| > 59 immediately follows from this result. We shall show in Theorem 12 that these sets are actual for infinite Dean words. Theorem 8. Let w be a Dean word of length |w| 59 with d 3 (w) = 6. Then D 3 (w) is one of the following sets S 1 = {101, 123, 212, 232, 303, 321} S 2 = {012, 030, 101, 121, 210, 232} S 3 = {010, 032, 212, 230, 303, 323} S 4 = {010, 030, 103, 121, 301, 323}

Lemma 16 . 3 +The image of any 7 5 + 5 3+Lemma 17 .Lemma 18 . 10 +

 16355171810 There exists an infinite5 -free Dean word avoiding 323. -free 4-ary word by the following 136-uniform morphism is a -free Dean word avoiding 323. Let w be a17 10 -free Dean word and d 3 (w) 2, then |w| < 289. There exists an infinite17 -free Dean word avoiding 030 and 232.

(

  Λ(u)) n+1-i . So for every w ∈ Λ, any word of F (w) i is uniquely determined by a word of T (w) n+1-i , which implies |F (w) i | |T (w) n+1-i |. By summing over all w ∈ Λ, F i T n+1-i .

Example 4 .Problem 1 .

 41 We have D 3 (g(m)) = S 1 for the morphism g of Theorem 12. However, d 4 (g(m)) = d 5 (g(m)) = d 6 (g(m)) = 0. Are there infinite Dean words w such that d l (w) > 0 for all l 3?

Table 1 :

 1 Thus a reduced word w ∈ Σ * 4 does not have factors from the set {02, 20, 13, 31}. In other words, the even and odd letters alternate in the reduced words.A reduced word w ∈ Σ * 4 is said to be a Dean word if it is square-free. Dean words are moderately numerous as suggested in Table1. The number of Dean words, i.e., square-free reduced words over Σ 4 .

	n	#	n	#	n	#	n	#	n	#
	1	4	2	8	3	16	4	24	5	40
	6	64	7	104	8	144	9	216	10	328
	11 496	12 720	13 1072 14 1584	15 2344
	16 3384 17 4952 18 7264 19 10632 20 15504

  Let w be a 5-directed Dean word, then |w| < 10.

	7 5 + -free Dean word avoiding 030 and 232. + -free 4-ary word by the following 358-uniform morphism 0 → 0103230121032123010321012303212301210323010321230 is a 17 10 3210123010321230121032301032101230321230121032123 0321012301032301210321230103210123032123010323012 0 → 010321012303210301210323010321230321 0 → 0103012101232123012101230103012321230323 030123210323012103212303210123210323 1 → 0103012101232123010301230323012321230323 1 → 010321012303210301210323010321230321 2 → 0103012101230323012321230121012321230323 012321032301210321230321030123210323 3 → 0103012101230103012303230121012321230323 2 → 010321012303210301210323010321012321 032301210321230321012321030121032123 Lemma 28.
		1032123032101230103212301210323010321230321012301 3 → 010321012303210301210323010321012321
		0323012103212301032101230321230121032123032101230 030121032123032101232103230121032123
		1032123012103230103210123010323012103212301032101
	2303212301032301210321230321012301032123012103230 Lemma 24. Let w be a 27 16 -free 11-directed Dean word, then |w| < 129.
	103210123032123 1 → 0103230121032123010321012303212301210323010321230 Lemma 25. There exists an infinite 27 16 + -free 10-directed Dean word.
	3210123010321230121032301032101230321230121032123 0321012301032301210321230103210123032123010323012 1032123032101230103212301210323010321012301032301 The image of any 7 + -free 4-ary word by the following 564-uniform morphism 5 is a 27 16 + -free Dean word that is 10-directed.
		2103212301032101230321230121032123032101230103212
	0 →	01032101230321030123210123032123010323012103012321012303210301232103230121032123010321 3012103230103212303210123010323012103212301032101 01230321230103230121030123210123032123010321012303210301232103230121030123210123032123
		01032301210321230103210123032103012321012303212301032301210301232103230121032123010321 2303212301032301210321230321012301032123012103230 01230321230103230121030123210123032123010321012303210301232103230121032123010323012103
		01232101230321230103230121032123010321012303210301232103230121030123210123032123010323 103210123032123 01210301232103230121032123010321012303212301032301210301232101230321030123210323012103
	212301032301210301232101230321230103230121032123 2 → 0103230121032123010321012303212301210323010321230 1 → 01032101230321030123210123032123010323012103012321012303210301232103230121032123010321
		01230321230103230121030123210123032123010321012303210301232103230121030123210123032123 3210123010321230121032301032101230103230121032123 01032301210321230103210123032103012321012303212301032301210301232103230121032123010321
		01230321230103230121030123210123032103012321032301210321230103230121030123210123032123 0103210123032123010323012103212303210123010321230 01032301210321230103210123032103012321032301210301232101230321230103230121030123210323
		01210321230103210123032123010323012103012321012303212301032101230321030123210323012103 1210323010321230321012301032301210321230103210123 212301032301210301232101230321230103230121032123
	2 →	01032101230321030123210123032123010323012103012321012303210301232103230121032123010321 0321230121032301032101230103230121032123032101230 01230321230103230121030123210123032123010321012303210301232103230121030123210123032123
		01032301210321230103210123032103012321012303212301032301210301232101230321030123210323 1032123012103230103210123032123010323012103212301 01210321230103230121030123210123032123010323012103212301032101230321030123210323012103
		01232101230321230103230121030123210323012103212301032101230321230103230121030123210123 0321012303212301210321230321012301032123012103230 03210301232103230121032123010323012103012321012303212301032101230321030123210323012103
	3 →	012321012303212301032301210301232103230121032123 103212303210123 01032101230321030123210123032123010323012103012321012303210301232103230121032123010321
	01230321230103230121030123210123032123010321012303210301232103230121030123210123032123 3 → 0103230121032123010321012303212301210323010321230 01032301210321230103210123032103012321012303212301032301210301232101230321030123210323
		01210321230103230121030123210123032123010321012303210301232103230121030123210123032123 3210123010321230121032301032101230103230121032123 01032301210301232103230121032123010321012303212301032301210301232101230321030123210323
		01210321230103230121030123210123032123010323012103212301032101230321030123210323012103 0103210123032123010323012103212303210123010321230 012321012303212301032301210301232103230121032123
		1210323010321230321012301032301210321230103210123
		0321230121032123032101230103212301210323010321012
	3032123010323012103212301032101230321230121032301 Lemma 26. Let w be a 7 4 -free 9-directed Dean word, then |w| < 114.
	0321012301032301210321230321012301032123012103230 103212303210123 Lemma 27. There exists an infinite 7 4 + -free 6-directed Dean word.
	Lemma 19. Let w be a 7 4 -free Dean word and d 3 (w) 3, then |w| < 68. Lemma 20. There exists an infinite 7 4 + -free Dean word avoiding 232, 212, 303, The image of any 7 + -free 4-ary word by the following 40-uniform morphism 5 is a 7
	and 323.

+ -free Dean word that is 6-directed.

The program can be dowloaded at https://www.lirmm.fr/~mrosenfeld/codes/Finding_the_coefficient_fo

We apply Theorem 10 to the Hall-Thue word m which does avoid the words 010 and 212.

Corollary 11. Let h : Σ * 3 → Σ * 4 be a non-erasing morphism. Then h(m) is squarefree if and only if h is square-free on the factors of m of length 7.

For the sake of completeness, the factors of length 7 of m are listed in the Appendix.

Theorem 12. There exists an infinite Dean word w ∈ Σ ω 4 such that D 3 (w) = S i , for each i = 1, 2, 3, 4.

Proof. We obtain a solution h(m) for the first set S 1 = {101, 123, 212, 232, 303, 321}; solutions for the other three sets are obtained by suitable permutations applied to the following morphism.

Let g : Σ * 3 → Σ * 4 be defined by

where the images have lengths 6, 4, 2, respectively. The morphism g is not squarefree since the image g(010) contains a square. However, a computer check can verify that g preserves square-freeness of the factors of m of length 7. Therefore, by Corollary 11, the word g(m) is square-free. Clearly, the images g(w) are reduced for all w ∈ Σ * 3 . By inspection, the words of S 1 are avoided by all words g(ab) with a = b. Since d 3 (g(m)) 6 by Corollary 7, it follows that D 3 (g(m)) = S 1 .

By the next theorem and the remark that follows, g is, in effect, the only morphism Σ * 3 → Σ * 4 that produces Dean words avoiding the words of S 1 .

Theorem 13. Let w be an infinite Dean word such that S 1 ⊆ D 3 (w). Then w = ug(v), where |u| 5, and v is a square-free ternary word.

Proof. Let w = x1z, where x has no occurrences of 1. (The word x can be empty.) By analysing the words without factors in S 1 , we conclude that 1 is preceded in w only by a suffix of g(0) = 103230, g(1) = 1030, or g(2) = 12. This gives the bound |x| |g(0)| -1 = 5 for the prefix x. We conclude that the suffix 1z has a decomposition in terms of g(a), a ∈ Σ 3 . This means that w = ug(v), where v is square-free since w is.

The image of any

Critical exponent VS directedness

A word u is d-directed if for every factor f of u of length d, the reverse of f , denoted by f R , is not a factor of u. In this section, we consider the trade-off between the critical exponent of an infinite Dean word and the smallest d such that it is d-directed. We use the same techniques as in the previous section for positive and negative results. In order to verify that a word is d-directed, we only have to check for occurrences of factors of length d and their reverse. A solution word for Problem 3 would contain all words in Ω. Clearly, if m j (w) = 0 then also m k (w) = 0 for all k < j.