KERNEL WORDS AND GAP SEQUENCE OF THE TRIBONACCI SEQUENCE∗

Yuke HUANG(黄煜可)School of Mathematics and Systems Science,Beihang University,Beijing 100191,ChinaE-mail:hyg03ster@163.comZhiying WEN(文志英)Department of Mathematical Sciences,Tsinghua University,Beijing 100084,ChinaE-mail:wenzy@tsinghua.edu.cn



KERNEL WORDS AND GAP SEQUENCE OF THE TRIBONACCI SEQUENCE∗

Yuke HUANG(黄煜可)
School of Mathematics and Systems Science,Beihang University,Beijing 100191,China
E-mail:hyg03ster@163.com
Zhiying WEN(文志英)†
Department of Mathematical Sciences,Tsinghua University,Beijing 100084,China
E-mail:wenzy@tsinghua.edu.cn

AbstractIn this paper,we investigate the factor properties and gap sequence of the Tribonacci sequence,the fixed point of the substitution σ(a,b,c)=(ab,ac,a).Let ωpbe the p-th occurrence of ω and Gp(ω)be the gap between ωpand ωp+1.We introduce a notion of kernel for each factor ω,and then give the decomposition of the factor ω with respect to its kernel.Using the kernel and the decomposition,we prove the main result of this paper:for each factor ω,the gap sequence{Gp(ω)}p≥1is the Tribonacci sequence over the alphabet {G1(ω),G2(ω),G4(ω)},and the expressions of gaps are determined completely.As an application,for each factor ω and p∈N,we determine the position of ωp.Finally we introduce a notion of spectrum for studying some typical combinatorial properties,such as power,overlap and separate of factors.

Key wordsthe Tribonacci sequence;gap sequence;kernel word;combinatorial property; spectrum

2010 MR Subject Classi fi cation11B85;68Q45

∗Received October 11,2014;revised March 4,2015.The work described in this paper was supported by grants from the National Science Foundation of China(11431007;11271223;11371210).

†Corresponding author:Zhiying WEN.

1 Introduction

The combinatorial structure of a sequence is often revealed by the research of the set of its factors,see Lothaire[14,15],Berstel[4,5]and[16,18].As a classical example over a binary alphabet,the combinatorial properties of the Fibonacci sequence are of great interest in many aspects of mathematics and computer science etc.,see for instance[3,11].The Tribonacci sequence,which is a natural generalization of the Fibonacci sequence,was studied extensively by many authors,see[13,17,19,20].

Wen and Wen[22]de fined and studied a class of factors of the Fibonacci sequence,called singular word,which play an important role in the studies of factor properties of the Fibonacci sequence.The above results were generalized to Sturmian sequences by Cao and Wen[9],and to the Tribonacci sequence by Tan and Wen[21].

Fixed a factor ω of the Fibonacci sequence,Huang and Wen[12]de fined the gap sequence induced by ω,and determined the structure of gap sequence by using results on singular words of the Fibonacci sequence.The main aim of this article is to extend the results above from the Fibonacci sequence to the Tribonacci sequence.However,in the studies of the gap sequence of the Tribonacci sequence,the techniques of singular words fail.To overcome this difficulty,we introduce a new notion called kernel words of the Tribonacci sequence.

This paper is organized as follows.

Section 1 is devoted to the introduction and preliminaries.In Section 2,we de fi ne the notion“kernel word”and study its properties.Section 3 is devoted to study the gaps and gap sequence of kernel words.In Section 4,we give the relation of a factor and its kernel,i.e.,the decomposition of a factor with respect to its kernel,and prove the decomposition is unique.In Section 5,using the results of Sections 3 and 4,we prove the main result of this article:for each factor ω,the gap sequence{Gp(ω)}p≥1is the Tribonacci sequence over the alphabet {G1(ω),G2(ω),G4(ω)},and the expressions of gaps are determined completely.Section 6 will be devoted to some applications of the main theorem:determining the expression of position of each ωp,where ωpis the p-th occurrence of ω;some combinatorial properties of the factors,such as the power,overlap and separate property for any factor ω.

1.1Basic Notations

Let A={a,b,c}be a three-letter alphabet.A word is a finite string of elements in A.The set of all finite words over A is denoted by A∗.We denote by ε the empty word.The concatenation of two words ν=x1x2···xrand ω=y1y2···ynis the word x1x2···xry1y2···yn,denoted by ν∗ω or νω.The set A∗is thus endowed with the structure of a monoid,and is called the free monoid generated by A.Let Γ denote the free group generated by A.Let ANbe the set of one-sided in finite words.

For a finite word ω=x1x2···xn,the length of ω is equal to n and denoted by|ω|.We denote by|ω|a(resp.|ω|b,|ω|c)the number of letters of a(resp.b,c)occurring in ω.The i-th conjugation of ω is the word Ci(ω):=xi+1···xnx1···xiwhere 0≤i≤n−1.The mirror wordof ω is de fined to beA word ω is called a palindrome if

Let τ=x1···xnbe a finite word(or τ=x1x2···be a sequence).For any i≤j≤n,de fi ne τ[i,j]:=xixi+1···xj−1xj.That means τ[i,j]is the factor of τ of length j−i+1,starting from the i-th letter and ending to the j-th letter.By convention,we note τ[i]:=τ[i,i]=xiand τ[i,i−1]:=ε.Word ω=τ[i,j]is said to occur at position i in τ.We say also that ω is a factor of τ,denoted by ω≺τ.We say that ν is a prefix(resp.suffix)of a word ω,and writeν⊳ω(resp.ν⊲ω)if there exists u∈A∗such that ω=νu(resp.ω=uν).

We denote by ω−1the inverse word of ω,that is,This only makes sense in Γ.But if ν is a prefix(resp.u is a suffix)of ω,we can write ν−1ω=u(resp.ωu−1=ν),with ω=νu.This makes sense in A∗.

1.2The Tribonacci Sequence

The Tribonacci sequence T∝is the fixed point beginning with a of the Tribonacci substitution σ:A∗→A∗de fined over A∗by σ(a)=ab,σ(b)=ac,σ(c)=a,As we know,σ(abc)=σ(a)σ(b)σ(c).The m-th iteration of σ is σm(a)=σm−1(σ(a)),m≥2 and we denote Tm=σm(a).We de fi ne σ0(a)=a,σ0(b)=b and σ0(c)=c.

