On the k-Abelian Complexity of the Cantor-like Sequence

LV Xiaotao(吕小涛)

(College of Science, Huazhong Agricultural University, Wuhan 430070, China)

Abstract: In this paper,we study the k-abelian complexity(n) of the Cantor-like sequence c,which is defined as the fixed point of the morphism σ : 110l1,00l+2 beginning with 1 for every integer l ≥2.We show that for every integer k with 1 ≤k ≤l,two factors u and v of the Cantor-like sequence which share the same prefix and suffix of length k are (k+1)-abelian equivalent if and only if they are k-abelian equivalent.Moreover,we show that the abelian complexity function and 2-abelian complexity function of the Cantor-like sequence are both (l+2)-regular.

Key words: Cantor-like sequence; k-abelian equivalence; k-abelian complexity; b-regular sequence

1.Introduction

The notion ofk-abelian equivalence,originally introduced in [8],has attracted a lot of interest recently[5,10-12,16].It is an equivalence relation which is a natural extension of the usual abelian equivalence and allows an infinite approximation of the equality of words.Thek-abelian equivalence relation has been widely studied in the following directions: analyzing the fluctuation of thek-abelian complexity of infinite words[4-5],estimating the number ofk-abelian equivalence classes,that is,k-abelian complexity[9,11],avoidingk-abelian powers[16]and so on.We continue the research of estimating the number ofk-abelian equivalence classes.Our starting point is reducing (k+1)-abelian equivalence tok-abelian equivalence.

Before giving the definition of thek-abelian complexity,we need some basic notation.Given a finite non-empty setAcalled alphabet,we denote byA∗,ANandAnthe set of finite words,the set of infinite words and the set of words of lengthnover the alphabetArespectively.Given a finite worduu1u2···unAnwithn ≥1,we denote the length ofuby|u|.The empty word will be denoted byεand we set|ε|0.For two wordsu,,the wordvis said to be a factor ofu,written byv ≺u,if there existx,such thatuxvy.Moreover,the factorvis called a prefix (resp.suffix) ofuifx(resp.y) is the empty wordε.For a worduu0u1···un-1,the prefix and suffix of lengthl(1≤l ≤n) are defined as

while forl ≤0,we define prefl(u)εand suffl(u)ε.The number of occurrences of a wordvinuis denoted by|u|v.Now we give the definitions of thek-abelian equivalence and thek-abelian complexity.

Definition 1.1Letkbe a positive integer.Two wordsu,are said to bek-abelian equivalent,writtenu ∼k v,if the following conditions hold:

1)|u|w|v|wfor every,

2) prefmin{k-1,|u|}(u)prefmin{k-1,|v|}(v) and suffmin{k-1,|u|}(u)suffmin{k-1,|v|}(v).

It is easy to check thatk-abelian equivalence is indeed an equivalence relation.

whereFω(n) is the set of all factors of lengthnoccurring inω.The 1-abelian complexity of an infinite word is also known as its abelian complexity.

The abelian complexity functions of some notable sequences,such as the Thue-Morse sequence and the Rudin-Shapiro sequence,are studied in [17] and [14],respectively.There are also many other works devoted to this subject(see [3]).

This paper is devoted to the study ofk-abelian complexity of the Cantor-like sequence

which satisfiesc01 and for everyn ≥0,1≤i ≤l

wherel ≥2 is an integer.The Cantor-like sequence c is also the fixed point of the morphismσ:110l1,00l+2beginning with 1,i.e.,cσ∞(1).

Our first result states that for every integerkwith 1≤k ≤l,the (k+1)-abelian equivalence of any two factors of the Cantor-like sequence c can be reduced to thek-abelian equivalence of such factors under certain conditions.In detail,we prove the following theorem.

Theorem 1.1Letkbe a positive integer with 1≤k ≤land letu,vbe two factors of c satisfying|u||v|.If prefk(u)prefk(v) and suffk(u)suffk(v),thenu ∼k+1vif and only ifu ∼k v.

To state our next result,we shall recall the definitions ofb-automatic andb-regular sequences.For more details,see [1] and the references therein.

Definition 1.3Letb ≥2 be an integer.Theb-kernel of an infinite sequence w(w(n))n≥0is the set of subsequences

The sequence w is called ab-automatic sequence if Kb(w) is finite.The sequence w is said to beb-regular if the Z-module generated by itsb-kernel is finitely generated.

By using Theorem 1.1,we are able to study thek-abelian complexity of c for every 2≤k ≤l+1.Here we are just concerned with the 2-abelian complexity of c,the method used in computingk-abelian complexity (3≤k ≤l+1) is similar.Actually we obtain the following result.

Theorem 1.2The 2-abelian complexity function of the Cantor-like sequence is (l+2)-regular.

Karhumäki,Saarela,and Zamboni[11]investigated thek-abelian complexity of Sturmian words and gave an characterization of ultimately periodic sequences by means ofk-abelian complexity.They also studied thek-abelian complexity of the Thue-Morse sequence,which is a 2-automatic sequence.Greinecker[7]and Parreau et al.[15]proved independently that the 2-abelian complexity of the Thue-Morse sequence is 2-regular.Our result(Theorem 1.2)gives another example whose 2-abelian complexity function is (l+2)-regular.

