Equation xiyjxk = uivjuk in words Jana Hadravováand Štěpán Holub Faculty of Mathematics and Physics, Charles University 186 75 Praha 8, Sokolovská 83, Czech Republic 5 hadravova@ff.cuni.cz, holub@karlin.mff.cuni.cz 1 0 2 n Abstract. We will prove that the word aibjak is periodicity forcing if a j ≥ 3 and i+k ≥ 3, where i and k are positive integers. Also we will J give examples showing that both boundsare optimal. 5 1 1 Introduction ] L F Periodicity forcing words are words w ∈A∗ such that the equality g(w)=h(w) . is satisfied only if g = h or both morphisms g,h : A∗ → Σ∗ are periodic. s c The first analysis of short binary periodicity forcing words was published by J. [ Karhumäki and K. Culik II in [2]. Besides proving that the shortest periodicity forcing words are of the length five, their work also covers the research of the 1 v non-periodic homomorphisms agreeingon the givensmall word w over a binary 2 alphabet. What in their work attracts attention the most, is the fact, that even 0 short word equations can be quite difficult to solve.The intricacies of the equa- 6 tion x2y3x2 = u2v3u2, proved to have only periodic solution [3], nothing but 3 reinforced the perception of difficulty. Not frightened, we will extend the result 0 . and prove that the word aibjak is periodicity forcing if j ≥ 3 and i+k ≥ 3, 1 where i and k are positive integers. Also we will give examples showing that 0 5 both bounds are optimal. 1 : v i 2 Preliminaries X r a Standard notation of combinatoric on words will be used: u≤ v (u≤ v resp.) p s means that u is a prefix of v (u is a suffix of v resp.). The maximal common prefix(suffix resp.)oftwowordu,v ∈A∗ willbe denotedbyu∧v (u∧ v resp.). s Bythe length of a worduwemeanthe numberofits lettersandwedenoteitby |u|. A (one-way) infinite word composed of infinite number of copies of a word u will be denoted by uω. It should be also mentioned that the primitive root of a word u, denoted by p , is the shortest word r such that u = rk for some u positive k. A word u is primitive if it equals to its primitive root. Words u,v are conjugate if there are words α,β such that u=αβ and v =βα. For further reading, please consult [6]. 2 We will briefly recall a few basic and a few more advanced concepts which will be needed in the proof of our main theorem. Key role in the proof will be played by the Periodicity lemma [6]: Lemma 1 (Periodicity lemma).Letp andq beprimitive words. If pω and qω have a common factor of length at least |p|+|q|−1, then p and q are conjugate. If, moreover, p and q are prefix (or suffix) comparable, then p=q. Reader should also recall that if two word satisfy an arbitrary non-trivial relation, then they have the same primitive root. Another well-known result is the fact that the maximal common prefix (suffix resp.) of any two different words from a binary code is bounded (see [6, Lemma 3.1]). We formulate it as the following lemma: Lemma 2. Let X = {x,y} and let α ∈ xX∗, β ∈ yX∗ be words such that α∧β ≥|x|+|y|. Then x and y commute. The previouslemma can be formulatedalso for the maximal commonsuffix: Lemma 3. Let X = {x,y} and let α ∈ X∗x, β ∈ X∗y be words such that α∧ β ≥|x|+|y|. Then x and y commute. s The most direct and most well known case is the following. Lemma 4. Let s=s s and let s ≤ s and s ≤ s. Then s and s commute. 1 2 1 s 2 p 1 2 Proof. Directly, we obtain s=s s =s s . 1 2 2 1 Next, let us remind the following property of conjugate words: Lemma 5. Let u,v,z ∈ A∗ be words such that uz = zv. Then u and v are conjugate and there are words σ,τ ∈A∗ such that στ is primitive and ∗ ∗ ∗ u∈(στ) , z ∈(στ) σ, v ∈(τσ) . We will also need not so well-know, but interesting, result by A. Lentin and M.-P. Schützenberger [4]. Lemma 6. Suppose that x,y ∈A∗ do not commute. Then xy+∪x+y contains at most one imprimitive word. Wenowintroducesomemoreterminology.Supposethatxandy donotcom- mute and let X = {x,y}, i.e. we suppose that X is a binary code. We say that a word u ∈ X∗ is X-primitive if u = vi with v ∈ X∗ implies u = v. Similarly, u,v ∈ X∗ are X-conjugate, if u = αβ and v = βα and the words α and β are from X∗. In the following lemma, first proved by J.-C. Spehner [7], and consequently by E. Barbin-Le Rest and M. Le Rest [1], we will see that all words that are imprimitive but X-primitive are X-conjugate of a word from the set x∗y∪xy∗. 3 Source of the inspiration of both articles was an article by A. Lentin and M.-P. Schützenberger [4] with its weaker versionstating that if the set of X-primitive words contains some imprimitive words, then so does the set x∗y ∪xy∗. As a curiosity, we mention that Lentin and Schützenberger formulated the theorem for x∗y∩y∗x instead ofx∗y∪y∗x (for which they provedit). Also, the Le Rests did not include in the formulationof the theorem the trivial possibility that the word x or the word y is imprimitive. Lemma 7. Suppose that x,y ∈ A∗ do not commute and let X = {x,y}. If w ∈ X∗ is a word that is X-primitive and imprimitive, then w is X-conjugate of a word from the set x∗y∪y∗x. Moreover, if w 6∈ {x,y}, then primitive roots of x and y are not conjugate. Putting together Lemma 6 with Lemma 7, we get the following result: Lemma 8. Suppose that x,y ∈ A∗ do not commute and let X = {x,y}. Let C be the set of all X-primitive words from X+ \X that are not primitive. Then either C is empty or there is k ≥1 such that C ={xiyxk−i,0≤i≤k} or C ={yixyk−i,0≤i≤k}. Thepreviouslemmafindsitsinterestingapplicationwhensolvingwordequa- tions. For example, we can see that an equation xiyjxk =zℓ, with ℓ≥ 2, j ≥2 andi+k≥2 has only periodic solutions.(This is a slightmodification ofa well known result of Lyndon and Schützenberger [5]). Notice, that we can use the previous lemma also with equations which would generate notable difficulties if solved “by hand”. E.g. equation (yx)iyx(xxy)jxy(xy)k =zm, with m≥2 , has only periodic solutions. We formulate it as a special lemma: Lemma 9. Suppose that x,y ∈A∗ do not commute and let X ={x,y}. If there is an X-primitive word α∈X∗ and a word z ∈A∗, such that α=zi, with i≥2, then α=xkyxℓ or α=ykxyℓ, for some k,ℓ≥0. We finish this preliminary part with the following useful lemmas: Lemma 10. Let u,v,z ∈A∗ be words such that z ≤ v and uv ≤ zvi, for some s p i≥1. Then uv ∈zp∗. v Proof. Let 0 ≤ j < i be the largest exponent such that zvj ≤ uv and let p r = (zvj)−1uv. Then r is a prefix of v. Our assumption that z ≤ v yields that s v ≤ vr and s r(r−1v)=v =(r−1v)r. Fromthecommutativityofwordsr−1v andr,itfollowsthattheyhavethesame primitiveroot,namely p .Since uv=(zvj)r wehaveuv ∈zp∗,whichconcludes v v the proof. 4 Lemma 10 has the following direct corollary. Lemma 11. Let w,v,t ∈ A∗ be words such that |t| ≤ |w| and wv ≤ tvi, for p some i≥1. Then w ∈tp∗. v Proof. Lemma10withu=t−1wandzemptyyieldsthatuv ∈p∗.Thenwv ∈tp∗ v v and from |t|≤|w|, we obtain that w ∈tp∗. v Lemma 12. Let u,v ∈ A∗ be words such that |u| ≥ |v|. If αu is a prefix of vi and uβ is a suffix of vi, for some i≥1, then αuβ and v commute. Proof. Since αu≤ vi and |u|≥|v| we have p α−1vα≤ u≤ uβ. p p Our assumption that uβ is a suffix of vi yields that uβ has a period |v|. Then, uβ ≤ (α−1vα)i and,consequently, αuβ ≤ vi. Fromv ≤ uβ andLemma 10, it p p s follows that αuβ ∈p∗, which concludes the proof. v Lemma 13. Letu,v ∈A∗ bewordssuchthat|u|≥|v|.Ifαuandβuareprefixes of vi, for some i≥1, and |α|≤|β|, then α is a suffix of β, and βα−1 commutes with v. Proof. Since αu is a prefix of v+ and |u|≥ |v|, we have α−1vα ≤ u. Similarly, p β−1vβ ≤ u. Therefore, p α−1vα=β−1vβ, and |α| ≤|β| yields α≤ β. From βα−1v =vβα−1 we obtain commutativity of s v and βα−1. Notice that the previous result can be reformulated for suffixes of vi: Lemma 14. Letu,v ∈A∗ bewordssuchthat|u|≥|v|.Ifuαanduβ aresuffixes of vi, for some i≥1, and |α|≤|β|, then α is a prefix of β, and α−1β commutes with v. 3 Solutions of xiyjxk = uivjuk Theorem 1. Let x,y,u,v ∈A∗ be words such that x6=u and xiyjxk =uivjuk, (1) where i+k ≥3, ik6=0 and j ≥3. Then all words x,y,u and v commute. Proof. First notice that, by Lemma 9, theorem holds in case that either of the words x, y, u or v is empty. In what follows, we suppose that x, y, u and v are non-empty. By symmetry, we also suppose, without loss of generality, that |x|>|u| and i≥k; in particular, i≥2. Recall that p (p , p , p resp.) denote x y u v the primitive root of x (y, u, v resp.). We first prove the theorem for some special cases. 5 (A) Let p = p . x u Then pinyjpkn =vj for some n≥1, and we are done by Lemma 9. x x Noticethatthe solutionofcase(A)allowsustoassumetheusefulinequality (i+k−1)|u|<|p |, (∗) x sinceotherwisepω anduω haveacommonfactorofthelengthatleast|p |+|u|, x x and u and x commute by the Periodicity lemma. From (u−i+1p u−k)u=u(u−ip u−k+1) x x andLemma5 wesee thattherearewordsσ andτ suchthatστ is primitiveand (u−i+1p u−k)∈(στ)m, u=(στ)ℓσ, u−i+1p u−k ∈(τσ)m, x x for some m≥1 and ℓ≥0. Then we have u=(στ)ℓσ, p =ui(τσ)muk−1 =ui−1(στ)muk, (∗∗) x for some m≥1 and ℓ≥0. (B) Let p and p be conjugate. y v Let α and β be such that p = αβ and p = βα. Since xip is a prefix of y v y uip+, we can see that u−ixiαβ ≤ β(αβ)+. From Lemma 10 we infer that v p andu−ixi ∈β(αβ)∗.Similarly,bythemirrorsymmetry,p xk ≤ p+uk yields y s v that xku−k ∈(αβ)∗α. Then xi+k =uipnuk, v for some n ≥ 1. From |v| > |y|, it follows that |v| ≥ |y|+|p | and, conse- v quently, (i+k)(|x|−|u|)=j(|v|−|y|)≥3|p |. v Then n≥3 and we are done by Lemma 9. (C) Let p and p be conjugate. x v Let α and β be such that p = αβ and p = βα. From (∗) and i ≥ 2, it x v follows that uip is a prefix of p2. Then ui(βα) ≤ α(βα)+ and Lemma 10 v x p yields that ui ∈ α(βα)∗. From i|u| < |p |, it follows ui = α. Since p is a x x suffix of αβαuk =p ui+k and u is a prefix of p , we deduce from Lemma 3 x x that x and u commute, case (A). We will now discuss separately cases when |x|≥|v| and |x|<|v|. 1. Suppose that |x|≥|v|. If i ≥ 3 or x 6= p , then (u−ix)xi−1 is a prefix of vj that is longer than x |p |+|x| by (∗). By the Periodicity lemma, p is a conjugate of p and we are x x v in case (C). The remaining cases deal with i=k =2 and i=2, k =1. 6 x x ... yj ... x ui v ... v uk Figure1. Case |x|≥|v|. 1a) First suppose that i = k = 2. Since (u−ix)x is a prefix of vj and x(xu−k) is a suffix of vj, we get, by Lemma 12, that (u−ix)x(xu−k) commutes with v. Then x3 =uipnuk, v for some n ≥ 0. From (i+k−1)|u| < |p | ≤ |x| and |p | ≤ |v| ≤ |x| we infer x v that n≥2. Therefore, p =p holds by Lemma 9, and we have case (A). u x 1b) Suppose nowthati=2andk =1.We willhavealook atthe wordsuand x=p expressed by (∗∗). Let h=(στ)m and h′ =(τσ)m. Then (∗∗) yields x u=(στ)ℓσ, x=u2h′ =uhu. 1b.i) Supposenowthat|p |≤|uh|.Sinceh′uhisaprefixofvj anduhisasuffix v ofvj,we obtainby Lemma 12 thath′uh=pn . From|p |≤|uh|,we infer n≥2 v v and,accordingto Lemma9,σ andτ commute.Thenalsoxanducommuteand we have case (A). 1b.ii) Supposethat|p |>|uh|.From|x|≥|v|≥|p |,itfollowsthatp =h′uu v v v 1 forsomeprefixu ofu.Wecansupposethatu isaproperprefixofu,otherwise 1 1 x and v are conjugate and we have case (C). Then u h′ ≤ uh′ ≤ (στ)+ and, 1 p p by Lemma 13, we obtain uu−1 ∈(στ)+. Therefore, u ∈(στ)∗σ. Since h≤ p , 1 1 s v we can see that στ ≤ τσ+. Lemma 3 then implies commutativity of σ and τ. s Therefore, the words x and u also commute and we are in case (A). 2. Suppose that |x|<|v| and i|x|=i|u|+|v|. From x≤ v, we have x≤ xuk. Since u≤ x we deduce from Lemma 3 that x s s p and u commute, thus we have case (A). 3. Suppose that |x|<|v| and i|x|>i|u|+|v|. r xi yj xk ui v vj−1 uk Figure2. Case |x|<|v| and i|x|>i|u|+|v|. Let r be a non-empty word such that uivr = xi. Notice that |r| < |p | x otherwise the words p and p are conjugate and we have case (C). Considering x v 7 the words u and p expressed by (∗∗), we can see that (τσ)muk−1ui is a prefix x of v and ui−1(στ)m is a suffix of v. Notice also that we have case (A) if σ and τ commute. 3a) Consider first the special case when r =uk. 3a.i) If i = k, then vj−2 = uiyjui. If j ≥ 4, we have case (B) by Lemma 9. If j = 3, then the equality uivr = xi implies xi = u2iyju2i and we get case (A) again by Lemma 9. 3a.ii) Supposethereforethatk k and (∗) we get |u−ixi−k| > 0 and, consequently, |vuk| > |xk|. Let v′ dente the word vukx−k. Then vj−2v′ = ryj, and j ≥ 3 together with |v| > |x| > |uk| = |r| yields that v′ is a suffix of yj. According to (∗∗), v′ = u−ixi−k ∈(τσ)mσk−1p∗. Then, σk is a suffix of yj and we have x (σkyσ−k)j =σkyjσ−k =vj−2v′σ−k. ThisisapointwhereLemma9turnsouttobeextremelyuseful.Directinspection yields that vj−2v′σ−k is nota jth powerof a wordfrom{σ,τ}∗.One canverify, for example, that the expression of vj−2v′σ−k in terms of σ and τ contains exactlyj−2occurrencesofτ2.Therefore,Lemma9yieldsthatσandτ commute, a contradiction. 3b) We first show that r = uk holds if k ≥ 2. Indeed, if k ≥ 2 then ukp u−k x is a suffix of v and, consequently, ukp u−kr is a suffix of xi. Since ukp u−kuk is x x also a suffix of xi, we can use Lemma 14 and get commutativity of x with one of the words u−kr or r−1uk. From |r|<|p | and |uk|<|p |, we get r=uk. x x 3c) Suppose that k =1 and r 6=u. 3c.i) If |r| < |u|, then r is a suffix of u and |xr−1u| > |x|. Since xr−1 ≤ v s and k = 1, the word x = xr−1r is a suffix of xr−1u. Therefore, xr−1 is a suffix of (ur−1)+. Since u2 ≤ x and |xr−1| ≥|u|+(|u|−|r|), the Periodicity lemma p implies that the primitive root of ur−1 is a conjugate of p . But since p is u u prefix comparable with ur−1, we obtain that ur−1 ∈ p+. Then also r ∈p+ and u u xr−1 ∈p+. Consequently, x and u commute, and we have case (A). u 3c.ii) Supposethereforethat|r|>|u|.Thenuisasuffixofr. Sincer isasuffix of p and p = ui(τσ)m, the word r is a suffix of ui(τσ)m. From |v| > |x| we x x obtain u−ixui ≤ v. Consequently, from p = ui(τσ)m and r ≤ v, it follows p x p that r is a prefix of (τσ)mui. Consider first the special case when r ∈ (τσ)mp∗. If r ∈ (τσ)mp+, then u u r ≤ ui(τσ)m yields that (τσ)m and u commute by Lemma 3. Consequently, σ s and τ commute, and we have case (A). Therefore, r = (τσ)m, p = uir and x v = u−ixir−1 ∈ (rui)+. We have proved that x and v have conjugate primitive roots, which yields case (C). Consider now the general case. 8 If m ≤ ℓ, then (τσ)m is a suffix of u. Since r is a prefix of (τσ)mui, and u≤ r, we get from Lemma 10 the case r∈(τσ)mp∗. s u Suppose that m > ℓ. Then u is a suffix of (τσ)m. Let s denote the word (τσ)mu−1 =(τσ)m−ℓ−1τ. If|r|≥|(τσ)m|,thenr =s′suforsomes′.Fromr ≤ (τσ)mui,itfollowsthat p s′su is a prefix of sui+1. Lemma 11 then yields s′s ∈ sp∗. Therefore r ∈ sup∗ u u and from su=(τσ)m, we have the case r ∈(τσ)mp∗. u Let |r| < |(τσ)m|. From |r| > |u| and (τσ)m = su, we obtain that there are words s ,s such that s = s s , r = s u ≤ v and s ≤ v. Since s is both a 1 2 1 2 2 p 1 s prefixandasuffixofv,Lemma4implies thats ands havethe sameprimitive 1 2 root, namely p . s Note that p =uisu. We now have x uis s =uis≤ v ≤ xir−1 ≤ (uisu)i−1uis . 2 1 s s s 1 Fromi≥2,itfollowsthatuis isasuffixof(uisu)i−1ui forsomen≥1.Lemma 2 3thenyieldscommutativityofsandu.Hence,wordsxandualsocommuteand we are in case (A). 4. Suppose now that |x|<|v| and i|x| |x|, denote z = x−1uiγ and z′ = γ−1vα−1 = xku−kα−1. From ′ |y|+|γ|+|α|<|v|=|γz α|, we deduce |y|<|z′| . Since xi−1 =zz′ and z′ is a prefix of xk, the word zz′ has a period |z| < |γ|. Since zz′ is a factor of v greater than |z|+|y| and v has a period |p |, the Periodicity lemma implies |p |≤|z|<|γ|, a contradiction with y y |γ|<|p |. ⊓⊔ y 4 Conclusion The minimal bounds for i, j, k in the previous theorem are optimal. In case that i=k and j is even, Eq. (1) splits into two separate equations, which have a solution if and only if either i=k and j =2, or i=k =1, see [2]. Apart from these solutions, we can find non-periodic solutions also in case that i6=k. Namely, for j =2 and i=k+1, we have x=α2k+1(βαk)2, u=α, y =βαk, v =(αkβ)2(α3k+1βαkβ)k. So far this seems to be the only situation when the equation xiy2xk =uiv2uk (2) with i > k has a non-periodic solution. We conjecture that if |i−k| ≥ 2, then Eq. (2) has only periodic solutions. Ifi=k =1 andj is odd,thenEq. (1)has severalnon-periodicsolutions,for example: x=αβα, u=α, y =γ, v =αγjα, where β2 =vj−1. References 1. EvelyneBarbin-LeRest and Michel LeRest. Surlacombinatoire descodesà deux mots. Theor. Comput. Sci.,41:61–80, 1985. 2. KarelCulikIIandJuhaniKarhumäki. Ontheequalitysetsforhomomorphismson free monoids with two generators. ITA,14(4):349–369, 1980. 3. ElenaCzeizler,ŠtěpánHolub,JuhaniKarhumäki,andMarkkuLaine. Intricaciesof simple word equations: an example. Internat. J. Found. Comput. Sci., 18(6):1167– 1175, 2007. 10 4. A.LentinandM.-P.Schützenberger. Acombinatorial probleminthetheoryoffree monoids. InG.Pollak,editor,Algebraic theory of semigroups / edited by G. Pollak. North-Holland Pub. Co Amsterdam ; NewYork,1979. 5. R. C. Lyndon and M.-P. Schützenberger. The equation am =bncp in a free group. The Michigan Mathematical Journal, 9(4):289–298, 12 1962. 6. GrzegorzRozenbergandArtoSalomaa,editors. Handbook of formallanguages, vol. 1: word, language, grammar. Springer-Verlag New York,Inc.,USA,1997. 7. J.-P. Spehner. Quelques problèmes d’extension, de conjugaison et de presentation dessous-monoïdesd’unmonoïdelibre.PhDthesis,UniversitéParisVII,Paris,1976.

Equation $x^iy^jx^k=u^iv^ju^k$ in words

Similar Equation $x^iy^jx^k=u^iv^ju^k$ in words