1 Introduction and preliminaries↩︎

Let us recall some basic notions of Combinatorics of words we will use in this paper.

1.1 Words↩︎

In the following, \(A\) and \(B\) are alphabets, that is, finite sets of symbols called letters. Since an alphabet with one element is of limited interest to us, we always assume that the cardinality of alphabets is at least two.

A word is an element in \(A^*\), the free monoid generated by \(A\), whose identity element is the empty word, denoted \(\varepsilon\), and whose composition law, usually unnoted, is simply the juxtaposition of symbols. We denote by \(A^+\) the set of non-empty words, that is, \(A^+=A^* \setminus \{\varepsilon\}\). We also speak of product of words, just as we speak of juxtaposition of words. We will not always specify the alphabet used, as this will often be irrelevant.

Given a non-empty word \(u = a_1\ldots a_n\), with \(a_i \in A\) for every integer \(i\) from 1 to \(n\), the length of \(u\) denoted by \(|u|\) is the integer \(n\), that is, the number of letters of \(u\). By convention, we have \(|\varepsilon| = 0\). The mirror image of \(u\), denoted by \(\tilde{u}\), is the word \(a_{n} \ldots a_{2}a_{1}\).

A word \(u\) is a factor of a word \(v\) if there exist two (possibly empty) words \(p\) and \(s\) such that \(v = p u s\). We denote by \({\rm Fcts}(v)\) the set of all factors of \(v\). If \(u\in{\rm Fcts}(v)\), we also say that \(v\) contains the word \(u\) (as a factor). If \(p = \varepsilon\), \(u\) is a prefix of \(v\). If \(s = \varepsilon\), \(u\) is a suffix of \(v\). If \(u \neq v\), \(u\) is a proper factor of \(v\). If \(u\), \(p\), and \(s\) are non-empty words, \(u\) is an internal factor of \(v\).

Two non-empty words \(u\) and \(v\) are conjugated if \(u=t_1t_2\) and \(v=t_2t_1\) for two (possibly empty) words \(t_1\) and \(t_2\). If \(t_1 \neq \varepsilon\) and \(t_2 \neq \varepsilon\), we say that \(v\) is a proper conjugated word of \(u\).

Let \(w\) be a non-empty word and let \(i, j\) be two integers such that \(0 \leq i-1 \leq j \leq |w|\). We denote by \(w{[i..j]}\) the factor of \(w\) such that \(|w{[i..j]}|=j-i+1\) and \(w = p w{[i..j]} s\) for two words \(s\) and \(p\) satisfying \(|p| = i-1\). Note that, when \(j = i - 1\), we have \(w{[i..j]} = \varepsilon\). When \(i=j\), we also denote by \(w{[i]}\) the factor \(w{[i..i]}\), which is the \(i^{\rm th}\) letter of \(w\). In particular, \(w{[1]}\) and \(w{[|w|]}\) are respectively the first and the last letter of \(w\).

An overlap is a word of the form \(xuxux\) where \(x \in A\) and \(u\in A^*\). Note that an equivalent definition is obtained by taking \(x \in A^+\). An overlap-free word is a word in which none of the factors are an overlap.

An overlap is said to be pure if all its proper factors are overlap-free. Let us remark that, if \(avava\) is a pure overlap, then \(a\in A\).

Repeating the reasoning that an overlap is either pure or contains an overlap, we obtain that a word that contains an overlap also contains a pure overlap (as a factor of the first).

Powers of a word are defined inductively by \(u^0 = \varepsilon\), and for every integer \(n \geq 1\), \(u^n = u u^{n-1}\). Given an integer \(k \geq 2\), since the case \(\varepsilon^k\) is of little interest, we call a \(k\)-power any word \(u^k\) with \(u\neq \varepsilon\). A \(2\)-power (resp. a \(3\)-power) is also called a square (resp. a cube). Given an integer \(k \geq 2\), a word is \(k\)-power-free if it does not contain any \(k\)-power as factor. A primitive word is a word that is not a \(k\)-power of another word whatever the integer \(k \geq 2\). A (non-empty) \(k\)-power \(v^k\) is called pure if any proper factor of \(v^k\) is \(k\)-power-free. In particular, we say that \(v^k\) is a pure \(k\)-power of a word \(w\) if \(v^k\in{\rm Fcts}(w)\) and \(v^k\) is pure. As for pure overlap, repeating the fact that a non-pure \(k\)-power contains a \(k\)-power, which is itself pure or not, we obtain that any \(k\)-power contains a pure \(k\)-power. Moreover, if \(v^k\) is a pure \(k\)-power then \(v\) is primitive but the converse does not hold.

The following proposition gives the well-known solutions (see [1]) to two elementary equations on words and will be widely used in the following sections:

We also need a property on words that is an immediate consequence of Proposition 6([Lotcase2]).

We also use a well-known result on combinatorics on words:

As a consequence of Proposition 9, we get:

Let us assume that \(au=v_1v_2\) and \(bv=v_2v_1\) for two words \(v_1\) and \(v_2\) in \(A^*\). And, by contradiction, let us assume that \(bvbvb\) is not a pure overlap, that is, \(v_2v_1v_2v_1b=T_1 \, ctctc \, T_2\) for some letter \(c\) and some words \(t\), \(T_1\) and \(T_2\) with \(T_1T_2 \neq \varepsilon\). It means that \(au \neq bv\) and so \(v_1,v_2 \neq \varepsilon\). Therefore, \(a\) is the first letter of \(v_1\) and \(b\) is the first letter of \(v_2\).

If \(|T_1| \geq |v_2|\) then \(ctctc\) is a factor of \(v_1v_2v_1b\), that is, of \(auau\): a contradiction with the hypotheses. In a same way, if \(|T_2| \geq |v_1|\) then \(ctctc\) is a factor of \(v_2v_1v_2a\): a contradiction.

From now, we assume that \(|T_1| < |v_2|\) and \(|T_2| <|v_1|\).

From the equality \(v_2v_1v_2v_1b=T_1 \, ctctc \, T_2\) with \(T_1T_2 \neq \varepsilon\), we get that \(|ct|< |v_2v_1|\).