The positive integer tm:=|Tm|is called the m-th Tribonacci number.Obviously,

•T0=a,T1=ab,T2=abac,Tm=Tm−1Tm−2Tm−3for m≥3;

•t0=1,t1=2,t2=4,tm=tm−1+tm−2+tm−3for m≥3.

We denote by δmthe last letter of the factor Tm,then δm=a(resp.b,c)for m≡0(resp.1,2)mod 3.For more properties of the sequence,we refer to[2,6,8,19-21].

1.3Gaps and Gap Sequence

Let ω be a factor of the Tribonacci sequence T∝=x1x2···,then it occurs in the sequence in finitely many times,which we arrange by the sequence{ωp}p≥1,where ωpdenotes the p-th occurrence of ω.Let the length of ω be n,and let ωp=xi+1···xi+n,ωp+1=xj+1···xj+n,the gap between ωpand ωp+1,denoted by Gp(ω),is de fined by

The sequence{Gp(ω)}p≥1is called the gap sequence of the factor ω,by convention,we de fi ne G0(ω)as the prefix of T∝before ω1.

For instance,G1(aba)=c(separated),G2(aba)=ε(adjacent)and G4(aba)=a−1(overlapped).When ωpand ωp+1are overlapped,the overlapped part is the word xj+1···xi+n.We take its inverse word as the gap Gp(ω).

The main result in this paper is:for any factor ω,the gap sequence{Gp(ω)}is the Tribonacci sequence on{G1(ω),G2(ω),G4(ω)}.In fact,We give also the expressions of each gap Gp(ω),so we determine the structure of gap sequence completely.

An equivalent concept of“gap”is“return word”introduced by Durand[10],the gap words de fined in this paper di ff er only by a prefix ω from the return words.We adopt“gap”since it will be convenient for our discussions.Durand proved that a sequence is primitive substitutive if and only if the set of its return words is finite.Vuillon[23]proved that an in finite word τ is a Sturmian sequence if and only if each non-empty factor ω≺τ has exactly two distinct return words;then Justin and Vuillon[13]extended the result to the episturmian sequence,that is,an in finite word τis a strict-episturmian sequence if and only if each non-empty factor ω≺τ has exactly n distinct return words,where n is the cardinality of the alphabet.

2 Kernel Word

In[12],starting from the singular words introduced in[22],the authors find that for any factor ω of the Fibonacci sequence,there exists a unique singular word sk(ω)called singular kernel of ω,such that sk(ω)occurs only once in ω.This property play an important role in the research on gap sequence of the Fibonacci sequence.We may de fi ne also singular words for the Tribonacci sequence[21],but they do not posses the property above.So instead of the singular words,we are going to look for a set of factors possessing the similar properties.Here we introduce the following two notions:kernel set of the sequence and kernel of a factor.

De finition 2.1(Kernel number)Let{km}m≥1be the sequence of positive integers with

The number kmis called the m-th kernel number.

Remark 2.2We can see that k3=t0=1 and k4=t1=2.By induction,we have km+3＜tmfor m≥2.

De finition 2.3(Kernel word)Let{Km}m≥1be the sequence of factors with

We call Kmthe kernel word with order m.

Remark 2.4Notice that Tm−3[1,km−1]is the prefix of Tm−2with length km−1,δm−1is the last letter of Tm−1,and Tm=Tm−1Tm−2Tm−3,so

that is for any m∈N,the word Kmis a factor of T∝.

De finition 2.5(Kernel set)De fi ne K:={Km}m≥1⊂A∗.

The set Kis called the kernel set of the Tribonacci sequence.

Proposition 2.6(Basic Properties)

(1)Tm=Tm−1Tm−2Tm−3for m≥3;

(2)tm=tm−1+tm−2+tm−3for m≥3;

(3)Km=δm−1Tm−4Km−3[2,km−3]for m≥4;

(4)Km=δm−1Tm−4Tm−5[1,km−3−1]for m≥5;

(5)km=km−3+tm−4for m≥4;

(6)km=km−1+tm−5for m≥5.

Here are the first few values of these sequences:

•{Tm}m≥0=a,ab,abac,abacaba,abacabaabacab,abacabaabacababacabaabac···.

•{tm}m≥0=1,2,4,7,13,24,44,81···.

•{Km}m≥1=a,b,c,aa,bab,cabac,aabacabaa,babacabaabacabab···.

•{km}m≥1=1,1,1,2,3,5,9,16,29,53···.

As the case of the Fibonacci sequence[22],kernel words of T∝are also palindrome.

Proposition 2.7(Palindrome)Each kernel word Kmis a palindrome.

ProofThe property is easy to check for m=1,2,3.Now we prove the conclusion for m≥4.

Claim 1Km−3⊳Kmand Km−3⊲Km.

By de finitions of δmand Km,we have Tm−4[tm−4]=δm−1=Km−3[1],so

Notice that Tm−6⊳Tm−3,Km−3=δm−4Tm−6[1,km−3−1]and δm−4=δm−1,then

Claim 2σ(Km+1[2,km+1−1])=Km+2[2,km+2−1]a−1.

The claim can be proved easily by induction and relation(3)of Proposition 2.6.

From Claim 1 and by induction,we have that the first and last letter of Kmare both δm−1.We get thus

So Claim 3 is equivalent to

When m=4,the property holds.By induction,assume the property holds for m≥4.By Claim 2 we have that σ(Km+1[2,km+1−1])=Km+2[2,km+2−1]a−1.Therefore

This means the property holds for m+1.

The proof of Proposition 2.7 ends immediately by using inductively Claim 3.

3 Gap Sequence with Respect to the Kernel Word Km

Let Kmbe a kernel word which is a factor of T∝by Remark 2.4.We denote by Km,pthe p-thoccurrence of Kmfor p≥1.The aim of this section is to prove that the gap sequence {Gp(Km)}p≥1is still a Tribonacci sequence over the alphabet{G1(Km),G2(Km),G4(Km)}.We are going to prove the conclusion above by proving the following three propositions.