This paper is organized as follows.In Section 2,we study the structure of left and right special factors of the Cantor-like sequence and prove Theorem 1.1.In Section 3,we give the recurrence relations for the abelian complexity function of the sequence c.As a consequence,the abelian complexity function of the Cantor-like sequence is (l+2)-regular.In section 4,we prove Theorem 1.2.

2.The k-Abelian Equivalence of Two Factors of the Sequence c

In this section,we reduce(k+1)-abelian equivalence of factors of the Cantor-like sequence c tok-abelian equivalence of them under certain conditions.Before stating the result,we give some auxiliary lemmas.The first one states that the factor setFc(n) is closed under the reversal operator.The second one characterizes the structure of the left and right special factors of c.Recall that a factorvofωis said to be right special (resp.left special) if there exist at least two distinct lettersa,such that bothvaandvb(resp.avandbv) are factorsω.Given an infinite sequenceN,letRSω(n) (resp.LSω(n)) denote the set of all right special (resp.left special) factors ofωof lengthn.The set of all right special factors and left special factors ofωare denoted byRSωandLSωrespectively.

For everyuu0u1···un-1c(n),there exists an integeri ≥1 such thatu ≺σi(1).Therefore,

Lemma 2.2For every 1≤n ≤l,

ProofThe result follows from Theorem 1 in [13] and Lemma 2.1 directly.

Forz,,we define

Lemma 2.3[6]Let0,1}∞andu,with|u|≥|z|≥2.Supposezaybwherea,0,1}.We have

Now,we prove Theorem 1.1.

Proof of Theorem 1.1When|u|≤2k −1,by the assumptions,we haveuv.In this case,the result is trivial.In the following,we always assume that|u|≥2k.The ‘only if’part follows directly from the definition ofk-abelian equivalence.

For the ‘if’ part,we only need to show thatu ∼k vimplies that for everyc(k+1),|u|z|v|z.For this purpose,we separateFc(k+1) into two disjoint parts,i.e.,Fc(k+1)E1∪E2where

Suppose1.If suffk(z)/c(k),then by Lemma 2.3,

If prefk(z)/c(k),then by Lemma 2.3,

So,for every1,|u|z|v|z.

Now,we prove the case2.By Lemma 2.2,LSc(n)∩RSc(n){0n}for every integer[1,l+1].Since 1≤k ≤l,E2{0k+1}.By Lemma 2.3 and the assumptions of this result,

So,for every factor1∪E2,|u|z|v|zwhenu ∼k v.

We may now apply Theorem 1.1ktimes to reduce thek-abelian equivalence to the 1-abelian equivalence under the theorem’s condition.

Corollary 2.1Let 1≤k ≤landu,vbe two factors of the sequence c with|u||v|.If prefk(u)prefk(v) and suffk(u)suffk(v),thenu ∼k+1vif and only ifu ∼1v.

3.The Abelian Complexity of the Sequence c

In this section,we shall investigate the abelian complexity of the Cantor-like sequence c.

Letωω0ω1ω2··· be an infinite sequence over{0,1}.It has been proved in Proposition 2.2 of [2] that the abelian complexity ofωis related to its digit sums in the following way:for everyn ≥1,

For the digit sums of the Cantor-like sequence c,we have the following lemma.

We first deal with the casem(l+2)j+qfor some 1≤q ≤l+1.By the equation(3.3b) and the inductive assumption,for everyi ≥0,1≤q ≤l+1,

ProofThe result follows from Lemma 3.1,Corollary 3.1 and the equality (3.1).

4.The 2-Abelian Complexity of the Sequence c

In this section,we shall prove the regularity of the 2-abelian complexity of c.We start by giving the following decomposition of the 2-abelian complexity of c.

For everyx,0,1}and everyn ≥1,let

Now,we shall show the regularity of{p2(n,x,y)}n≥1for allx,0,1}.

Lemma 4.1p2(1,0,0)1 and for everyn ≥2,

Moreover,the sequence{p2(n,0,0)}n≥1is (l+2)-regular.

ProofThe initial values can be verified by enumerating all factors of length at mostl+1.Now,letn>l+1 and supposen ≤(l+2)ifor somei ≥1.

By the definition of the functionMc(n),it is obvious that|ω|1≤Mc(n −2) for every,0,0.So,p2(n,0,0)≤Mc(n −2)+1.In the following we prove the reverse inequality.

For every 0≤j ≤n −1,letWj0n-jprefj(σi(1)) which is a factor ofσi(01) and hence,a factor of c.Note that|W0|10 and it follows from Lemma 3.1 that|Wj|1Mc(j)forj1,···,n −2.If the last letter ofWjis 0,thenWjWn,0,0.Otherwise,|Wj+1|1|Wj|1ssince ‘11’ is not a factor of c.Therefore,Wj+1,0,0.This implies thatp2(n,0,0)≥Mc(n−2)+1 which proves(4.3).The regularity of the sequence{p2(n,0,0)}n≥1then follows from (4.3) and Corollary 3.1.