If \(T_2 = \varepsilon\) then \(T_1 \neq \varepsilon\), \(c=b\), and there exists a non-empty word \(X\) such that \(v_2=T_1X\) and \(ctct=Xv_1 \, T_1Xv_1\). It implies that there exists two non-empty words \(t_1\) and \(t_2\) of the same length such that \(T_1=t_1t_2\), \(ct=(Xv_1)t_1=t_2(Xv_1)\). From Case [Lotcase1] of the proposition 6, there exist two words \(r\) et \(s\) and an integer \(n\) such that \(t_2=rs\), \(Xv_1=r(sr)^n\) and \(t_1=sr\). If \(r \neq \varepsilon\) then \(r\) (prefix of \(Xv_1)\) starts with \(c (=b)\). And \(v_2v_1=t_1t_2Xv_1\), factor of \(auau\), contains \(rrsr\) where \(sr=t_1\) (prefix of \(v_2\)) also starts with \(c\). That is, \(rrsr\) contains an overlap: a contradiction. If \(r = \varepsilon\) then \(Xv_1=s^n(\neq \varepsilon)\) and \(t_1=t_2=s\). It follows that \(v_2v_1=t_1t_2Xv_1\), again, factor of \(auau\), contains \(s^3\): a contradiction.

If \(T_1 = \varepsilon\), in the same way as in the case \(T_2 = \varepsilon\), and using mirror image, we obtain a contradiction with the hypotheses.