Proposition 3.1(Expression of G0(Km))The prefix of the Tribonacci sequence T∝before the word Km,1is G0(Km)=Tm−1δ−1m−1for m≥1.

Proposition 3.2(First four gaps of kernel word,m≥3)

(1)G1(Km)=G3(Km)=Tm−2[km,tm−2]Tm−3Tm−1[1,tm−1−1];

(2)G2(Km)=Tm−2[km,tm−2]Tm−1[1,tm−1−1];

(3)G4(Km)=Tm−1[km,tm−1−1].

Theorem 3.3(Gaps sequence of kernel word)For any m≥1,we have

where x1x2···is the Tribonacci sequence T∝over{G1(Km),G2(Km),G4(Km)}.

Theorem 3.3 means:for any m≥1,the gap sequence{Gp(Km)}p≥1is the Tribonacci sequence over the alphabet{G1(Km),G2(Km),G4(Km)}.

3.1Proof of Proposition 3.1

Lemma 3.4Let m≥3,Tmoccurs exactly twice in TmTm(resp.Tm−1Tm,Tm−1Tm−2Tm).More precisely,it occurs as prefix and suffix of the word.

ProofNotice that when m=3,Tm=abacaba,TmTm=abacabaabacaba,and

It is easily to check that the properties hold.Assume the conclusions hold for m=n where n≥3,we will prove that the conclusions hold for m=n+1.

Since Tn+1Tn+1=TnTn−1Tn−2TnTn−1Tn−2,by the induction hypothesis and TnTn−1Tn−2⊳TnTn,all possible positions of Tnin TnTn−1Tn−2Tnare 1,tn+1 and tn+1+1.So all possible positions of Tn+1(=TnTn−1Tn−2)in Tn+1Tn+1are at 1(prefix),tn+1 and tn+1+1(suffix).

It is easy to check that Tn+1occurs at the positions 1 and tn+1+1 in Tn+1Tn+1.Suppose Tn+1occurs at the position tn+1,then

That is,TnTn−1Tn−2=Tn−1Tn−2Tn.But the last letter of these two words are δn−2and δnrespectively,which are distinct by the de finition of δm,we get thus a contradiction.So Tn+1occurs in Tn+1Tn+1only twice as prefix and suffix(at positions 1 and tn+1+1).

The other two conclusions could be obtained by an analogous argument.

Remark 3.51.Lemma 3.4(1)is still valid for m=0,1,2.

2.When m=1,2,Lemma 3.4(2)does not hold,in this case,Tmoccurs in Tm−1Tmonly once,it is a suffix of Tm−1Tm.

3.When m=2,Lemma 3.4(3)does not hold,in this case,Tmoccurs in Tm−1Tm−2Tmonly once,it is a suffix of Tm−1Tm−2Tm.

ProofSince Kmis a palindrome,Km[km]=δm−1.The letter(δm−1Tm−5Tm−4)[km]is

Moreover,the letter(δm−1Tm−5Tm−6Tm−4)[km]is

By Proposition 2.6,Km=δm−1Tm−4Tm−5[1,km−3−1].Let∆be a factor of the Tribonacci sequence,we say that Tm−4can extend to Kmin∆at the position L+1,if Tm−4occurs in∆at position L+1,and if it is preceded by the letter δm−1and followed by the word Tm−5[1,km−3−1]=Km−3[2,km−3].

On the other hand,if Kmoccurs in∆at position L,then Tm−4will occur at position L+1.Consequently,this Tm−4can extend to Kmat position L+1.

We get thus a criterion(called K-criterion)to determine whether Kmis factor of a word ∆:We first find all possible positions where Tm−4occurs in∆,then we observe these positions.Let L+1 be a possible position,if Tm−4can extend to Km,then Kmoccurs at the position L;otherwise,Kmdoes not occur at this position.The number of positions where Tm−4can extend to Kmis the occurring number of Kmin∆.

Lemma 3.7For m≥2,Kmoccurs in Tm−1Tm−2[1,km−1]only once,it is exactly the suffix of this word(at position tm−1).

ProofThe property is easy to check when 2≤m＜6.When m≥6,by Proposition 2.6(3)and(4),we see that Km=δm−1Tm−4Km−3[2,km−3]and

By the K-criterion,in order to find all positions of Kmin Tm−1Tm−2[1,km−1],we find all possible positions of Tm−4in Tm−1[2,tm−1]Tm−4,then discuss whether these Tm−4can extend to a Kmor not.

Using Tm=Tm−1Tm−2Tm−3four times on Tm−1,Tm−2and Tm−3,respectively,

Using Lemma 3.4,all possible positions of Tm−4occur in the word Tm−1[2,tm−1]Tm−4are shown by Fig.3.1,where[i]means the position of the i-th occurrence of Tm−4,i=1,2,···,7.We are going to prove that only the 7-th position is valid.

Step 1Since Tm−3⊳Tm−2and km≤tm−3,Tm−2[1,km−1]=Tm−3[1,km−1],then

By the de finition of Km,the suffix word δm−1Tm−3[1,km−1]is Km.That means,kernel word Kmis the suffix of Tm−1Tm−2[1,km−1].

In this case,the Tm−4in Kmlocates at position[7].

Step 2By the K-criterion,we exclude all other possible positions.

(1)If Tm−4at position[2]or[6],the letter before Tm−4is δm.

(2)If Tm−4at position[4],the letter before Tm−4is δm−2.

All of them contradict the first letter of Kmis δm−1,so the Tm−4occurs at positions[2],[4]or[6]can’t extend to a Km.

(3)By Lemma 3.6,Km/⊳δm−1Tm−5Tm−6Tm−4,so the Tm−4occurs at positions[1]or[5]can’t extend to a Km.

(4)By Lemma 3.6,Km/⊳δm−1Tm−5Tm−4,so the Tm−4occurs at position[3]can’t extend to a Km.

Proof of Proposition 3.1For m=1,K1=a,G0(a)=ε=T0[1,t0−1].

For m≥2,notice that

Using Lemma 3.7,we see that Kmoccurs in

only once(as suffix).So T∝[tm−1,tm−1+km−1]is the first occurrence of Km,i.e.,Km,1.

