类康托序列的k-Abelian复杂度.pdf

应用数学MATHEMATICA APPLICATA2023,36(4):1100-1108On the k-Abelian Complexity of theCantor-like SequenceLV Xiaotao(吕小涛)(College of Science,Huazhong Agricultural University,Wuhan 430070,China)Abstract:In this paper,we study the k-abelian complexity P(k)c(n)of the Cantor-likesequence c,which is defined as the fixed point of the morphism :1 7 10l1,0 7 0l+2beginning 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 suffixof 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 functionof the Cantor-like sequence are both(l+2)-regular.Key words:Cantor-like sequence;k-abelian equivalence;k-abelian complexity;b-regularsequenceCLC Number:O157AMS(2010)Subject Classification:11B85;68R15Document code:AArticle ID:1001-9847(2023)04-1100-091.IntroductionThe notion of k-abelian equivalence,originally introduced in 8,has attracted a lot ofinterest recently5,1012,16.It is an equivalence relation which is a natural extension of theusual abelian equivalence and allows an infinite approximation of the equality of words.Thek-abelian equivalence relation has been widely studied in the following directions:analyzingthe fluctuation of the k-abelian complexity of infinite words45,estimating the number ofk-abelian equivalence classes,that is,k-abelian complexity9,11,avoiding k-abelian powers16and so on.We continue the research of estimating the number of k-abelian equivalence classes.Our starting point is reducing(k+1)-abelian equivalence to k-abelian equivalence.Before giving the definition of the k-abelian complexity,we need some basic notation.Given a finite non-empty set A called alphabet,we denote by A,ANand Anthe set offinite words,the set of infinite words and the set of words of length n over the alphabet Arespectively.Given a finite word u=u1u2un Anwith n 1,we denote the length of uby|u|.The empty word will be denoted by and we set|=0.For two words u,v A,theword v is said to be a factor of u,written by v u,if there exist x,y Asuch that u=xvy.Moreover,the factor v is called a prefix(resp.suffix)of u if x(resp.y)is the empty word.For a word u=u0u1un1 An,the prefix and suffix of length l(1 l n)are defined asprefl(u):=u0u1ul1and suffl(u):=unlun1;Received date:2023-02-10Foundation item:Supported by the National Natural Science Foundation of China(11801203)Biography:LV Xiaotao,male,Han,Henan,lecturer,major in complexity theoryNo.4LV Xiaotao：On the k-Abelian Complexity of the Cantor-like Sequence1101while for l 0,we define prefl(u)=and suffl(u)=.The number of occurrences of a wordv in u is denoted by|u|v.Now we give the definitions of the k-abelian equivalence and thek-abelian complexity.Definition 1.1 Let k be a positive integer.Two words u,v Aare said to be k-abelianequivalent,written u kv,if the following conditions hold:1)|u|w=|v|wfor every w Ak,2)prefmink1,|u|(u)=prefmink1,|v|(v)and suffmink1,|u|(u)=suffmink1,|v|(v).It is easy to check that k-abelian equivalence is indeed an equivalence relation.Definition 1.2The k-abelian complexity of an infinite word is the function P(k):N N and for every n 1,P(k)(n)is assigned to be the number of k-abelian equivalenceclasses of factors of of length n.Precisely,for every positive integer n,P(k)(n)=Card(F(n)/k),where F(n)is the set of all factors of length n occurring in.The 1-abelian complexity ofan infinite word is also known as its abelian complexity.The abelian complexity functions of some notable sequences,such as the Thue-Morsesequence and the Rudin-Shapiro sequence,are studied in 17 and 14,respectively.Thereare also many other works devoted to this subject(see 3).This paper is devoted to the study of k-abelian complexity of the Cantor-like sequencec:=c0c1c2=10l10l(l+2)10l1which satisfies c0=1 and for every n 0,1 i lc(l+2)n=c(l+2)n+l+1=cnand c(l+2)n+i=0,(1.1)where l 2 is an integer.The Cantor-like sequence c is also the fixed point of the morphism:1 7 10l1,0 7 0l+2beginning with 1,i.e.,c=(1).Our first result states that for every integer k with 1 k l,the(k+1)-abelianequivalence of any two factors of the Cantor-like sequence c can be reduced to the k-abelianequivalence of such factors under certain conditions.In detail,we prove the following theorem.Theorem 1.1Let k be a positive integer with 1 k l and let u,v be two factorsof c satisfying|u|=|v|.If prefk(u)=prefk(v)and suffk(u)=suffk(v),then u k+1v if andonly if u kv.To state our next result,we shall recall the definitions of b-automatic and b-regularsequences.For more details,see 1 and the references therein.Definition 1.3Let b 2 be an integer.The b-kernel of an infinite sequence w=(w(n)n0is the set of subsequencesKb(w):=(w(ben+c)n0|e 0,0 c be.The sequence w is called a b-automatic sequence if Kb(w)is finite.The sequence w is saidto be b-regular if the Z-module generated by its b-kernel is finitely generated.By using Theorem 1.1,we are able to study the k-abelian complexity of c for every2 k l+1.Here we are just concerned with the 2-abelian complexity of c,the methodused in computing k-abelian complexity(3 k l+1)is similar.Actually we obtain thefollowing result.Theorem 1.2The 2-abelian complexity function of the Cantor-like sequence is(l+2)-regular.1102MATHEMATICA APPLICATA2023Karhum aki,Saarela,and Zamboni11investigated the k-abelian complexity of Sturmianwords and gave an characterization of ultimately periodic sequences by means of k-abeliancomplexity.They also studied the k-abelian complexity of the Thue-Morse sequence,whichis a 2-automatic sequence.Greinecker7and Parreau et al.15proved independently that the2-abelian complexity of the Thue-Morse sequence is 2-regular.Our result(Theorem 1.2)givesanother 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 rightspecial factors of the Cantor-like sequence and prove Theorem 1.1.In Section 3,we give therecurrence 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 cIn this section,we reduce(k+1)-abelian equivalence of factors of the Cantor-like sequencec to k-abelian equivalence of them under certain conditions.Before stating the result,we givesome auxiliary lemmas.The first one states that the factor set Fc(n)is closed under thereversal operator.The second one characterizes the structure of the left and right specialfactors of c.Recall that a factor v of is said to be right special(resp.left special)if thereexist at least two distinct letters a,b A such that both va and vb(resp.av and bv)arefactors.Given an infinite sequence AN,let RS(n)(resp.LS(n)denote the set ofall right special(resp.left special)factors of of length n.The set of all right special factorsand left special factors of are denoted by RSand LSrespectively.Lemma 2.1For every u=u0u1un1 Fc(n)with n 1,its mirror u=un1un2u0is also a factor of the Cantor-like sequence.ProofBy the definition of the morphism,(1)=101=(1)and(0)=0+2=(0).Thus for every i 1,i(1)=i(1).For every u=u0u1un1 Fc(n),there exists an integer i 1 such that u i(1).Therefore,u=un1un2u0 i(1)=i(1),which implies u is also a factor of c.Lemma 2.2For every 1 n l,RSc(n)=LSc(n)=0n.For every i 0 and l(l+2)i n l(l+2)i+1,RSc(n)=0n,suffn(i(0l10l),if n l(l+2)i+1,(2l+1)(l+2)i,0n,if n (2l+1)(l+2)i,l(l+2)i+1.LSc(n)=0n,prefn(i(0l10l),if n l(l+2)i+1,(2l+1)(l+2)i,0n,if n (2l+1)(l+2)i,l(l+2)i+1.ProofThe result follows from Theorem 1 in 13 and Lemma 2.1 directly.For z,w A,we defineP(z,w):=1,if z is a prefix of w,0,otherwise,and S(z,w):=1,if z is a suffix of w,0,otherwise.No.4LV Xiaotao：On the k-Abelian Complexity of the Cantor-like Sequence1103Lemma 2.36Let 0,1and u,z Fwith|u|z|2.Suppose z=aybwhere a,b 0,1.We have|u|z=|u|yb P(yb,u),if yb/LS,|u|ay S(ay,u),if ay/RS,|u|yb|u|(1a)yb P(yb,u),if yb LS,|u|ay|u|ay(1b)S(ay,u),if ay RS.Now,we prove Theorem 1.1.Proof of Theorem 1.1When|u|2k 1,by the assumptions,we have u=v.Inthis case,the result is trivial.In the following,we always assume that|u|2k.The only ifpart follows directly from the definition of k-abelian equivalence.For the if part,we only need to show that u kv implies that for every z Fc(k+1),|u|z=|v|z.For this purpose,we separate Fc(k+1)into two disjoint parts,i.e.,Fc(k+1)=E1 E2whereE1=z Fc(k+1)|prefk(z)/RSc(k)or suffk(z)/LSc(k),E2=z Fc(k+1)|prefk(z)RSc(k)and suffk(z)LSc(k).Suppose z E1.If suffk(z)/LSc(k),then by Lemma 2.3,|u|z=|u|suffk(z)P(suffk(z),u)=|v|suffk(z)P(suffk(z),v)=|v|z.If prefk(z)/RSc(k),then by Lemma 2.3,|u|z=|u|prefk(z)S(prefk(z),u)=|v|prefk(z)S(prefk(z),v)=|v|z.So,for every z E1,|u|z=|v|z.Now,we prove the case z E2.By Lemma 2.2,LSc(n)RSc(n)=0n for everyinteger n 1,l+1.Since 1 k l,E2=0k+1.By Lemma 2.3 and the assumptions ofthis result,|u|0k+1=|u|0k|u|0k1 S(0k,u)=|u|0k(|u|0k11 P(0k11,u)S(0k,u)=|v|0k(|v|0k11 P(0k11,v)S(0k,v)=|v|0k+1.So,for every factor z E1 E2,|u|z=|v|zwhen u kv.We may now apply Theorem 1.1 k times to reduce the k-abelian equivalence to the1-abelian equivalence under the theorems condition.Corollary 2.1Let 1 k l and u,v be two factors of the sequence c with|u|=|v|.If prefk(u)=prefk(v)and suffk(u)=suffk(v),then u k+1v if and only if u 1v.3.The Abelian Complexity of the Sequence cIn this section,we shall investigate the abelian complexity of the Cantor-like sequence c.Let =012 be an infinite sequence over 0,1.It has been proved in Proposition2.2 of 2 that the abelian complexity of is related to its digit sums in the following way:for every n 1,P(1)(n)=M(n)m(n)+1,(3.1)whereM(n):=maxi+n1j=ij|i 0and m(n):=mini+n1j=ij|i 0.1104MATHEMATICA APPLICATA2023For the digit sums of the Cantor-like sequence c,we have the following lemma.Lemma 3.1For all n 1,Mc(n)=n1i=0ciand mc(n)=0.ProofSince 0nis always a factor of c for every n 1,we have mc(n)=0 for everyn 1.For every i 0 and n 1,let(i,n):=i+n1j=icj.We only need to show thatMc(n)(0,n)for every n 1.For this purpose,we shall prove that for every n 1,(i,n)(0,n)for all i 0.(3.2)Since 1 occurs in c and 11 does not occur in c,we have(i,1)1=(0,1)and(i,2)1=(0,2).Now suppose(3.2)holds for n l+1 and suppose n (l+2)ifor some i 1.By the definition of the function Mc(n),it is obvious that|1 Mc(n 2)for every Wn,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,let Wj=0njprefj(i(1)which is a factor of i(01)andhence,a factor of c.Note that|W0|1=0 and it follows from Lemma 3.1 that|Wj|1=Mc(j)for j=1,n 2.If the last letter of Wjis 0,then Wj Wn,0,0.Otherwise,|Wj+1|1=|Wj|1=s since 11 is not a factor of c.Therefore,Wj+1 Wn,0,0.This implies thatp2(n,0,0)Mc(n2)+1 which proves(4.3).The regularity of the sequence p2(n,0,0)n1then follows from(4.3)and Corollary 3.1.Lemma 4.2p2(1,0,1)=p2(1,1,0)=0 and for every n 2,p2(n,0,1)=p2(n,1,0)=Mc(n 1).(4.4)Moreover,the sequences p2(n,0,1)n1and p2(n,1,0)n1are both(l+2)-regular.ProofBy Lemma 2.1,for every factor w of c,its reversal w is also a factor of c.Therefore,p2(n,1,0)=p2(n,0,1).Clearly,for every Wn,0,1,1|1 Mc(n 1).So,p2(n,0,1)Mc(n 1).Next,we prove the reverse inequality.Let i be a positive integer such that n (l+2)i.For every 1 j n 1,letWj=0njprefj(i(1)which is a factor of i(01)and therefore,a factor of c.By Lemma3.1,|Wj|1=Mc(j)for j=1,n 2.If the last letter of Wjis 1,then Wj Wn,0,1.Otherwise,suppose that Wjends with 10mwhere m is an integer with 1 m j 1.Then1106MATHEMATICA APPLICATA2023Wjm Wn,0,1and|Wjm|1=|Wj|1=s.This implies that p2(n,0,1)Mc(n 1).Theresult then follows from(4.4)and Corollary 3.1.To deal with the set of factors Wn,1,1and the sequence p2(n,1,1)n1,we introduce thefollowing two sets.Let g(i)i0be a monotone increasing sequence of integers whose values equal to thelength of the factors of c beginning and ending with 1.Let G(i)i0be the sets of thecorresponding factors of length g(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 and G(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 integer i,G(3i)=(G(i)(0l1)1(10l)1(G(i),G(3i+1)=(G(i),G(3i+2)=(10l)1(G(i+1)(0l1)1,(4.5)where(G(i):=(v):v G(i)and wv1=u,u1w=v if w=uv.ProofThis will be done by induction on i.It is easy to check that G(0)=1,G(1)=10l1,G2=10l(l+2)1,which implies(4.5)holds when i=0.Suppose(4.5)holds fori 3j(j 1).Next we shall prove the results for 3j i 3(j+1).The proof in this stepwill be separated into the following three cases.Case 1i=3j for some 1 j i 1.By induction,G(i 1)=G(3j 1)=G(3(j 1)+2)=(10l)1(G(j)(0l1)1.Since(1)=10l1 and every element in G(j)begins and ends with 1,for every U G(i),thereexists u G(j)such that U=(10l)1(u)or U=(u)(0l1)1.Otherwise,suppose thereis another U G(i)which is not in the forms of(10l)1(u)or(u)(0l1)1.Consider thepre-image of U,i.e.,the shortest usatisfying U(u).By the definition of the morphism,the factor uis unique.Then,u/G(j 1)G(j)and g(j 1)|u|g(j),whichcontradicts with the definitions of G(j)and g(j).So,we haveG(i)=(G(j)(0l1)1(10l)1(G(j).Case 2i=3j+1 for some 1 j i 1.By induction,G(i 1)=G(3j)=(G(j)(0l1)1(10l)1(G(j).With a similar argument in the Case 1,we obtain that:G(i)=(G(j).Case 3i=3j+2,for some 1 j i 1.By induction,G(i 1)=(G(j).Forevery u G(j),v G(j+1),|u|=g(j)g(j+1)=|v|,and there are no factors beginningand ending with 1 of length between g(j)and g(j+1).Therefore,for every V G(i),there exists v Gj+1such that V (v).If V (v)for some v v with|v|v|,then|V|(u)|=g(3j+1)g(3j+2).(Otherwise,there exists a factor vwith length|u|v|v|beginning and ending with 1,which contradicts with the definitions of g(j)and g(j+1).)Hence,V (v),(10l)1(v),(v)(0l1)1,(10l)1(v)(0l1)1.Moreover,bythe monotonicity of the sequence g(n)n0,we have V=(10l)1(v)(0l1)1.Therefore,G(i)=G(3j+2)=(10l)1(G(j+1)(0l1)1.Corollary 4.1g(0)=1,and for every n 0,g(3n)=(l+2)g(n)(l+1),g(3n+1)=(l+2)g(n),g(3n+2)=(l+2)g(n+1)(2l+2).No.4LV Xiaotao：On the k-Abelian Complexity of the Cantor-like Sequence1107Corollary 4.2For every i 0 and u,v G(i),|u|1=|v|1.By Corollary 4.2 and(4.1),for every n 1,we havep2(n,1,1)=1,if n=g(i)for some i 0,0,otherwise.The following lemma proves the regularity of the sequence p2(n,1,1)n1.Lemma 4.4p2(1,1,1)=1,p2(i,1,1)=0 for i=2,l+1 and for every n 1,0 j l+1,p2(l+2)n+j,1,1)=p2(n,1,1),if j=0,(4.6a)p2(n+1,1,1),if j=1,(4.6b)p2(n+2,1,1),if j=2,(4.6c)0,otherwise.(4.6d)Moreover,the sequence p2(n,1,1)n1is(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 every i 0,g(i)mod(l+2)0,1,2.Therefore,for every n 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,if n=g(i)for some i 0,then p2(n,1,1)=1and by Corollary 4.1,(l+2)n=(l+2)g(i)=g(3i+1).Hence,p2(l+2)n