If \(T_1 \neq \varepsilon\) and \(T_2 \neq \varepsilon\), let \(T_2'\) be the word such that \(T_2=T_2'b\). There exist two non-empty words \(X\) and \(Y\) such that \(v_1=YT_2'\), \(v_2=T_1X\) and \(ctctc=Xv_1 \, v_2Y=XYT_2'\, T_1XY\). Since \(|ct| \leq |XY|\), let \(u_1\) and \(u_2\) be the words of the same length such that \(T_2' T_1=u_1cu_2\), \(ct=XYu_1\) and \(tc=u_2XY\). Since \(ctc=(cu_2)(XY)=(XY)(u_1c)\), from Case [Lotcase1] of Proposition 6, there exist two words \(r\) et \(s\) and an integer \(n\) such that \(cu_2=rs\), \(XY=r(sr)^n\) and \(u_1c=sr\). If \(|r| = 0\), then \(s=u_1c=cu_2\) and \(XY=s^n\) with \(n \geq 1\). One of the words \(T_1ctc(=T_1s^{n+1})\) or \(ctcT_2'(=s^{n+1}T_2')\) is factor of \(v_2v_1\) that is of \((au)^2\). But the last letter of \(T_1\) is the last letter of \(cu_2\) that is of \(s\) and the first letter of \(T_2'\) is the first letter of \(u_1c\) that is of \(s\). It means that \(auau=(v_1v_2)^2\) contains an overlap: a contradiction. If \(|r| = 1\), then \(r=c\) and \(s=u_1=u_2\). Since \(X\) and \(Y\) are non-empty, \(Y\) ends with \(c\) and \(X\) starts with \(c\). It implies that \(v_1v_2=YT_2'T_1X\), factor of \(au\) contains \(cscsc\): a contradiction. If \(|r| \geq 2\), there exists a word \(r'\) such that \(r=cr'c\). Therefore, \(u_1cu_2\) factor of \(v_2v_1\) contains \(cr'cr'c\): a final contradiction.     \(\fbox{}\)

The result is obvious when \(k=3\). By contradiction, assume that \((au)^{k-1}\) contains a \(k\)-power \(v^k\) with \(k \geq 4\). In particular, we have \(0<|v|<|au|\).

If \(|v^{k-1}| <|au|\) and, in particular, \(|v^{3}| <|au|\), then there exist a conjugated word of \(au\) (so a factor of \(auau\)) that contains \(v^{3}\): a contradiction with the fact that \(auaua\) is pure.

If \(|v^k| \geq |v| +|au|\), then, by Lemma 10 and Remark 1, the word \(au\) is not primitive. This means that \(auau\) contains a cube: a contradiction with the fact that \(auaua\) is pure.     \(\fbox{}\)

1.2 Morphisms↩︎

A morphism \(f\) from \(A^*\) to \(B^*\) is a mapping from \(A^*\) to \(B^*\) such that \(f(uv) = f(u)f(v)\) for all words \(u, v\) in \(A^*\). When \(B\) has no importance, we say that \(f\) is a morphism on \(A^*\) or that \(f\) is defined on \(A^*\). Note that a morphism on \(A^*\) is entirely determined by the images of the letters of \(A\).

Given a set \(X\) of words over \(A\), and given a morphism \(f\) on \(A^*\), we denote by \(f(X)\) the set \(\{f(w) \mid w \in X\}\).

Given an integer \(L\), \(f\) is \(L\)-uniform if \(|f(a)| = L\) for every letter \(a\) in \(A\). A morphism \(f\) is uniform if it is \(L\)-uniform for some integer \(L \geq 0\).

A morphism \(f\) on \(A^*\) is overlap-free if the image of any overlap-free word by \(f\) is also overlap-free. In other words, an overlap-free morphism is a morphism that preserves overlap-free words. For instance, the empty morphism \(\epsilon\) (\(\forall a \in A\), \(\epsilon(a) = \varepsilon\)) or the identity endomorphism \(Id\) (\(\forall a \in A\), \(Id(a) = a\)) are overlap-free.

A morphism \(f\) on \(A^*\) is \(k\)-power-free (\(k \geq 2\)) if \(f(w)\) is \(k\)-power-free for every \(k\)-power-free word \(w\) in \(A^+\).

We say that a morphism is non-erasing if, for all letters \(a \in A\), \(f(a) \neq \varepsilon\). The empty morphism \(\epsilon\) is the only morphism that is both erasing and overlap-free or \(k\)-power-free (\(k \geq 2\)). Indeed, for any erasing morphism \(f \neq \epsilon\) defined on \(A^*\), there exist two different letters \(a\) and \(b\) in \(A\) (remember \({{\rm Card(}A{\rm)}} \geq 2\)) such that \(f(a) \neq \varepsilon\), \(f(b) = \varepsilon\), and so \(f(aba^{k-1})\) contains a \(k\)-power and especially an overlap when \(k=3\) with \(aba^{k-1}\) \(k\)-power-free and \(abaa\) overlap-free. From now, since the case \(f=\epsilon\) is of little interest, we always assume that \(f \neq \epsilon\).

A morphism on \(A^*\) is called prefix (resp. suffix) if, for all different letters \(a\) and \(b\) in \(A\), the word \(f(a)\) is not a prefix (resp. not a suffix) of \(f(b)\). A prefix (resp. suffix) morphism is non-erasing. A morphism is bifix if it is prefix and suffix.

A non-erasing morphism on \(A^*\) is called strongly prefix (resp. strongly suffix) if, for all different letters \(a\) and \(b\) in \(A\), the words \(f(a)\) and \(f(b)\) do not start (resp. do not end) with the same letter. A morphism is strongly bifix if it is strongly prefix and strongly suffix.

Let \(f\) be a morphism from \(A^*\) to \(B^*\) and, by contraposition, suppose that \(f\) is not a strongly bifix.

If \(f\) is not strongly prefix, let \(a\) and \(b\) be two different letters in \(A\) such that \(f(a)\) and \(f(b)\) starts with the same letter \(x\). Let \(\alpha\) and \(\beta\) be the words such that \(f(a)=x\alpha\) and \(f(b)=x\beta\). The image of the overlap-free word \(aab\) by \(f\) contains the overlap \(x\alpha x\alpha x\): \(f\) is not overlap-free.

If \(f\) is not strongly suffix, on the same way, we get that the image of a word of the form \(baa\) contains an overlap.     \(\fbox{}\)

Given a morphism \(f\) on \(A\), the mirror morphism \(\tilde{f}\) of \(f\) is defined for all words \(w\) in \(A^+\), by \(\tilde{f}(w)=\widetilde{f(\tilde{w})}\). In particular, \(\tilde{f}(a)=\widetilde{f(a)}\) for every letter \(a\) in \(A\).

Let us recall that a word \(w\) is overlap-free (resp. \(k\)-power-free) if and only if \(\tilde{w}\) is overlap-free (resp. \(k\)-power-free). As a direct consequence, a morphism \(f\) is overlap-free (resp. \(k\)-power-free) if and only if \(\tilde{f}\) is overlap-free (resp. \(k\)-power-free).

Proofs of the three following lemmas are left to the reader.

Let \(f\) be a morphism from \(A^*\) to \(B^*\) and, by contraposition, suppose that \(f\) is not a ps-morphism.

Let \(a\), \(b\), and \(c\) be letters of \(A\) with \(b \neq a\) and \(c \neq a\) such that \(f(a) = ps\), \(f(b) = ps'\), and \(f(c) = p's\) for some words \(p\), \(p'\), \(s\), and \(s'\).

If \(p \neq \varepsilon\), then \(f(aab)\) contains \(pspsp\). If \(s \neq \varepsilon\), then \(f(caa)\) contains \(spsps\). In these both cases, we get that \(f\) is not an overlap-free morphism.

If \(f(a) = \varepsilon\), since \(f \neq \epsilon\), let \(d\) be a letter of \(A\) such that \(f(d) \neq \varepsilon\). Therefore, we get that \(f(dadaad) = f(d)^3\), meaning that \(f\) is not overlap-free.     \(\fbox{}\)

Let us assume that \(f(\overline{w})=pu^ks\) for a factor \(\overline{w}\) of a word \(w\), a non-empty word \(u\) and an integer \(k \geq 2\), Let us also assume that \(\overline{w}\) contains a factor \(w_0\) such that \(|f(w_0)|=|u|\). If \(f\) is a ps-morphism, Lemma 10 states that \(\overline{w}\) necessarily contains a \(k\)-power \(w'^k\) such that \(f(w')\) is a conjugated word of \(u\). We will say that \(f(w)\) contains a synchronised \(k\)-power \(u^k\) or that \(f(w)\) and \(u^k\) are synchronised. More precisely:

Let \(a\) be the letter and let \(u\) be the word such that \(f(w)\) and \(auaua\) are synchronised, let \(\overline{w}\) be the shortest factor of \(w\) whose image by \(f\) contains \(auaua\), and let \(w_0\) be a factor of \(\overline{w}\) such that \(|f(w_0)|=|au|\).

There exist a prefix \(p\) of \(f(\overline{w}{[1]})\) and a suffix \(s\) of \(f(\overline{w}{[|\overline{w}|]})\) such that \(f(\overline{w})=pauauas\) with \(|p| < |f(\overline{w}{[1]}|\) and \(|s| < |f(\overline{w}{[|\overline{w}|]}|\). Let \(w_1\) and \(w_2\) be the words such that \(w=w_1w_0w_2\).

If \(w_1=\varepsilon\), i.e., \(\overline{w}\) starts with \(w_0\), then \(p=\varepsilon\) and \(f(\overline{w})\) starts with \(au\). It implies that \(au=f(w_0)\). By Lemma 5, it follows that \(\overline{w}\) starts with \(w_0^2\). Let \(x\) be the first letter of \(w_0\). Let \(w_0'\) and \(w'\) be the words such that \(w_0=xw_0'\) and \(w=xw_0'xw_0'w'\). Since \(f(w')\) starts with \(a\) and since \(f\) is strongly bifix, we get that \(w'\) starts with \(x\) (see Remark 12) and that \(w\) starts with the overlap \(xw_0'xw_0'x\).

If \(w_2=\varepsilon\), i.e., \(\overline{w}\) ends with \(w_0\), then, in a similar way, we obtain that \(\overline{w}\) ends with \(yw_0''yw_0''y\) where \(y\) is the last letter of \(w_0\) and \(w_0''\) is the word such that \(w_0=w_0''y\).

From now, let us assume that \(w_1\) and \(w_2\) are non-empty, i.e., \(w_0\) is an internal factor of \(\overline{w}\). Since \(|pa| \leq |f(w_1{[1]}|\), \(|as| \leq |f(w_2{[|w_2|]}|\), it implies that \(f(w_0)\) is an internal factor of \(uau\). In particular, since \(f(w_0)=|au|\), it means that \(f(w_0)\) and \(au\) are conjugated words. More precisely, there exist four words \(u_1\), \(u_2\), \(u_3\) and \(u_4\) such that \(f(w_1)=pau_1\), \(f(w_2)=u_4as\), \(f(w_0)=u_2au_3\) with \(u=u_1u_2=u_3u_4\).

Since \(|f(w_0)|=|u_2au_3|=|au|=|au_1u_2|\), we get that \(u_1=u_3\) and \(u_2=u_4\), that is, \(f(w_1)=pau_1\), \(f(w_2)=u_2as\) and \(f(w_0)=u_2au_1\).

Let \(t\) be the greatest common suffix of \(w_0\) and \(w_1\). Since \(f\) is strongly bifix, we have \(|f(t)| \geq |au_1|\). Since \(|p| \leq |f(w_1{[1]}|\), by Lemma 7, we get that \(w_1=t\) is a suffix of \(w_0\). In particular, \(u_2\) ends with \(p\). There exist a word \(w_0'\) and a word \(u_2'\) such that \(w_0=w_0'w_1\), \(u_2=u_2'p\) and \(f(w_0')=u_2'\).

Since \(f(w_2)=u_2as=f(w_0')pas\) avec \(|pa| \leq |f(w_1{[1]}|\) and \(|as| \leq |f(w_2{[|w_2|]}|\) and since \(f\) is strongly bifix, we get that there exist a letter \(x\) such that \(f(x)=pas\) (see Remark 12). By Lemma 6, it implies that \(w_2=w_0'x\). It also means that \(w_1\) starts with \(x\). So there exist a word \(w_1'\) such that \(w_1=xw_1'\). It follows that \(\overline{w}=xw_1'w_0'xw_1'w_0'x\) is an overlap with \(|f(xw_1'w_0')|=|f(w_1w_0')|=|au|\).     \(\fbox{}\)

2 Reduction of a power↩︎

2.1 About overlap-free morphisms↩︎

Since \(f\) is a ps-morphism, we have \(f\) non-erasing and injective.

If \(T\) is an overlap-free word, then \(f\) is not overlap-free, and the proof is complete in this case. So, we assume that \(T = T_1bvbvbT_2\) where \(b \in A\), \(v, T_1, T_2 \in A^*\), with the additional condition that \(bvbvb\) is a pure overlap.

Therefore, we have \(f(T_1)f(b)f(v)f(b)f(v)f(b)f(T_2) = \pi_1f(a)f(u)f(a)f(u)f(a)\sigma_2\).

Let \(\alpha_1\) be the first letter of \(f(a)\) and \(\alpha_2\) be the last letter of \(f(a)\). Let \(A_1\) and \(A_2\) be the words in \(B^*\) such that \(f(a)=\alpha_1A_1=A_2\alpha_2\).

Let \(\beta_1\) be the first letter of \(f(b)\) and \(\beta_2\) be the last letter of \(f(b)\). Let \(B_1\) and \(B_2\) be the words in \(B^*\) such that \(f(b)=\beta_1B_1=B_2\beta_2\).

Step : If \(T\) starts with an overlap \(bvbvb\) such that \(|f(bv)|=|f(au)|\) then it ends with an overlap \(ctctc\) such that \(|f(ct)|=|f(au)|\) and vice versa.

The case where \(T\) ends with an overlap is the mirror case of the case where \(T\) starts with an overlap. We only deal with this last case.

Let us assume that \(T=bvbvbT'\) with \(|f(bv)|=|f(au)|\).

If \(\pi_1=\varepsilon\), then, by Lemma 6, we get \(au=bv\). Since \(|\sigma_2|<|f(T')|\), it implies that \(\sigma_2=\varepsilon\) and \(T'=\varepsilon\), i.e., \(T=auaua\) (with obviously \(|f(au)|=|f(ua)|=|f(bv)|\)).

If \(\pi_1 \neq \varepsilon\), let \(bv_1\) be the shortest prefix of \(bv\) such that \(|f(bv_1)|>|\pi_1f(a)|\). Let \(\sigma'\) be the word such that \(f(bv_1)=\pi_1f(a)\sigma'\) with \(|\sigma'|<|f(v_1{[|v_1|]})|\) and let \(v_2\) be the word such that \(v=v_1v_2\). Since \(|\pi_1f(au)|=|f(bv)|+|\pi_1|=|\pi_1f(a)\sigma'| +|f(v_2)|+|\pi_1|\), it follows that \(f(u)=\sigma'f(v_2)\pi_1\). It implies that \(f(bT')=\pi_1f(a) \sigma_2\). Since \(f\) is strongly bifix, \(f(bv_1)=\pi_1f(a)\sigma'\), \(|\sigma'|<|f(v_1{[|v_1|]})|\) and \(|\sigma_2|<|f(T'{[|T'|]})|\), by Lemma 6, we get that \(T'=v_1\). Let \(c\) be the last letter of \(bv_1\) (\(\neq \varepsilon\)) and let \(v_3\) be the word such that \(bv_1=v_3c\). We get that \(T=v_3cv_2v_3cv_2v_3c\) with \(|f(v_2v_3c)|=|f(bv)|=|f(au)|\).

Let us note that, in fact, \(v_2v_3c\) is a conjugated word of \(bv\).

Step : Elementary cases

Case 1.a: \(|f(T_1b)| = |\pi_1f(a)|\)

In this case, \(f(b)\) ends with \(\alpha_2\). If \(b \neq a\) then \(f(baa)\) ends with \(\alpha_2 A_2\alpha_2 A_2\alpha_2\). This means that \(f\) is not overlap-free. If \(b=a\) then, since \(|\pi_1|<|f(T{[1]})|\), we obtain \(T_1= \varepsilon=\pi_1\). From Lemma 5, the equality \((f(T)=)f(bvbvbT_2)=f(auaua)\sigma_2\) with \(|\sigma_2|<|f(T{[|T|]}|\) implies that \(\sigma_2=\varepsilon\) and that \(bvbvbT_2=auaua\). Since \(auaua\) is a pure overlap, we therefore have \(T_2=\varepsilon\) and \(au=bv\).

Case 1.b: \(|f(bT_2)| = |f(a)\sigma_2|\)

As in case 1.a, we obtain that \(T\) ends with \(ua=vb\) when \(a=b\). And \(f(aab)\) starts with \(\alpha_1A_1\alpha_1A_1\alpha_1\) when \(a\neq b\), i.e., \(f\) is not overlap-free.

Case 2.a: \(|\pi_1f(a)| \leq |f(T_1)|\)

Since \(|\sigma_2|<|f(T{[|T|]})|\), the word \(f(uaua)\) contains the overlap \(\beta_1B_1f(v)\beta_1B_1f(v)\beta_1\) with \(uaua\) overlap-free: \(f\) is not overlap-free.

Case 2.b: \(|f(a)\sigma_2| \leq |f(T_2)|\)

As in case 2.a and since \(|\pi_1|<|f(T{[|1|]})|\), we get that the word \(f(auau)\) contains the overlap \(\beta_2f(v)B_2\beta_2f(v)B_2\beta_2\) with \(auau\) overlap-free: \(f\) is not overlap-free.

Case 3.a: \(|\pi_1f(a)| > |f(T_1b)|\) and \(T_2 =\varepsilon\)

It means that \(|\pi_1A_2| \geq |f(T_1b)|\). So the overlap \(\alpha_2f(u)A_2\alpha_2f(u)A_2\alpha_2\) is a factor of \(f(vbvb)\) with \(vbvb\) overlap-free: \(f\) is not overlap-free.

Case 3.b: \(|f(a)\sigma_2|>|f(bT_2)|\) and \(T_1=\varepsilon\)

As Case 3.a, we obtain that the overlap \(\alpha_1A_1f(u)\alpha_1A_1f(u)\alpha_1\) is a factor of \(f(bvbv)\) with \(bvbv\) overlap-free: \(f\) is not overlap-free.

Step : Other cases

If \(f(bvbvb)\) and \(f(auaua)\) have a common factor of length greater than or equal to \(|f(au)| + |f(bv)|\) then, according to the corollary 10, there exist two integers \(i,j \geq 1\) and two words \(t_1,t_2\) such that \(f(au) = (t_1t_2)^i\) and \(f(bv) = (t_2t_1)^j\), where \(t_1t_2\) and \(t_2t_1\) are primitive words.

If \(i \geq 2\), then \(f(auau)\) contains a cube, and therefore an overlap with \(auau\) overlap-free. Similarly, if \(j \geq 2\), we obtain that \(f\) is not overlap-free. Having \(i=j=1\) means that \(f(au)\) and \(f(bv)\) are conjugated words. Since \(|\pi_1|<|f(T{[1]}|\) and \(|\sigma_2|<|f(T{[|T|]})|\), if we have \(T_1 = \varepsilon\), or \(T_2 = \varepsilon\) then it ends the proof.

So, from now, when \(T_1 = \varepsilon\), or \(T_2 = \varepsilon\), we will assume that any common factor of \(f(bvbvb)\) and \(f(auaua)\) is of length less than \(|f(au)| + |f(bv)|\).

Case 4.a: \(|f(T_1)| < |\pi_1f(a)| <|f(T_1b)|\) and \(T_1 \neq \varepsilon\)

If \(T_2= \varepsilon\), then \(f(uaua)\) and \(f(bvbv)\) are common factor of \(f(bvbvb)\) and \(f(auaua)\) (of length greater than or equal to \(|f(au)| + |f(bv)|\)). So, as previously said, it ends the proof.

If \(T_2 \neq \varepsilon\), since \(|\sigma_2|<|f(T_2)|\), the word \(f(uaua)\) contains the overlap \(\beta_2f(v)B_2\beta_2f(v)B_2\beta_2\) with \(uaua\) overlap-free: \(f\) is not overlap-free.

Case 4.b: \(|f(bT_2)| < |f(a)\sigma_2|<|f(T_2)|\) and \(T_2 \neq \varepsilon\)

This case is solved as Case 4.a.

Case 5: \(|\pi_1f(a)| < |f(b)|\) and \(|f(a)\sigma_2| < |f(b)|\) with \(T_1=T_2=\varepsilon\)

As we previously said, if \(f(bvbvb)\) and \(f(auaua)\) have a common factor of length greater or equal to \(|f(au)| + |f(bv)|\) then it ends the proof.

There exist two non-empty words \(x\) and \(t\) such that \(f(b)=\pi_1f(a)t=xf(a)\sigma_2\). Since \(f(auaua)=f(a)tf(vbv)xf(a)\) is a common factor of \(f(bvbvb)\) and \(f(auaua)\), we have \(|f(auaua)|+|f(a)tf(vbv)xf(a)| < 2|f(au)| + 2|f(bv)|\), i.e., \(|f(b)|>3|f(a)|+|x|+|t|\). Therefore, there exists a word \(Y\) such that \(|Y|>|f(a)|\), \(\pi_1=xf(a)Y\), and \(\sigma_2=Yf(a)t\), that is, \(f(b)=xf(a)Yf(a)t\). Since \(f(uau)=tf(vbv)x\), we obtain that \(|f(u)|=|tf(v)x| +\frac{1}{2}|aY|> |t|+|x|+|f(v)f(a)|\). So, there exist two words \(y\) and \(z\) such that \(Y=yf(a)z\), i.e., \(f(b)=xf(a)yf(a)zf(a)t\) and \(f(u)=(tf(v)x) \, (f(a)y) = (zf(a))\, (tf(v)x)\). From Case [Lotcase1] of Proposition 6, we get that there exist two words \(r\) and \(s\) in \(A^*\), and an integer \(n\) such that \(tf(v)x=r(sr)^{n}\), \(zf(a)=rs\), and \(f(a)y=sr\). It follows that \(f(bvb)\) contains \(zf(a)tf(v)xf(a)y=r(sr)^{n+2}\) for an integer \(n\) (since \(tx \neq \varepsilon\), if \(n=0\) then \(r \neq \varepsilon\)) and so an overlap. Since \(bvb\) is overlap-free, \(f\) is not overlap-free.

Case 6: \(|\pi_1f(a)| > |f(T_1b)|\) and \(|f(a)\sigma_2|>|f(bT_2)|\) with \(T_1 \neq \varepsilon\) and \(T_2 \neq \varepsilon\)

There exist two non-empty words \(\sigma_1\) and \(\pi_2\) such that \(f(T_1)=\pi_1 \sigma_1\) and \(f(T_2)=\pi_2 \sigma_2\). Since \(|\pi_1|<|f(T{[1]}|\), \(|\sigma_2|<|f(T_2{[|T_2|]})|\), \(f(b) \neq \varepsilon\) and \(f\) strongly bifix morphism, the word \(\sigma_1\) is a proper prefix of \(f(a)\) and the word \(\pi_2\) is a proper suffix of \(f(a)\).

If \(f(bvbvb)\) and \(f(auaua)\) have a common factor of length greater or equal to \(|f(au)| + |f(bv)|\) then, \(|f(au)|=|f(bv)|\). So \(|f(T_1bv)|=|\pi_1f(au)\sigma_1|\) and it follows that \(\sigma_1\) is a suffix of \(f(v)\). By Lemma 5, since \(|\pi_1|<|f(T_1{[1]})|\), we get that \(T_1\) is a suffix of \(v\). Let \(v'\) be the word such that \(v=v'T_1\). The overlap \(T_1bv'T_1bv'T_1\) is a prefix of \(T\). Furthermore, \(T_1bv'\) and \(bv\) are conjugated words. It follows that \(|f(T_1bv')|=|f(au)|\).

In the case of any common factor of \(f(bvbvb)\) and \(f(auaua)\) is of length less than \(|f(au)| + |f(bv)|\), we obtain the equation \(\sigma_1 f(bvbvb) \pi_2=f(auaua)\) with \(|\sigma_1 f(b)|<|f(a)|\) and \(|f(b) \pi_2|<|f(a)|\). This case is solved as Case 5, by exchanging the roles of \(au\) and \(bv\).     \(\fbox{}\)

2.2 Equations of reduction↩︎

The reduction technique described in Lemma 15 and using Lemma 14 is the central idea in the proof of Proposition 25.

The situation described in Figure 1 is an example of a case where the hypotheses of Lemma 15 hold.

We say that we have reduced \(w\).

Let us note that \(p\) is not necessarily a prefix of \(f(w_1{[1]})\) and \(s\) is not necessarily a suffix of \(f(w_{\kappa}{[|w_{\kappa}|]})\).

Figure 2 deals with Point [RemReducC1] of Remark 23 and Figure 3 deals with Point [RemReducC2] of Remark 23. In addition to the situation described in Figure 1, we will mostly use these two other points in the proof of Proposition 25.

For any positive integer \(\ell\), since \(|f(x_i)|=|f(x_j)|\) is equivalent to \(|f(x_i^\ell)|=|f(x_j^\ell)|\) and since a prefix (resp. a suffix) of \(f(x_i)\) is a prefix (resp. a suffix) of \(f(x_i^\ell)\), we immediately obtain the following Corollary that will be the central point of proof of Proposition 25.

3 Main result↩︎

Let \(f\) be a morphism from \(A^*\) to \(B^*\). We assume that \(f\) is not \(k\)-power-free and we want to show that \(f\) is not overlap-free.

The morphism \(f\) must be a strongly bifix morphism. Otherwise, \(f\) is not overlap-free and it ends the proof.

Let \(w\) be a shortest \(k\)-power-free word whose image by \(f\) contains a \(k\)-power. Hence, \(f(w)=p u^{k} s\) for two words \(p\) and \(s\) and a non-empty word \(u\) in \(B^+\).

If \(f(w)\) and \(u^{k}\) are synchronised then, by Lemma 10, \(w\) contains a \(k\)-power: a contradiction.

Now, let us assume that \(f\) is a strongly bifix morphism, and that \(f(w)\) and \(u^{k}\) are not synchronised. In particular, it implies that \(f\) is ps-morphism and injective.

The central point of this proof is that, starting with \(w\) and \(u\), we use iteratively reduction of Lemma 24 (that is, of Lemma 15 and including the special cases of Remark 23) on the word whose image contains a \(k\)-power in such a way that there is no reduction left. That is, no situation of the hypotheses of Lemma 24 can be founded after this procedure. We obtain new words \(W\) and \(U\) such that \(f(W)=PU^{k}S\) with \(P\) a proper prefix of \(W{[1]}\), \(S\) a proper suffix of \(W{[|W|]}\) and \(f(W)\) and \(U^{k}\) are not synchronised.

Moreover, if \(W \neq w\), i.e., \(|W|<|w|\), then, by definition of \(w\), it means that \(W\) contains a \(k\)-power.

We will show that either \(f\) is not overlap-free, or \(f(W)\) and \(U\) can again be reduced using Lemma 24: a contradiction.

Another way to define \(W\) is to choose a word of minimal length whose image by \(f\) contains a non-synchronised \(k\)-power. If we can reduce \(W\) then this contradicts the hypothesis of minimal length of \(W\).

We focus on the fact that \(W\) necessarily contains an overlap. Indeed, any factor of \(U^k\) of length greater than \(2|U|\) contains an overlap. So, the contrary ends the proof: \(f\) is not overlap-free. More precisely, whatever the proper conjugated word \(U_c\) of \(U\), \(f(W)\) contains \(U_cU_cx\) where \(x\) is the first letter of \(U_c\).

Step : For any pure overlap \(avava\) of \({W}\) with \(a \in A\) and \(v\in A^*\), the words \({U}^{k}\) and \(f(avava)\) do not have any common factor of length at least \(|{U}|+|f(av)|\).

By contradiction, let us assume that \({U}^{k}\) and \(f(avava)\) have a common factor of length at least \(|{U}|+|f(av)|\). By Corollary 10, there exist two words \(t_1\) and \(t_2\), and two integers \(r\) and \(q\) such that \(f(av)=(t_1t_2)^r\) and \({U}=(t_2t_1)^q\) with \(t_1t_2\) and \(t_2t_1\) primitive words.

If \(r \geq 2\) then \(f(avav)=(t_1t_2)^{2 \times r}\) with \(2 \times r \geq 4\). Therefore, \(f(avav)\) contains an overlap with \(avav\) overlap-free:  \(f\) is not overlap-free.

If \(r=1\) then let \(v_1\) and \(v_2\) be the words such that \(W=v_1\, avav \, v_2\). Since \(f(W)=p(t_2t_1)^{q \times k} s\), by Remark 11, there exist two integers \(\ell_1\) and \(\ell_2\) such that \(f(v_1)=p(t_2t_1)^{\ell_1}t_2\) and \(f(v_2)=t_1(t_2t_1)^{\ell_2}s\) with \(\ell_1 + \ell_2 \geq q \times k-3\).

Since \(f\) is strongly bifix, using Lemma 6 or Lemma 7, by induction, we get that \(W\) contains \((av)^{q}\): a contradiction with the hypothesis that \(f(W)\) and \(U^{k}\) are not synchronised.

Step : \({W}{[2..|{W}|-1]}\) contains an overlap and so a pure overlap.

By contradiction, let us assume that \({W}{[2..|{W}|-1]}\) is overlap-free. In particular, it implies that \(W\) starts or ends with a pure overlap. Let \(s_1\) and \(p_{k+1}\) be the words such that \(f({W}{[1]})=ps_1\) and \(f({W}{[|{W}|]})=p_{k+1}s\), that is, \({U}^{k}=s_1f({W}{[2..|{W}|-1]})p_{k+1}\).

If \(|s_1|+|p_{k+1}| < |U^{k-2}|\), then \(|f({W}{[2..|{W}|-1]})| > 2|U|\) and so contains an overlap: \(f\) is not overlap-free.

If \(|s_1|+|p_{k+1}| \geq |U^{k-2}| \, (\geq |U|)\) then either \(|s_1| \geq |U|/2\) or \(|p_{k+1}| \geq |U|/2\). If \(|s_1| \geq |U|/2\) and \(W\) starts with a pure overlap \(avava\) with \(a\in A\) and \(v \in A^*\). It implies that \(s_1\) is a suffix of \(f(a)\). If \(W=avava\) then \(|s_1f(vav)p_{k+1}|\geq |U|+|f(va)|\) with \(s_1f(vav)p_{k+1}\) a common factor of a power of \(U\) and a power of \(f(av)\): a contradiction with Step 1. If \(W \neq avava\) then \(|s_1f(vava)|\geq 2|s_1|+|f(va)| \geq |U|+|f(va)|\) with \(s_1f(vava)\) a common factor of a power of \(U\) and a power of \(f(av)\): a contradiction with Step 1. In a same way, If \(|p_{k+1}| \geq |U|/2\), \(W\) can not end with a pure overlap.

If \(|s_1| < |U|/2\) then \(|p_{k+1}| > |U|/2\) and \(W\) do not end with a pure overlap. So either \({W}{[2..|{W}|-1]}\) contains an overlap or \({W}{[2..|{W}|]}\) is overlap-free. But, in this second case, \(f({W}{[2..|{W}|-1]})p_{k+1}\) is factor of \(U^k\) with \(|f({W}{[2..|{W}|-1]})p_{k+1}|=k|U|-|s_1| >2|U|\). So \(f({W}{[2..|{W}|]})\) contains an overlap: \(f\) is not overlap-free.

In the same way, if \(|p_{k+1}| < |U|/2\), we obtain that \({W}{[2..|{W}|-1]}\) contains an overlap or that \(f\) is not overlap-free.

Let \(POI\) be the set of pure overlaps that are factors of \(\left({W}{[2..|{W}|-1]} \right)\).

The set \(\left\{|f(avava)| \mid avava \in POI \right\}\) is finite and admits a minimum \(L_{min}\).

Let \(POM = \left\{ avava \in POI \mid |f(avava)| =L_{min} \right\}\).

Let us also recall that, if \(avava\) is a pure overlap, then \(a\in A\).

Step : For any overlap \(avava \in POM\), the word \(f(avava)\) is an internal factor of \({U}^2\).

For any pure overlap \(avava \in POI\), since \(f(avava)\) is an internal factor of \(U^k\), by Step 1, we have \(|f(avava)| < |U|+|f(av)|\). Since \(|f(avava)| \geq 2|f(a)|\), we can not have \(|f(avava)| \geq 2|U|\).

Let \(W_1\) and \(W_2\) be the non-empty words such that \(W=W_1avavaW_2\). By contradiction, let us assume that \(f(avava)\) (with \(|f(avava)| < 2|U|\)) is not an internal factor of \({U}^2\). It means that there exist two non-empty words \(v_1\) and \(v_2\) such that \(f(avava)=v_1Uv_2\). In particular, \(v_1\) is a suffix of \(U\), \(v_2\) is a prefix of \(U\) and \(|v_1v_2|<|U|\). Since \(|f(ava)|<|{U}|\), we get that \(|v_1v_2|=|f(av)|+|f(ava)|-|U|<|f(av)|\).

Case .: \(|v_1| \leq |f(a)|\) and \(|v_2| \leq |f(a)|\)

Let \(A_1\) and \(A_2\) be the words such that \(v_1\) such that \(f(a)=v_1A_1=A_2v_2\) and \(U=A_1f(vav)A_2\).

If \(|v_1v_2| = |f(a)|\), i.e., \(|v_1|=|A_2|\) then \(|f(avav)|=|U|\): a contradiction with the assumption that \(f(W)\) and \(U^k\) are not synchronised.

In a same way, if \(|v_1| = |f(a)|\) and \(|v_2| = |f(a)|\) then \(|f(vav)|=|U|\): again a contradiction with the assumption that \(f(W)\) and \(U^k\) are not synchronised. It means that \(A_1A_2 \neq \varepsilon\).

If \(|v_1|>|A_2|\) then \(|v_2|>|A_1|\). Since \(v_1\) and \(A_2\) are both suffixes of \(U\), let \(X\) be non-empty the word such that \(v_1=XA_2\). Since \(v_2\) and \(A_1\) are both prefixes of \(U\), let \(Y\) be the non-empty word such that \(v_2=A_1Y\). We get \(Xf(a)=f(a)Y\) with \(|X|=|Y|=|v_1|-|A_2|=|v_2|-|A_1| < |f(a)|\). By Case [Lotcase1] of Proposition 6 and Remark 7, we get that \(f(a)Y\), prefix of \(f(ava)\), contains an overlap: \(f\) is not overlap-free.

If \(|v_1|<|A_2|\) then \(|v_2|<|A_1|\). Let \(X\) be the non-empty word such that \(Xv_1=A_2\). Since \(v_2\) and \(A_1\) are both prefixes of \(U\), let \(Y\) be the word such that \(A_1=v_2Y\). We get \(Xf(a)=f(a)Y\) with \(|X|<|f(a)|\). By Case [Lotcase1] of Proposition 6, there exist two words \(r\) and \(s\) in \(A^*\), and an integer \(n\) such that \(f(a)=r(sr)^{n}\), \(X=rs\) and \(Y=sr\). Since \(|X|<|f(a)|\), we get that \(n \geq 1\) when \(r \neq \varepsilon\) and \(n \geq 2\) when \(r = \varepsilon\). But, if \(s=\varepsilon\) or if \(n \geq 2\), since \(f(a)\) or \(f(aa)\) contains an overlap, we get that \(f\) is not overlap-free: it ends the proof. So we may assume that \(n=1\), \(r \neq \varepsilon\) and \(s \neq \varepsilon\).

Let \(W_1'\) the smallest suffix of \(W_1\) such that \(f(W_1')\) ends with \(X\). There exist a word \(p_1'\) such that \(f(W_1')=p_1'X\) with \(|p_1'|<|f(W_1'{[1]})|\). It follows that \(f(W_1'a)=p_1'rsrsr\). If \(W_1'a\) is overlap-free, it ends the proof: \(f\) is not overlap-free. Since \(|f(W_1')|=|p_1'sr|\) and \(|f(a)|=|rsr|\), if \(W_1'a\) contains an overlap \(btbtb\) then \(b \neq a\) and \(|f(btbtb)|<|f(avava)|\): a contradiction the hypothesis of the minimal length of \(f(avava)\).

Case .: \(|v_1| > |f(a)|\)

Since \(f(a)\) is the suffix of \(Uv_2\) and of \(v_1v_2\) of length \(|f(a)|\), let \(X\) be the word such that \(v_1v_2=Xf(a)\). And, since \(f(a)\) is a prefix of \(v_1\), let \(Y\) be the word such that \(v_1v_2=f(a)Y\).

If \(|Y|=|f(a)|\) then \(|f(vava)|=|U|\): a contradiction with the assumption that \(f(W)\) and \(U^k\) are not synchronised.

If \(|Y|<|f(a)|\), by Case [Lotcase1] of Proposition 6 and Remark 7, we get that \(f(a)Y\), prefix of \(f(ava)\), contains an overlap: \(f\) is not overlap-free.

If \(|Y|>|f(a)|\), let \(Z\) be the non-empty word such that \(Y=Zf(a)\) and \(X=f(a)Z\). Since \(|f(av)|>|v_1v_2|\), we get that \(v \neq \varepsilon\), \(Y\) is a prefix of \(f(v)\) and \(X\) is a suffix of \(f(v)\). It follows that \(f(vav)\) contains the overlap \(f(a)Zf(a)Zf(a)\): \(f\) is not overlap-free.

Case .: \(|v_2| > |f(a)|\)

It is the mirror image of Case .

Step : Decomposition of \(U^k\).

For every integer \(j\) in \([1,k+1]\), let \(i_j\) be the smallest integer such that \(PU^{j-1}\) is a prefix of \(f(W{[1..i_j]})\). We have \(i_1=1\) and there exist some words \(p_j\) and \(s_j\) such that \(f(W{[i_j]})=p_js_j\), \(p_1=P\), \(s_{k+1}=S\), \(p_j \neq \varepsilon\) if \(j \neq 1\), and \(s_1 \neq \varepsilon\).

Let \(avava\) be an overlap and let us assume that \(avava \in POM\). If \(i_j=i_\ell\) with \(j < \ell\) then, by definition of \(i_j\) and \(i_\ell\), it means that \(f(W{[i_j]})\) contains \(U^{\ell-j}\). If \(f(avava)\) is factor of \(U\) that is of \(f(W{[i_j]})\) then \(f\) is not overlap-free. If \(f(avava)\) is factor of \(U^2\) (but not of \(U\)) then we must have \(j+1=\ell\) (and \(i_{j+1}\neq i_{j+2}\)) otherwise \(f\) is not overlap-free (and it ends the proof). It follows that \(f(avava)\) is a factor of \(f(W{[i_j..i_{j+2}]})\). Let \(\alpha \geq i_{j}\) be the greatest integer and \(\beta \leq i_{j+2}\) be the lowest integer such that \(f(avava)\) is a factor of \(f(W{[\alpha..\beta]})\) that is \(f(W{[\alpha..\beta]})=\pi_1f(auaua)\sigma_2\) with \(|\pi_1|<|f(W{[\alpha]})|\) and \(|\sigma_2|<|f(W{[\beta]})|\). By Lemma 13, either \(f\) is not overlap-free (and it ends the proof) or \(W{[\alpha..\beta]}\) starts with an overlap. In this second case, since \(f(avava)\) is not factor of \(U\), we get that \(\alpha=i_j\). It follows that \(W{[i_j..\beta]}\) contains at least three occurences of \(W{[i_j]}\) that is \(|f(W{[i_j..\beta]})| \geq 3|U|\): a contradiction with \(i_j=i_{j+1}\) and \(\beta \leq i_{j+2}\).

So we get that \(i_j \neq i_\ell\) when \(j \neq \ell\). It follows \(f(\omega{[1..i_{j}]})=pU^{j-1}s_{j}\) for every integer \(j\) in \([1,k+1]\) and \(U=s_jf(\omega{[i_j+1..i_{j+1}-1]})p_{j+1}\) for every integer \(j\) in \([1,k]\).

Step : Case where there exists an overlap \(avava \in POM\) such that \(f(avava)\) is an internal factor of \(U\).

It means that, for every integer \(j\) in \([1,k]\), \(f(avava)\) is an internal factor of \(f(\omega{[i_j..i_{j+1}]})\). Let \(T_j\) be the shortest factor of \(f(\omega{[i_j..i_{j+1}]})\) that contains \(f(avava)\).

By Lemma 13 and Remark 21, there exist a letter \(b_j\) and a word \(v_j\) such that \(T_j\) starts with \(b_jv_jb_jv_jb_j\) with \(f(v_jb_j)\) an internal factor of \(f(au)f(au)\) and \(|f(b_jv_j)|=|f(v_jb_j)|=|f(au)|\). By Lemma 15 and Remark 22, a reduction can be done: a contradiction with the hypotheses.

Step : Case where, for any overlap \(avava \in POM\), \(f(avava)\) is an internal factor of \({U}^2\) but not of \(U\).

For any \(avava \in POM\), let \(V_{1,av}\) and \(V_{2,av}\) be the words such that \(f(avava)=V_{1,av}V_{2,av}\) with \(V_{1,av}\) a suffix of \(U\) and \(V_{2,av}\) a prefix of \(U\). In particular, we have either \(|f(av)|<|V_{1,av}|\) or \(|f(av)|<|V_{2,av}|\). For any integer \(j\) in \([1,k-1]\), \(f(avava)\) is an internal factor of \(f(\omega{[i_j..i_{j+2}]})\). Let \(T_j\) be the shortest factor of \(f(\omega{[i_j..i_{j+2}]})\) that contains \(f(avava)\).

Let \(\alpha \nu \alpha \nu \alpha \in POM\) such that \(|V_{1,\alpha \nu}|= \max \{|V_{1,av}| \mid avava \in POM\}\) and let \(\beta \mu \beta \mu \beta \in POM\) such that \(|V_{2,\beta \mu}|= \max \{|V_{2,av}| \mid avava \in POM\}\).

Let \(j_\alpha\) be an integer such that \(\alpha \nu \alpha \nu \alpha \in {\rm Fcts} \left( \omega{[i_{j_\alpha}..i_{j_\alpha+2}]} \right)\).

For any integer \(j\) in \([1,k-1]\), let \(T_j\) be the shortest factor of \(f(\omega{[i_j..i_{j+2}]})\) that contains \(f(\alpha \nu \alpha \nu \alpha)\). Since \(f(W)\) and \(U^k\) are not synchronised, there exists an integer \(r \in \{j_\alpha-1,j_\alpha+1\}\) such that \(T_r \neq \alpha \nu \alpha \nu \alpha\). By Lemma 13 and Remark 21, there exist a letter \(b_r\) and a word \(v_r\) such that \(T_r\) starts with \(b_rv_rb_rv_rb_r\) with \(|f(b_rv_r)|=|f(\alpha \nu)|\). Since \(|V_{1,b_r v_r}|<|V_{1,\alpha \nu}|\), it implies that \(b_r =W{[i_r]}\) and \(V_{1,b_r v_r}=p_r\). Since \(f(b_rv_rb_rv_rb_r)\) is an internal factor of \(U^2\), it follows that \(|V_{1,\alpha \nu}| > 2|f(v_r b_r )| = 2|f(\alpha \nu)|\).

Moreover, we have \(|V_{2,\beta \mu}| \geq |V_{2,b_r v_r}| = |s_r| + 2|f(v_r b_r )| \geq 2|f(\beta \mu)|\).

By Lemma 13 and Remark 21, for any integer \(j \in [1,k-1]\), there exist a letter \(b_j\) and a word \(v_j\) such that \(T_j\) starts with \(b_jv_jb_jv_jb_j\) with \(f(b_jv_j)\) an internal factor of \(f(\beta \mu)f(\beta \mu)\) and \(|f(b_jv_j)|=|f(\beta \mu)|\).

Since \(|V_{2,\beta \mu}| \geq 2|f(\beta \mu)|\), for any integer \(j \in [1,k-1]\), there exist a word \(X_j\) such that \(V_{2,b_j v_j}\) starts with \(f(v_jb_j)\) or with \(f(b_jv_j)\) and \(|X_j|<|f(b_jv_j)|=|f(v_jb_j)|\). Let \(q\) be the integer such that \(|X_q|=\max \{|X_i| \mid j \in [1,k-1]\}\). By Lemma 15, Point [RemReducC1] of Remark 23 and Remark 22, a reduction can be done: a contradiction with the hypotheses.     \(\fbox{}\)

References↩︎