Then by the de finition of G0(Km),

Corollary 3.8|G0(Km)|=tm−1−1.

Corollary 3.9Kmoccurs in G0(Km)Kmonly once.It is exactly the suffix of this word.

3.2Proof of Proposition 3.2

We are going to prove Proposition 3.2.In order to prove it,we need a lemma.

Lemma 3.10Let m≥3 and denote

(1)∆1=δm−1Tm−2Tm−3Tm−1Tm−3[1,km−1],

(2)∆2=δm−1Tm−2Tm−1Tm−3[1,km−1],

(3)∆3=δm−1Tm−1Tm−3[1,km−1],

The word Kmoccurs in∆ionly twice.More precisely,as prefix and suffix of the word∆i.

ProofAs an example,we only prove Lemma 3.10(1).The conclusions are easy to check for 3≤m＜6.When m≥6,the proofs are similar with Lemma 3.7.

By the de finition of Kmand Proposition 2.6,we have that:for m≥5,

so Tm−3[1,km−1]=Tm−4Tm−5[1,km−3−1].That means,

Using Tm=Tm−1Tm−2Tm−3repeatedly,we can see that

Using Lemma 3.4,all possible positions of Tm−4occur in the word Tm−2Tm−3Tm−1Tm−4are shown by Fig.3.2,where[i]means the position of the i-th occurrence of Tm−4,i=1,2,···,14.We are going to prove that only the 1-st and the 14-th positions are valid.

Step 1Using Tm=Tm−1Tm−2Tm−3twice on Tm−2and Tm−3,respectively,

By Proposition 2.6,the prefix word δm−1Tm−4Tm−5[1,km−3−1]is Km.That means,kernel word Kmis the prefix of δm−1Tm−2Tm−3Tm−1Tm−3[1,km−1].

In this case,the Tm−4occurs at position[1].

Since Tm−1=Tm−1[1,tm−1−1]∗δm−1,we have

By the de finition of Km,the suffix word δm−1Tm−3[1,km−1]is Km.That means,kernel word Kmis the suffix of δm−1Tm−2Tm−3Tm−1Tm−3[1,km−1].

In this case,this Tm−4above occurs at position[14].

Step 2By the K-criterion,we exclude all other possible positions.

(1)If Tm−4occurs at positions[3]or[7]or[9]or[13],the letter before Tm−4is δm.

(2)If Tm−4occurs at positions[5]or[11],the letter before Tm−4is δm−2.

All of them contradict the first letter of Kmis δm−1,so the Tm−4occurs at these positions can’t extend to a Km.

Using Lemma 3.4 and a similar way in the proof of Lemma 3.10,we get

Proof of Proposition 3.2By formula(3.5),Km,1=T∝[tm−1,tm−1+km−1].It is easy to check that

Using Lemma 3.10(1),Kmoccurs in the word T∝[tm−1,tm−1+tm+km−1]only twice as prefix and suffix,so Γ1=Km,2.Associating with Proposition 3.1,we get

That means,

The proofs of G2(Km),G3(Km)and G4(Km)could be obtained by an analogous argument as the proof of G1(Km)and we omit the details.We only list the positions of the first fi ve terms of the sequence{Km}m≥1which will give the four gaps in Proposition 3.2:

(1)Km,1=T∝[tm−1,km+3−1];

(2)Km,2=T∝[tm−1+tm,tm+km+3−1];

(3)Km,3=T∝[tm−1+tm+1,tm+1+km+3−1];

(4)Km,4=T∝[tm+2,tm+2+km−1];

(5)Km,5=T∝[tm+2+tm−1,tm+2+km+3−1].

This means:

(1)G1(Km)=T∝[km+3,tm−1+tm−1]=Tm−2[km,tm−2]Tm−3Tm−1[1,tm−1−1];

(2)G2(Km)=T∝[tm+km+3,tm−1+tm+1−1]=Tm−2[km,tm−2]Tm−1[1,tm−1−1];

(3)G3(Km)=T∝[tm+1+km+3,tm+2−1]=Tm−2[km,tm−2]Tm−3Tm−1[1,tm−1−1];

(4)G4(Km)=T∝[tm+2+km,tm+2+tm−1−1]=Tm−1[km,tm−1−1].

Corollary 3.12Let m≥3,then

(1)|G1(Km)|=tm−km;

(2)|G2(Km)|=tm−2+tm−1−km;

(3)|G4(Km)|=tm−1−km.

Corollary 3.13Kmoccurs in KmG1(Km)Km(resp.KmG2(Km)Km,KmG4(Km)Km)only twice,they are exactly the prefix and suffix of this word.

A word ν is called“located at the center in the word ω”if there exist wordsµ1andµ2such that ω=µ1νµ2and|µ1|=|µ2|.

Proposition 3.14For any m≥1,G1(Km),G2(Km)and G4(Km)are palindromes.

ProofThe proposition is easy to check for m=1.Now let m≥2.By Proposition 2.6(6),km+5−tm−tm−1=km+4−tm−1=km+3＞0,so km+5＞tm−1+tm.By Remark 2.2,tm−1+tm＞km+3.Notice that by the de finition of Kmand Proposition 3.2,we have

By Proposition 2.6,

since|δm+1T∝[1,km+3−1]|=km+3,we see that G1(Km)is located at the center in Km+5,which results that G1(Km)is a palindrome since Km+5is a palindrome.

By an analogous argument as above,we can prove that G2(Km)is located at the center in Km+6,which concludes G2(Km)is a palindrome.

From the de finitions of G4(Km)and Km,we have

therefore G4(Km)is located at center of Km+3,so G4(Km)is a palindrome.

3.3Proof of Theorem 3.3

Lemma 3.15(Decomposition of T∝,Tan and Wen[21],Theorem 3.1)

Let m≥1 be fixed.De fi ne a substitution φm:A→A∗by φm(a)=G1(Km),φm(b)= G2(Km)and φm(c)=G4(Km).Let alphabet Am:={G1(Km),G2(Km),G4(Km)}={α,β,γ}.For a standard word Tn=σn(a)and its mirror wordwe denote Tn(Am):=φm(Tn)andthe k-th standard word and its mirror word over alphabet Am.If there is no confusion,we simply write Tnandfor short.