Lemma 4.2p2(1,0,1)p2(1,1,0)0 and for everyn ≥2,

Moreover,the sequences{p2(n,0,1)}n≥1and{p2(n,1,0)}n≥1are both (l+2)-regular.

ProofBy Lemma 2.1,for every factorwof c,its reversalis also a factor of c.Therefore,p2(n,1,0)p2(n,0,1).

Clearly,for every,0,1,1≤|ω|1≤Mc(n −1).So,p2(n,0,1)≤Mc(n −1).Next,we prove the reverse inequality.

Letibe a positive integer such thatn ≤(l+2)i.For every 1≤j ≤n −1,letWj0n-jprefj(σi(1)) which is a factor ofσi(01) and therefore,a factor of c.By Lemma 3.1,|Wj|1Mc(j) forj1,···,n −2.If the last letter ofWjis 1,thenWjWn,0,1.Otherwise,suppose thatWjends with 10mwheremis an integer with 1≤m ≤j −1.ThenWj-mWn,0,1and|Wj-m|1|Wj|1s.This implies thatp2(n,0,1)≥Mc(n −1).The result then follows from (4.4) and Corollary 3.1.

To deal with the set of factorsWn,1,1and the sequence{p2(n,1,1)}n≥1,we introduce the following two sets.

Let{g(i)}i≥0be a monotone increasing sequence of integers whose values equal to the length of the factors of c beginning and ending with 1.Let{G(i)}i≥0be the sets of the corresponding factors of lengthg(i) which begin and end with 1.For examples,g(0)1,g(1)l+2,g(2)l(l+2)+2,g(3)(l+1)(l+2)+1 andG(0){1},G(1){10l1},G(2){10l(l+2)1},G(3){10l(l+2)10l1,10l10l(l+2)1}.Then,we have the following result.

Lemma 4.3G(0){1},and for every non-negative integeri,

whereσ(G(i)):{σ(v):(i)}andwv-1u,u-1wvifwuv.

ProofThis will be done by induction oni.It is easy to check thatG(0){1},G(1){10l1},G2{10l(l+2)1},which implies (4.5) holds wheni0.Suppose (4.5) holds fori<3j(j ≥1).Next we shall prove the results for 3j ≤i<3(j+1).The proof in this step will be separated into the following three cases.

Case 1i3jfor some 1≤j ≤i −1.By induction,

Sinceσ(1)10l1 and every element inG(j)begins and ends with 1,for every(i),there exists(j) such thatU(10l)-1σ(u) orUσ(u)(0l1)-1.Otherwise,suppose there is anotherU′(i) which is not in the forms of (10l)-1σ(u) orσ(u)(0l1)-1.Consider the pre-image ofU′,i.e.,the shortestu′satisfyingU′≺σ(u′).By the definition of the morphismσ,the factoru′is unique.Then,u′/(j −1)∪G(j) andg(j −1)<|u′|

Case 2i3j+1 for some 1≤j ≤i −1.By induction,

With a similar argument in the Case 1,we obtain that:

Case 3i3j+2,for some 1≤j ≤i −1.By induction,G(i −1)σ(G(j)).For every(j),(j+1),|u|g(j)

Corollary 4.1g(0)1,and for everyn ≥0,

Corollary 4.2For everyi ≥0 andu,(i),|u|1|v|1.

By Corollary 4.2 and (4.1),for everyn ≥1,we have

The following lemma proves the regularity of the sequence{p2(n,1,1)}n≥1.

Lemma 4.4p2(1,1,1)1,p2(i,1,1)0 fori2,···,l+1 and for everyn ≥1,0≤j ≤l+1,

Moreover,the sequence{p2(n,1,1)}n≥1is (l+2)-automatic.

ProofThe initial values can be proved by enumerating all the factors of length at mostl+1.By the recursive formula given in Corollary 4.1,for everyi ≥0,g(i) mod (l+2)0,1,2}.Therefore,for everyn ≥1 and 3≤j ≤l+1,W(l+2)n+j,1,1∅,which impliesp2((l+2)n+j,1,1)0.The equality (4.6d) is proved.

Now,we verify the equality(4.6a).Clearly,ifng(i)for somei ≥0,thenp2(n,1,1)1 and by Corollary 4.1,(l+2)n(l+2)g(i)g(3i+1).Hence,p2((l+2)n,1,1)1p2(n,1,1).In turn,ifp2((l+2)n,1,1)1,then (l+2)ng(j) for somej ≥1.Using Corollary 4.1 again,ng(j)/(l+2)g((j −1)/3).Therefore,p2(n,1,1)1p2((l+2)n,1,1).

The remaining two equalities can be proved in the same way.

Proof of Theorem 1.2By the equalities (4.2),(4.3) and (4.4),for everyn ≥2,

The result follows from Lemma 4.1,Lemma 4.2 and Lemma 4.4.