The following lemma gives a decomposition of Tnwhich describes the gaps of Km’s.

Lemma 3.16For n≥m,we have

where x1,x2,···xtn−m∈Am,and x1x2···xtn−m=Tn−mis the k-th standard word over alphabet Am.

ProofLet m≥3,(1)-(3)below show the lemma holds for n=m,m+1,m+2.

(1)When n=m,the word Tn−m=T0is α=x1over Am.So the left side of equation(3.24)is equal to KmG1(Km)over A.In fact,

(2)When n=m+1,the word Tn−m=T1is αβ=x1x2over Am.So the left side of equation(3.24)is equal to KmG1(Km)KmG2(Km)over A.In fact,

(3)When n=m+2,the word Tn−m=T2is αβαγ=x1x2x3x4over Am.So the left side of equation(3.24)is equal to KmG1(Km)KmG2(Km)KmG1(Km)KmG4(Km)over A.In fact,

(4)When n≥m+3,assume the conclusion holds for n−1,n−2 and n−3,then

where x1x2···xtn−m−1(resp.y1y2···ytn−m−2,z1z2···ztn−m−3)is Tn−m−1(resp.Tn−m−2,Tn−m−3)over Am.So x1x2···xtn−m−1y1y2···ytn−m−2z1z2···ztn−m−3is Tn−mover Am.

By(1)-(4),the proposition holds for all n≥m and m≥3.

By an analogous argument as above,the theorem is easy to prove for m=1,2.

By Propositions 2.7 and 3.14,Km,G1(Km),G2(Km)and G4(Km)are palindromes,so Lemma 3.16 is equivalent to

Corollary 3.17For n≥m,the wordhave relation

where x1x2···xtn−misover{G1(Km),G2(Km),G4(Km)}.

Proof of Theorem 3.3By Proposition 3.14,Lemma 3.15 and Corollary 3.17,

where xn,1xn,2···xn,tn−misover the alphabet{G1(Km),G2(Km),G4(Km)}.

By Proposition 2.6,km+5=km+4+tmfor m≥0,then

By Proposition 3.1,G0(Km)Km=T∝[1,km+3−1]too,so

By Corollaries 3.9 and 3.13,all factor Kmof T∝appear in formula(3.32).Thus by Lemma 3.15

That means the gap sequence is the Tribonacci sequence T∝over Am.

4 Uniqueness of Kernel Decomposition

Now we turn to give two types of“kernel decomposition”for each factor ω:

•The weak type(see De finition 4.5 below)shows that the relation between ω and Ker(ω);

•The strong type(see De finition 4.12 below)shows the relation between ωpand Ker(ω)pfor each p≥1,i.e.,Ker(ωp)=Ker(ω)p.

These properties play an important role in the studies:using them,we can extend Theorem 3.3 and other related properties from kernel word to an arbitrary factor.

4.1De finition of Ker(ω)

De finition 4.1(Kernel word of factor ω,Ker(ω))Let ω be a factor and let

Then Kmis called the kernel of factor ω and is denoted by Ker(ω)=Km∈K.

That means,Ker(ω)is the maximal kernel factor of ω in the sense above.

•Ker(T3)=Ker(abacaba)=c,Ker(T4)=Ker(abacabaabacab)=aa.

Notice that K1=a,K2=b and K3=c,so each factor ωε contains at least one kernel word.By the de finition,the kernel Ker(ω)is unique in the following sense:if both Kmand Knare kernel words of ω,then m=n.

Let Kmbe the kernel of ω,if Ker(ω)=Kmoccurs in ω only once?Theorem 4.3 will give an a ffi rm answer.

4.2Weak Type of Decomposition

Lemma 4.2(Property of Gaps)For m≥1,we have

ProofFor m=1,2,K1=a,K2=b,K3=c,K4=aa,K5=bab,and

(1)G1(K1)=b,G2(K1)=c,K1G4(K1)K1=aa;

(2)G1(K2)=aca,G2(K2)=aa,K2G4(K2)K2=bab.

So the conclusions hold for m=1,2.By the proof of Proposition 3.14,Km+3=KmG4(Km)Kmfor m≥3,it remains to prove the first two terms for m≥3.

By Proposition 3.2,for p=1,2,we have

which prove the conclusions hold.

Theorem 4.3Let Kmbe the kernel of ω,then Kmoccurs exactly once in ω.

ProofSuppose kernel word Kmoccurs in ω more than once,then by Theorem 3.3,the gap between two consecutive Kmwill be one of the three words:G1(Km),G2(Km)or G4(Km).So ω will contains one factor KmGi(Km)Km(i=1,2 or 4),by Lemma 4.2,ω will contain a word Knwith n＞m,which contradicts the hypotheses Ker(ω)=Km.

Corollary 4.4Let Kmbe the kernel of ω,then for each q,there is at most one positive integer(denoted by p)such that Km,qoccurs in ωp.

ProofAssume Km,qoccurs in ωp1and ωp2,wherethen ω1=u1Km,qv1,andBy the equality ω=u1Kmv1=u2Kmv2,it is easy to see that there will be two different Kmoccurring in ω,which contradicts Theorem 4.3.

Let ω be a factor,and Kmbe its kernel,by Theorem 4.3,there exist uniquely two words µ1(ω)andµ2(ω)depending only ω,such that

De finition 4.5(Weak type of decomposition)Let ω be a factor,decomposition(4.4)above is called the weak type of decomposition of ω.

Let K′⊂K be a proper subset of K.Similarly to the de finition of kernel set,for a factor ω,let m=max{m:Km≺ω,Km∈K′}and Ker′(ω)=Km.Then there exists ω such that either ω has no kernel word,or Ker′(ω)occurs more than once in ω.

Proposition 4.6(Minimum)In the sense above,we see that the kernel set K is minimal.

ProofLet K′be a proper subset of K and let

4.3Strong Type of Decomposition

Lemma 4.7Let m≥1,then

ProofBy the de finition of kernel word and Proposition 3.2,Km=δm−1Tm−3[1,km−1]and G4(Km)=Tm−1[km,tm−1−1].So

This means the conclusions hold.

Remark 4.8The i-th conjugation of ω=x1···xnis de fined by the word

Using this de finition,we have G4(Km)Km=Ckm(Tm−1),that is,the word G4(Km)Kmis exactly the km-conjugation of the word Tm−1.

Proposition 4.9Kmoccurs(as a factor of the Tribonacci sequence T∝)always preceded by the wordand followed by the word

ProofBy Theorem 3.3,we only need to prove the follow properties:

The other proofs could be obtained by analogous arguments as the case above.

Now ωpis the p-th occurrence of ω in T∝,then there exists Km,q(the q-th occurrence of Km)occurs in ωp,and we write Ker(ωp)=Km,q.We will prove Ker(ωp)=Km,p.

Proposition 4.10Let ω be a factor and Km=Ker(ω).Then for any q,there exists p such that Km,q=Ker(ωp).

ProofSince Km≺ω,there exists integers r and p(r)such that Km,roccurs in ωp(r).By decomposition(4.4),ωp(r)=µ1(ω)Km,rµ2(ω).

In this case,by Proposition 4.9,Kmoccurs always preceded by the wordµ1(ω)and followed by the wordµ2(ω),which yields the conclusion.

For m=1,2,3,it is easy to check that

For m≥4,by Proposition 3.2,G4(Km)[1,tm−4]=Tm−1[km,km+1−1].By the de finition of Km,we can see

For m=1,2,it is easy to check that

For m≥3,by Proposition 3.2,G4(Km)[1,tm−3]=Tm−1[km,km+2−1].By the de finition of Km,we can see

In Cases 2.1(resp.2.2 or 2.3),kernel word Km+3(resp.Km+1or Km+2)occurs in ω,which contradicts the hypotheses of Ker(ω)=Km.

Thus only Case 1 is possible which yields the conclusion.

By Proposition 4.10 and Corollary 4.4,we have

Theorem 4.11Ker(ωp)=Km,p.

Let ω be a factor,and Kmbe its kernel,by Theorem 4.11,there exist uniquely two words µ1(ω)andµ2(ω)depending only ω,such that

De finition 4.12(Strong type of decomposition)Let ω be a factor,decomposition(4.11)above is called the strong type of decomposition of ω.

Corollary 4.13(The expressions ofµ1(ω)andµ2(ω))For each ω,µ1(ω)andµ2(ω)in decompositions(4.4)and(4.11)have expressions as

where 2≤i≤tm−1+1,0≤j≤tm−1−1.

5 Structure of Gap Sequence:General Case

Using Theorem 3.3 and Theorem 4.11,we obtain the main theorem of the paper:

Theorem 5.1(Gap sequence of factor ω)For any ω≺T∝,we have

where x1x2···is the Tribonacci sequence T∝over{G1(ω),G2(ω),G4(ω)}.

Theorem 5.1 means:for any ω≺T∝,the gap sequence{Gp(ω)}p≥1is the Tribonacci sequence over{G1(ω),G2(ω),G4(ω)}.

As an example,take ω=bac,then G1(ω)=abaa,G2(ω)=aba and G4(ω)=a.

We see that the gap sequence is{Gp(ω)}p≥1=ABACABAABACABABACABAABA···,which is the Tribonacci sequence over the alphabet{A,B,C}.

From Theorem 5.1,we get immediately that

Corollary 5.2Any factor ω has exactly three distinct gaps G1(ω),G2(ω)and G4(ω).

The corollary above was proved by Justin and Vuillon for episturmian sequence[13].

Proposition 5.3(Relation between Gp(ω)and Gp(Ker(ω)),p≥1)

Let m be the integer such that Ker(ω)=Km,then

ProofThe proof of the proposition will be easy by the following diagram.

Proposition 5.4(Relation between G0(ω)and G0(Ker(ω)))

Let m be the integer such that Ker(ω)=Km,then

ProofThe proof of the proposition will be easy by the following diagram.

Corollary 5.5(Length)Let ω be a factor and Kmbe the kernel of ω.Let i,j with 2≤i≤tm−1+1,0≤j≤tm−1−1 be as in decomposition(4.4),then

(1)|G0(ω)|=i−2;

(2)|G1(ω)|=tm−2+tm−3−km+i−j−1;

(3)|G2(ω)|=tm−2−km+i−j−1;

(4)|G4(ω)|=−km+i−j−1.

ProofBy Propositions 5.3,5.4 and Corollary 4.13,we can see

(1)|G0(ω)|=|G0(Km)|−|µ1|=|G0(Km)|−tm−1+i−1=i−2;

(2)|Gp(ω)|=|Gp(Km)|−|µ1|−|µ2|=|Gp(Km)|−tm−1+i−1−j,for p≥1.

By Corollary 3.12,for m≥3,|G1(Km)|=tm−km,|G2(Km)|=tm−2+tm−1−km,|G4(Km)|=tm−1−km.So

|G1(ω)|=tm−km−tm−1+i−1−j=tm−2+tm−3−km+i−j−1;

|G2(ω)|=tm−2+tm−1−km−tm−1+i−1−j=tm−2−km+i−j−1;

|G4(ω)|=tm−1−km−tm−1+i−1−j=−km+i−j−1.

6 Some Applications

Notice that if we consider the position of ωp∈T∝,then the factors ωpand ωq(pq)are distinct.In fact,ωpshould be regarded as two variables ω and p,ω is the factor and p indicates the position of ω.

In this section,we will using our main results to study some properties of ωp:(1)Determine the position of ωpfor all ω≺T∝and p∈N,see Subsection 6.1;(2)Study some combinatorial properties of factor ωp,see Subsection 6.2.

6.1Positions of Factor ωp

Notation(1)Let N(a,p):=|T∝[1,p]|abe the number of letter a occuring in T∝[1,p].Similarly,de fi ne N(b,p):=|T∝[1,p]|band N(c,p):=|T∝[1,p]|c.

(2)Let L(ω,p)be the position of factor ωp,i.e.,ωp=T∝[L(ω,p),L(ω,p)+|ω|−1].

Theorem 6.1(Position of Km,p)For m≥3,i.e.,or b,we have

ProofBy Corollary 3.12,for m≥3,|G1(Km)|=tm−km,|G2(Km)|=tm−2+tm−1−kmand|G4(Km)|=tm−1−km.By Corollary 3.8,|G0(Km)|=tm−1−1.Then

Remark 6.2The positions corresponding to m=1,2 are respectively

Theorem 6.3(Position of ωp+1)Let

where i is de fined in Corollary 4.13.

ProofBy Corollary 4.13 and equation(4.11),

Taking ω=bac,p=9 for example,we can calculate L(ω,p+1)by the following steps.

Step 1We have T∝[1,9]=abacabaab,so N(a,p)=5,N(b,p)=3,N(c,p)=1.

Step 2Since Ker(bac)=c=K3,then m=3,tm−2=2,tm−1=4,tm=7.

Step 3By bac=(caba)[i,4]∗c∗(abac)[1,j],we see i=3.

Step 4So L(ω,p+1)=5∗7+3∗(2+4)+1∗4+3−1=35+18+4+3−1=59.

6.2Combinatorial Properties of Factors

Let P be a property and ω a factor.If ωphas this property,we say ωp∈P.We say the factorω∈P if there exists an index p∈N such that ωp∈P,but in this case,we do not know where is the position of ωp∈T∝,so we wish to determine the set{(ω,p)|ωp∈P,ω≺T∝,p∈N}.For instance,we consider P is“property of square factor”,that is,if ω∈P,then there exists p such that ωpωp+1∈T∝.Let ω=aba∈T∝,then ω1=T∝[1,3],ω2=T∝[5,7]and ω3=T∝[8,10].So ω1P,ω2∈P,and ω∈P.By the example,we are led naturally to study combinatorial properties of factor ω of the following two types:

Local QuestionDetermine all factors ω∈T∝such that ω∈P,i.e.,there exists p∈N such that ωp∈P.

Global QuestionDetermine all factors ω∈T∝and all indices p such that ωp∈P.More precisely,de fi ne the spectrum of P by

By the de finition above,the global question is equivalent to determine the spectrum of the property P.By the de finition above,the spectrum of the property P depends on the two independent variables ω and p.For a given factor ω,the spectrum Λ(P)will give all indices p such that ωp∈P;and for a given index p,the spectrum Λ(P)will give all factors ω such that ωp∈P.The local question is equivalent to determine the projection of the spectrum Λ(P)on factor space.

We will study mainly some combinatorial properties for both local question and global question,such as adjacent property,separated property and overlapped property of factors.From our knowledge,all previous studies on combinatorial over words concern with only local question,in fact,“global question”is much more difficult than“local question”.

NotationFor the convenience,we give some notations.

(1)Γa={p∈N|T∝[p]=a};

(2)Γb={p∈N|T∝[p]=b};

(3)Γc={p∈N|T∝[p]=c};

(4)Γaa={p∈N|T∝[p]=a,T∝[p+1]=a},etc.

It is easy to see that Γa⊔Γb⊔Γc=N and Γaa⊔Γab⊔Γac=Γa,etc.

By Theorem 5.1,we get immediately

Lemma 6.4Let ω∈T∝,then

(1)Gp(ω)=G1(ω)⇔p∈Γa;

(2)Gp(ω)=G2(ω)⇔p∈Γb;

(3)Gp(ω)=G4(ω)⇔p∈Γc.

To prove combinatorial properties of the factors(power,separated,overlapped),we divide all factors into several types according to lengths of gaps.

De finition 6.5(Types)The sets Tp(p=1,···,7)are de fined as follows:

T1:={ω∈T∝|3−tm−1≤i−j＜km−tm−2−tm−3+1};

T2:={ω∈T∝|i−j=km−tm−2−tm−3+1};

T3:={ω∈T∝|km−tm−2−tm−3+1＜i−j＜km−tm−2+1};

T4:={ω∈T∝|i−j=km−tm−2+1};

T5:={ω∈T∝|km−tm−2+1＜i−j＜km+1};

T6:={ω∈T∝|i−j=km+1};

T7:={ω∈T∝|km+1＜i−j≤tm−1+1}.

Corollary 6.6For m≥2,all factors with Ker(ω)=Kmcan be divided into seven disjoint types:

ProofSince 2≤i≤tm−1+1 and 0≤j≤tm−1−1,then 3−tm−1≤i−j≤tm−1+1.By Proposition 5.5,we see

|G1(ω)|=tm−2+tm−3−km+i−j−1＞0⇔i−j＞km−tm−2−tm−3+1;

|G2(ω)|=tm−2−km+i−j−1＞0⇔i−j＞km−tm−2+1;

|G4(ω)|=−km+i−j−1＞0⇔i−j＞km+1.

Furthermore,

which yields the corollary.

•Power Property

Let ω∈T∝.We say that ω∈Pi(i≥1)if there exists p such that ωp···ωp+i≺T∝.By de finition of gaps Gp(ω),ω∈Piis equivalent to there exists p such that|Gp(ω)|,|Gp+1(ω)|,···,|Gp+i−1(ω)|are equal to zero.

Proposition 6.7(Global property for power property)

(1)Λ(P1)=(T2,Γa)⊔(T4,Γb)⊔(T6,Γc);

(2)Λ(P2)=(T2,Γaa);

(3)Λ(P1)Λ(P2)=(T2,Γab⊔Γac)⊔(T4,Γb)⊔(T6,Γc);

(4)Λ(Pi)=∅,i≥3.

ProofWe only prove conclusion(1),the others could be proved by a similar discussion.By the de finition of Λ(P1),ωp∈Λ(P1)means Gp(ω)=ε.By Lemma 6.4 and Corollary 6.6,

So Λ(P1)=(T2,Γa)⊔(T4,Γb)⊔(T6,Γc).

We have shown that the local question is equivalent to determine the projection of the spectrum Λ(P)on factor space.Thus we get the local properties(1),(2)and(4)of power property immediately.Since the di ff erence of two spectrum is not necessary a spectrum,we get the local property(3)by taking the di ff erence of sets Λ′(P1)Λ′(P2).Here is the following corollary.

Corollary 6.8(Local property for power property)

(1)Λ′(P1)=T2⊔T4⊔T6;

(2)Λ′(P2)=T2;

(3)Λ′(P1)Λ′(P2)=T4⊔T6;

(4)Λ′(Pi)=∅,i≥3.

•Separated Property

Let ω∈T∝.We say that ω∈Si(i=1,2,···)if there exists p and nonempty factors u1,···,ui−1such that ωpu1ωp+1u2···ui−1ωp+i≺T∝.If for all i∈N,ω∈Si,we say thatω∈S∝.By de finition of Gp(ω),ω∈Siis equivalent to there exists p such that|Gp(ω)|,|Gp+1(ω)|,···,|Gp+i−1(ω)|are strictly positive.

Propositions 6.9 and 6.11 could be proved by similar discussions as Proposition 6.7;Corollaries 6.10 and 6.12 could be proved by similar discussions as Corollary 6.8.

Proposition 6.9(Global property for separated property)

(1)Λ(S1)=(T3⊔T4,Γa)⊔(T5⊔T6,Γa⊔Γb)⊔(T7,N);

(2)Λ(S2)=(T3⊔T4,Γaa)⊔(T5⊔T6,Γaa⊔Γab⊔Γba)⊔(T7,N);

(3)Λ(S3)=(T5⊔T6,Γaab⊔Γaba⊔Γbaa⊔Γbab)⊔(T7,N);

(4)Λ(S4)=(T5⊔T6,Γaaba⊔Γabaa⊔Γabab⊔Γbaab⊔Γbaba)⊔(T7,N);

(5)Λ(S5)=(T5⊔T6,Γabaab⊔Γababa⊔Γbaaba)⊔(T7,N);

(6)Λ(S6)=(T5⊔T6,Γabaaba)⊔(T7,N);

(7)Λ(Si)=Λ(S∝)=(T7,N),i≥7.

Corollary 6.10(Local property for separated property)

(1)Λ′(S1)=Λ′(S2)=T3⊔···⊔T7;

(2)Λ′(S3)=···=Λ′(S7)=T5⊔T6⊔T7;

(3)Λ′(Si)=Λ′(S∝)=T7.

•Overlapped Property

Let ω∈T∝.We say that ω∈Oi(i=1,2,···)if there exists p and nonempty factors u1,···,ui−1such that ωpu−11ωp+1u−12···u−1i−1ωp+i≺T∝.If all i∈N,ω∈Oi,we say thatω∈O∝.By de finition of Gp(ω),ω∈Oiis equivalent to there exists p such that|Gp(ω)|,|Gp+1(ω)|,···,|Gp+i−1(ω)|are strictly negative.

Proposition 6.11(Global property for overlapped property)

(1)Λ(O1)=(T1,N)⊔(T2⊔T3,Γb⊔Γc)⊔(T4⊔T5,Γc);

(2)Λ(Oi)=Λ(O∝)=(T1,N),i≥2.

Corollary 6.12(Local property for overlapped property)

(1)Λ′(O1)=T1⊔···⊔T5;

(2)Λ′(O2)=Λ′(O∝)=T1.

References

[1]Araújo I M,Bruyère V.Words derivated from Sturmian words.Theor Comput Sci,2005,340:204-219

[2]Arnoux P,Rauzy G.Représentation géométrique de suites de complexité 2n+1.Bull Soc Math France,1991,119:199-215

[3]Allouche J P,Shallit J.Automatic Sequences:Theory,Applications,Generalizations.Cambridge:Cambridge Univ Press,2003

[4]Berstel J.Recent results in Sturmian words//Dassow J,Salomaa A,eds.Developments in Language Theory.Singapore:World Scienti fi c,1966:13-24

[5]Berstel J.Mot de Fibonacci,Séminaire d’informatique thérique.LITP,Paris,Année,1980/1981:57-78

[6]Berstel J.Recent results on extensions of Sturmian words.Inter J Algebra Comput,2002,12:371-385

[7]Balková L,Pelantová E,Steiner W.Sequences with constant number of return words.Monatsh Math,2008,155:251-263

[8]Chekhova N,Hubert P,Messaoudi A.Propriétés combinatoires,ergodiques et arithmétiques de la substitution de Tribonacci.J Théor Nombres Bordeaux,2001,13:371-394

[9]Cao W T,Wen Z Y.Some properties of the factors of Sturmian sequences.Theor Comput Sci,2003,304:365-385

[10]Durand F.A characterization of substitutive sequences using return words.Discrete Math,1998,179:89-101

[11]Du C F,Mousavi H,Schae ff er L,Shallit J.Decision algorithms for Fibonacci-automatic words,with applications to pattern avoidance.arxiv.1406.0670

[12]Huang Y K,Wen Z Y.The sequence of return words of the Fibonacci sequence.Theor Comput Sci,2015,593:106-116

[13]Justin J,Vuillon L.Return words in Sturmian and episturmian words.RAIRO-Theoretical Informatics and Applications,2000,34(5):343-356

[14]Lothaire M.Combinatorics on words//Encyclopedia of Mathematics and its Applications Vol 17.Reading,MA:Addison-Wesley,1983

[15]Lothaire M.Algebraic Combinatorics on Words.Cambridge:Cambridge Univ Press,2002

[16]Liu H,Wen Z Y.IFS on boundaries of homogeneous trees:WQB condition and multifractal analysis.Acta Math Sci,2010,30B(5):1514-1522

[17]Mousavi H,Shallit J.Mechanical proofs of properties of the Tribonacci word.arXiv:1407.5841v1

[18]Niu M,Wen Z Y.On the correlation dimension of the spectral measure for the m-multiplicative sequence.Acta Math Sci,2007,27B(5):862-870

[19]Rosema S W,Tijdeman R.The Tribonacci substitution.Integers:Elect J Combin Number Theory,2005,5(3):♯A13

[20]Richomme G,Saari K,Zamboni L Q.Balance and Abelian complexity of the Tribonacci word.Adv Appl Math,2010,45:212-231

[21]Tan B,Wen Z Y.Some properties of the Tribonacci sequence.European J Combin,2007,28:1703-1719

[22]Wen Z X,Wen Z Y.Some properties of the singular words of the Fibonacci word.European J Combin,1994,15:587-598

[23]Vuillon L.A characterization of Sturmian words by return words.European J Combin,2001,22:263-275