ABELIAN MAXIMAL PATTERN COMPLEXITY OF WORDS TETUROKAMAE,STEVENWIDMER,ANDLUCAQ.ZAMBONI ABSTRACT. InthispaperwestudythemaximalpatterncomplexityofinfinitewordsuptoAbelian equivalence. We compute a lower bound for the Abelian maximal pattern complexity of infinite 3 words which are both recurrent and aperiodic by projection. We show that in the case of binary 1 words,theboundisactuallyachievedandgivesacharacterizationofrecurrentaperiodicwords. 0 2 n a J 1. INTRODUCTION 2 2 Let A be a finite non-empty set. We denote by A∗, AN and AZ respectively the set of finite words, theset of (right)infinitewords, and theset of bi-infinitewords overthealphabet A. Given ] O aninfinitewordα = α0α1α2... ∈ AN withαi ∈ A,wedenotebyFα(n)thesetofallfactorsofα C oflengthn, thatis, theset ofallfinitewordsoftheform αiαi+1···αi+n−1 withi ≥ 0.Weset . h p (n) = #(F (n)). α α t ma Thefunctionpα : N → Nis called thefactorcomplexityfunctionofα. We recall that two words u and v in A∗ are said to be Abelian equivalent, denoted u ∼ab v, if [ and only if |u|a = |v|a for all a ∈ A, where |u|a denotes the numberof occurrences of the letter a v1 inu. It isreadily verifiedthat ∼ab defines an equivalencerelationon A∗.We define 3 ab 1 Fα (n) = Fα(n)/ ∼ab 1 and set 5 ab ab . p (n) = #(F (n)). 1 α α 0 ab 3 Thefunctionpα : N → NwhichcountsthenumberofpairwisenonAbelianequivalentfactorsof 1 α oflengthn iscalled theAbeliancomplexityofα (see [8]). : v There are a number of similarities between the usual factor complexity of an infinite word and i its Abelian counterpart. For instance, both may be used to characterize periodic bi-infinite words X (see [7] and [1]). A word α is periodic if there exists a positiveinteger p such that α = α for r i+p i a all indices i, and it is ultimatelyperiodic if α = α for all sufficiently large i. An infinite word i+p i isaperiodicifit isnot ultimatelyperiodic. Thefactorcomplexityfunctionalso providesacharac- terizationofultimatelyperiodicwords. Ontheotherhand, Abeliancomplexitydoesnotyieldsuch acharacterization. Indeed,bothSturmianwordsandtheultimatelyperiodicword 01∞ = 0111··· havethesame, constant2,Abelian complexity. Asanotherexample,bothcomplexityfunctionsgiveacharacterizationofSturmianwordsamongst all aperiodicwords: Theorem1. Letαbeanaperiodicinfinitewordoverthealphabet{0,1}. Thefollowingconditions areequivalent: 2000MathematicsSubjectClassification. Primary68R15. Keywordsandphrases. Abelianequivalence,complexityofwords,periodicity. ThethirdauthorissupportedbyaFiDiPrograntfromtheAcademyofFinland. 1 2 T.KAMAE,S.WIDMER,ANDL.Q.ZAMBONI • Theword α isbalanced,thatis, Sturmian. • (M. Morse,G.A. Hedlund,[7]). Theword α satisfiesp (n ) = n+1 foralln ≥ 0. α 0 ab • (E.M. Coven, G.A. Hedlund,[1]). Theword α satisfiesp (n) = 2for alln ≥ 1. α In [3], the first and third authors introduced a different notion of the complexity of an infinite word calledthemaximalpatterncomplexity: For each positiveinteger k, let Σk(N) denote the set of all k-element subsets of N. An element S = {s1 < s2 < ··· < sk} ∈ Σk(N) willbecalled ak-pattern. Weput α[S] := α(s1)α(s2)···α(sk) ∈ Ak. Foreachn ∈ N,thewordα[n+S]iscalledaS-factorofα,wheren+S := {n+s ,n+s ,··· ,n+ 1 2 s }. WedenotebyF (S)thesetofall S-factors of α.We definethepatterncomplexityp (S) by k α α p (S) = #F (S) α α and themaximalpatterncomplexityp∗(k) by α p∗(k) = sup p (S). α α S∈Σk(N) In [3] the authors show that maximal pattern complexity also gives a characterization of ulti- matelyperiodicwords : Theorem 2. Let α ∈ AN.Then thefollowingareequivalent (1) α iseventuallyperiodic (2) p∗(k)is uniformlyboundedin k α (3) p∗(k) < 2k for somepositiveintegerk. α In otherwords, α isaperiodicifand onlyif p∗(k) ≥ 2k foreach positiveintegerk. Wesay α ∈ α AN is pattern Sturmian if p∗(k) = 2k for each positive integer k. Two types of recurrent pattern α Sturmian words are known: rotation words (see below) and a family of ‘simple’ Toeplitz words (see [3]). Unfortunately, to date there is no known classification of recurrent pattern Sturmian words(as in thecaseofTheorem1). Theconnection between items (1) and (3) in Theorem 2 was generalized by thefirst authorand R. Hui in[5]. Wesayα ∈ AN is periodicbyprojectionifthereexistsaset ∅ =6 B $ A, such that 1 (α) := 1 (α(0))1 (α(1))1 (α(2))··· ∈ {0,1}N. B B B B is eventually periodic (where 1 denotes the characteristic function of B). We say α is aperiodic B byprojectionifα is notperiodicby projection. Then: Theorem 3. Let #A = r ≥ 2,and α ∈ AN beaperiodicbyprojection. Then p∗(k) ≥ rk foreach α positiveintegerk. In other words, low pattern complexity (relative to the size of the alphabet) implies periodic by projection. Notice that if #A = 2, then α is periodic by projection if and only if α is eventually periodic. InthispaperweintroduceandstudyanAbeliananalogueofmaximalpatterncomplexity: Given ak-pattern S ∈ Σk(N),we define ab F (S) = F (S)/ ∼ α α ab ABELIANMAXIMAL PATTERNCOMPLEXITYOFWORDS 3 and theassociated Abelianpatterncomplexity ab ab p (S) = #F (S) α α whichcountsthenumberofpairwisenonAbelianequivalentS-factorsofα.WedefinetheAbelian maximalpatterncomplexity ab ab p∗ (k) = sup p (S). α α S∈Σk(N) Itis clearthat foreach positiveinteger k andforeach pattern S ∈ Σk(N) wehave ab ab p (S) ≤ p (S) and p∗ (k) ≤ p∗(k). α α α α In thispaperweshow: Theorem 4. Let #A = r ≥ 2 and α ∈ AN be recurrent and aperiodic by projection. Then for each positiveinteger k we have ab p∗ (k) ≥ (r−1)k +1 α In case r = 2 equality always holds. Moreover for k = 2 and general r, there exists α satisfying theequality. For example, if α ∈ {0,1}N is a Sturmian word and S ∈ Σk(N) is a k-block pattern, i.e., ab S = {0,1,2,...,k − 1}, then we have p (S) = 2 (since α is balanced) while p (S) = k + 1. α α Sinceαisbothrecurrentandaperiodic,itfollowsfromtheabovetheoremthattheAbelianmaximal ab patterncomplexityp∗ (k) takes themaximumvaluek +1 foreach positiveintegerk.Moreover, α all recurrent pattern Sturmianwordssharethisproperty. ab For a rotation word α ∈ AN with r = #A ≥ 3, we show that p∗ (k) = rk for each positive α integer k (see Theorem 6). Since p∗(k) = rk, the abelianization doesn’t decrease the complexity α ab inthiscase. Ontheotherhand,intheproofofTheorem 4,weshowthatp∗ (2) = 2r−1forany α Toeplitzword α ∈ AN with#A = 2. We define two classes of words with A = {0,1,··· ,r − 1} and r ≥ 2. Let θ be an irrational number and c0 < c1 < ··· < cr−1 < cr be real numbers such that cr = c0 + 1. Define α ∈ Ak by α(n) = i if nθ ∈ [ci,ci+1) (mod 1) forany i ∈ A and n ∈ N. We call such α a rotationword. Let Z be the 2-adic compactification of Z and γ ∈ Z . For n ∈ Z , let τ(n) ∈ N ∪{∞} be the 2 2 2 superimum of k ∈ N such that 2k devides n. Let Bi (i ∈ A) be infinite subsets of N∪{∞} such thatBi∩Bj = ∅foranyi,j ∈ Awithi 6= j and∪i∈ABi = N∪{∞}. Defineα ∈ AN byα(n) = i ifτ(n−γ) ∈ Bi forany i ∈ A and n ∈ N.Wecall such α aToeplitzword. Wedonot knowwhethertheinequalityin Theorem4 istightwhen r ≥ 3 and k ≥ 3. 2. BACKGROUND & NOTATION Givenafinitenon-emptyset A,weendowAN withthetopologygenerated by themetric 1 d(x,y) = where n = inf{k : x 6= y } 2n k k whenever x = (xn)n∈N and y = (yn)n∈N are two elements of AN. For ω ∈ AN, let O(ω) denote the closure of the orbit O(ω) := {Tnω : n ∈ N} of ω with respect to the shift T on AN, where (Tω)(n) = ω(n+1)(n ∈ N). Givena finiteword u = a a ...a with n ≥ 1 and a ∈ A, we denotethelength n of u by |u|. 1 2 n i Foreach a ∈ A, welet |u| denotethenumberofoccurrences oftheletter a inu. a 4 T.KAMAE,S.WIDMER,ANDL.Q.ZAMBONI Foreach u ∈ A∗,we denoteby Ψ(u) the Parikhvector or abelianizationof u, that is the vector indexedby A Ψ(u) = (|u| ) . a a∈A GivenΞ ⊂ A∗,we set ab Ξ := Ξ/ ∼ ab and Ψ(Ξ) := {Ψ(ξ)|ξ ∈ Ξ}. ab ThereisanobviousbijectionbetweenthesetsΞ andΨ(Ξ)whereoneidentifiestheAbelianclass ofan elementu ∈ A∗ withitsParikhvector Ψ(u). GivenanonemptysetΩ ⊂ AN, S ∈ Σk(N) and an infinitesetN ⊂ N weput Ω[S] := {ω[S]|ω ∈ Ω} ⊂ Ak and Ω[N] := {ω[N]|ω ∈ Ω} ⊂ AN where ω[N] ∈ AN isdefined byω[N](n) = ω(Nn) (n ∈ N). Analogouslywecan definethemaximalpatterncomplexityof Ωby p∗(k) = sup p (S) Ω Ω S∈Σk(N) where p (S) = #Ω[S] Ω and theAbelian maximalpattern complexityof Ω ab ab p∗ (k) = sup p (S) Ω Ω S∈Σk(N) where ab ab p (S) = #Ω[S] . Ω 3. SUPERSTATIONARY SETS & RAMSEY’S INFINITARY THEOREM Lemma3.1. Letω ∈ AN bearecurrentinfiniteword. ThenthereexistsaninfinitesetN = {N < 0 N < N < ···} ⊂ N satisfyingthefollowingcondition: 1 2 (∗) ∀i ≥ 0, ∀k ≥ 0 ω ω ···ω ω∞ ∈ O(ω)[N] i+N0 i+N1 i+Nk−1 i+Nk Proof. We show by induction on k that for each k ≥ 0 there exists natural numbers N < 0 N < ··· < N such that for each j ≤ k, if u u ···u ∈ O(ω)[{N ,N ,...,N }] then 1 k 0 1 j 0 1 j u0u1···ukj−j+1 ∈ O(ω)[{N0,N1,...,Nk}]. Clearly we can take for N0 any natural numberin N. Next suppose we have chosen natural numbers N < N < ··· < N with the required property. 0 1 k Fix a positive integer L such that if u ∈ O(ω)[{N ,N ,...,N }], then there exists i ≤ L − N 0 1 k k with u = ω ω ···ω . Since ω is recurrent, there exists a positive integerN > N i+N0 i+N1 i+Nk k+1 k such that ω = ω for each i ≤ L. We now verify that N < N < ··· < N satis- i i+Nk+1 0 1 k+1 fies the required property. So assume j ≤ k + 1 and u u ···u ∈ O(ω)[{N ,N ,...,N }]. We 0 1 j 0 1 j must show that u u ···uk+1−j+1 ∈ O(ω)[{N ,N ,...,N }]. This is clear in case j = k + 1, 0 1 j 0 1 k+1 thus we can assume j ≤ k. Then by induction hypothesis we have that u = u u ···uk−j+1 ∈ 0 1 j O(ω)[{N ,N ,...,N }].Fix i ≤ L−N such thatu = ω ω ···ω .Then 0 1 k k i+N0 i+N1 i+Nk ABELIANMAXIMAL PATTERNCOMPLEXITYOFWORDS 5 u u ···uk+1−j+1 = u u ···uk−j+1u 0 1 j 0 1 j j = ω ω ···ω ω i+N0 i+N1 i+Nk i+Nk = ω ω ···ω ω . i+N0 i+N1 i+Nk i+Nk+1 Henceu u ···uk+1−j+1 ∈ O(ω)[{N ,N ,...,N }]as required. (cid:3) 0 1 j 0 1 k+1 It isreadily verifiedthat: Lemma 3.2. Let N = {N < N < N < ···} ⊂ N be an infiniteset satisfyingthecondition(*) 0 1 2 above, andlet N′ beanyinfinitesubsetofN.Then N′ alsosatisfies(*). Proposition 3.3. Let Ω ⊂ AN be non-empty and let N = {N < N < N < ···} ⊂ N be an 0 1 2 infiniteset. Thenforeverypositiveintegerk,thereexistsaninfinitesubsetN′ ofN (dependingon k) suchthatforanytwo finitesubsetsP andQof N′ with 1 ≤ |P| = |Q| ≤ k,we have Ω[P] = Ω[Q]. Proof. We willrecursivelyconstructasequenceofnested infinitepatterns N′ = N ⊂ ··· ⊂ N ⊂ N = N k 2 1 such thatforeach 1 ≤ i ≤ k wehave Ω[P] = Ω[Q] forall finitesubsets P and QofN with1 ≤ |P| = |Q| ≤ i. i WebeginwithN .Giventwo finitesub-patterns P andQofN with|P| = |Q| = 2,wewrite 2 1 P ∼ Q ⇐⇒ Ω[P] = Ω[Q]. 2 Then ∼ defines an equivalence relation on the set of all sub-patterns of N of size 2, and hence 2 1 naturallydefines afinitecoloring ontheset of allsize 2 sub-patternsof N ,orequivalentlyon the 1 set of all 2-element subsetsof thenatural numbers N, wheretwo patterns P and Q are monochro- maticifand onlyifP ∼ Q. Wenowrecall thefollowingwell knowntheoremofRamsey: 2 Theorem 5([2],Ramsey). ]Letk beapositiveinteger. Thengivenanyfinitecoloringofthesetof all k-element subset of N, there exists an infinite set A ⊂ N such that any two k-element subsets ofA aremonochromatic. Thus applying the above theorem we deduce that there exists an infinite pattern N ⊂ N such 2 1 thatany twosub-patterns P and QofN ofsize2are ∼ equivalent. 2 2 Having constructed N ⊂ N ⊂ ··· ⊂ N ⊂ N = N with the required properties, we next k k−1 2 1 construct N as follows: Givenanytwo sub-patternsP andQ ofN ofsizek +1,wewrite k+1 k P ∼ Q ⇐⇒ Ω[P] = Ω[Q]. k+1 Again this defines a finite coloring of the set of all size k +1 sub-patterns of N , or equivalently k on the set of all (k + 1)−element subsets of N. Hence by Ramsey’s theorem, we deduce that there exists an infinite pattern N ⊂ N such that any two sub-patterns of N of size k + 1 k+1 k k+1 are monochromatic, i.e., ∼ equivalent. Moreover, since N ⊂ N , it follows that any two k+1 k+1 k sub-patterns P and QofN ofsize1 ≤ |P| = |Q| ≤ k are ∼ equivalent. k+1 |P| (cid:3) Definition 3.4. Let k ≥ 2. A nonemptyset Ω ⊂ AN is calleda k-superstationaryset if Ω[S] = Ω[S′] foranyS andS′ ∈ Σk(N) (see[6]). 6 T.KAMAE,S.WIDMER,ANDL.Q.ZAMBONI Asan immediateconsequenceofProposition3.3wehave Corollary3.5. LetΩ ⊂ AN benon-emptyandletN ⊂ Nbeaninfiniteset. Thenforeverypositive integerk,thereexistsan infinitesubsetN′ suchthatΩ[N′]is k-superstationary. Lemma 3.6. Let α ∈ AN be aperiodic by projection and let N ⊂ N be any infinite set. Put Ω := O(α)[N]. Then for any {i < j} ⊂ N, the directed graph (A,Ei,j) is strongly connected, where Ei,j = {(ω(i),ω(j)) ∈ A×A; ω ∈ Ω, ω(i) 6= ω(j)}. Proof. Fix{i < j} ⊂ NandN = {N0 < N1 < ···}. Foranyl = 0,1,··· ,Nj−Ni−1,letAl be the set of a ∈ A such that α(n) = a holds for infinitelymany n ∈ N with n ≡ l (mod Nj −Ni). For any a,b ∈ A, if {a,b} ∈ Al for some l ∈ {0,1,··· ,Nj − Ni − 1}, then a,b are two way connected in the graph (A,Ei,j). Hence for a,b ∈ A, a,b are two way connected in the graph (A,Ei,j) if there exist a0,a1,··· ,ak ∈ A and l1,··· ,lk ∈ {0,1,··· ,Nj − Ni − 1} such that (i)a = a, a = b, and (ii){a ,a } ∈ A forany i = 1,··· ,k. 0 k i−1 i li Supposeto thecontrary that thereexist a,b ∈ A such thata and bare not twoway connected in the graph (A,Ei,j). Let A be the set of a′ ∈ A such that a,a′ are two way connected in the graph (A,Ei,j). Then,wehave∅ =6 A⊂6=A. Moreover,thereexistsS with∅ =6 S ⊂ {0,1,··· ,Nj−Ni−1} suchthatA ⊂ Aforanyl ∈ S andA ∩A = ∅foranyl ∈ {0,1,··· ,N −N −1}\S. Therefore, l l j i 1 (α(0))1 (α(1))1 (α(2))··· A A A isperiodicwithperiodN −N ,whichcontradictsourassumptionthatαisaperiodicbyprojection. j i Thus,thegraphis stronglyconnected. (cid:3) Combininglemmas3.1, 3.2and 3.6withProposition3.3weobtain: Proposition 3.7. Let ω ∈ AN be recurrent and aperiodic by projection and k ≥ 2. Then there existsan infiniteset N ⊂ N suchthatΩ := O(α)[N]is ak-superstationaryset and (1) Foranyω ∈ Ωand i ∈ N, ω(0)ω(1)···ω(i−1)ω(i)∞ ∈ Ω (2) Forany{i < j} ⊂ N,thedirected graph(A,Ei,j) isstronglyconnected. 4. MAIN RESULTS Proofof Theorem 4. Fixapositiveintegerk.ByProposition3.7,thereexistsaninfinitesetN ⊂ N such that Ω = O(α)[N] ⊂ AN is k + 1-superstationary and satisfies conditions (1) and (2) of ab ab ab Proposition 3.7. Since p∗ (k) ≥ p∗ (k), it is sufficient to prove that #Ω ≥ (r − 1)k + 1, α Ω k where Ω := Ω[{0,1,··· ,k −1}]. k Let(A,E0,1) bethestronglydirected graph where E0,1 = {(ω(0),ω(1)) ∈ A×A withω(0) 6= ω(1); ω ∈ Ω}. Then there exists a sequence a0a1···al of elements in A containing all elements in A such that (a ,a ) ∈ E (i = 0,1,··· ,l−1). i i+1 0,1 Defineanon-directed graph (A,F) by F = {{a,b} ⊂ A witha 6= b and eitherakb∞ ∈ Ωorbka∞ ∈ Ω}. ABELIANMAXIMAL PATTERNCOMPLEXITYOFWORDS 7 Since Ω is k + 1-superstationary, for any i = 0,1,··· ,l − 1, there exists ω ∈ Ω such that ω[{kr,kr + 1}] = aiai+1. Hence, by (1) of Proposition 3.7, there exists ξ ∈ Akr such that ξaia∞i+1 ∈ Ω and ξa∞i ∈ Ω. Then, there exists b ∈ A occurring in ξ at least k times. Since Ω is k + 1-superstationary, this implies that bka and bka are in Ω[{0,1,··· ,k}]. Therefore, i i+1 bka∞ ∈ Ω and bka∞ ∈ Ω by (1) of Proposition 3.7. Hence, we have two cases according to i i+1 whetherb ∈ {a ,a } ornot. i i+1 Case1:b ∈ {a ,a }. In thiscase, wehave{a ,a } ∈ F. i i+1 i i+1 Case 2: b ∈/ {a ,a }. In this case, we have 2 edges {b,a } and {b,a } in F, by which a and i i+1 i i+1 i a are connected. i+1 Thus,wehaveaconnectedgraph (A,F). Thisimpliesthereareatleast r−1edges. If{a,b} ∈ F, then either akb∞ ∈ Ω or bka∞ ∈ Ω. Since Ω is k-superstationary, either ahbk−h ∈ Ω (h = k ab 0,1,··· ,k) or bhak−h ∈ Ω (h = 0,1,··· ,k). Any case, there are k + 1 elements in Ω k k consistingonlyofaand b. ab Since#F ≥ r−1,thereareatleast (r−1)(k+1)−(r−2) = (r−1)k+1elementsinΩ k consisting only of 2 elements, where we subtract r −2 since the number of overlapping counted forconstantwordsis 2(r−1)−r = r −2. ab Thus,#Ω ≥ (r −1)k +1. k ab If #A = 2, then p∗ (k) ≤ k +1 (k = 1,2,···) for any α ∈ AN, since the number of vectors α (|ξ| ,|ξ| ) overall ξ ∈ {0,1}k isk +1. 0 1 LetA = {0,1,··· ,r −1}with r ≥ 3. Forn ≥ 1, let τ(n) bethemaximumτ ∈ N such that2τ isafactorofn. Defineα ∈ AN byα(n) = τ(n+1) (mod r). ThenαisoneoftheToeplitzwords defined in Introduction. It isclearly recurrent andaperiodicbyprojection. Take any 2-pattern S = {s < t} ⊂ N. Let d = τ(t − s). Then there exists u ∈ N with 0 ≤ u < 2d such that eitherτ(s−u) = d, τ(t−u) > d or τ(s−u) > d, τ(t−u) = d. Assume without loss of generality that the latterholds. Let c ∈ A be such that c ≡ d (mod r) and denote by Ea ∈ RA theunitvectorat a ∈ A. Thereare 3cases for n ∈ Z. Case 1:τ(n+u+1) > d. In this case, τ(n+t+1) = d holds. Hence, Ψ(α[n+S]) = Ea +Ec forsomea ∈ A. Case2: τ(n+u+1) = d. In this case, τ(n+s+1) = d holds. Hence, Ψ(α[n+S]) = Ea +Ec forsomea ∈ A. Case3:τ(n+u+1) < d.Inthiscase,τ(n+s+1) = τ(n+t+1) < d. Hence,Ψα[n+S]) = 2Ea forsomea ∈ A. Therefore, {Ψ(α[n+S]) : n ∈ N} ⊂ {Ea +Ec; a ∈ A}∪{2Ea; a ∈ A}, ab ab ab andhence,p∗ (2) ≤ 2r−1. Thus,p∗ (2) = 2r−1sincewealreadyhavep∗ (2) ≥ 2r−1. Note α α α thatthisproofremainstrueforanyofthegeneral Toeplitzwordsdefined intheIntroduction. (cid:3) Remark 4.1. Theorem 4 is not true without the assumption of recurrency. In fact, let α = 103103210331··· ∈ {0,1}N. Then, p∗ab(3) = 3. To see this, suppose α[n + S] = 111 for some α n ∈ N,andsome3-pattern S = {i < j < k}.Then j −i = 3b −3a andk −j = 3c −3b forsome positiveintegers a < b < c. Moreover,thishappenswhen n = 3a −i. 8 T.KAMAE,S.WIDMER,ANDL.Q.ZAMBONI Supposeα[m+S] = 110 forsome m. Then sincethere existspositiveintegers d < e such that m+i = 3d andm+j = 3e,wehavej−i = (m+j)−(m+i) = 3e−3d = 3b−3a. Thisimplies that 3e + 3a = 3b + 3d, concluding e = b and a = d by the uniqueness of 3-adic representation. Hence,m = 3d −i = 3a −i, acontradiction. Ifα[m+S] = 101forsomem,thensincethereexistspositiveintegersd < esuchthatm+i = 3d and m + k = 3e, we have k − i = (m + k) − (m + i) = 3e − 3d = 3c − 3a. This implies that 3e +3a = 3c +3d, concludinge = c and a = d by the uniqunessof3-adic representation. Hence, m = 3d −i = 3a −i, acontradiction. Finally,ifα[m+S] = 011 forsomem,then sincethereexistspositiveintegers d < esuch that m+j = 3d andm+k = 3e,wehavek−j = (m+k)−(m+j) = 3e−3d = 3c−3b. Thisimplies that 3e + 3b = 3c + 3d, concluding e = c and b = d by the uniquness of 3-adic representation. Hence,m = 3d −j = 3b −j = 3a −i, againacontradiction. Thus if 111 ∈ {α[n + S]; n ∈ N} then {110,101,011} ∩ {α[n + S]; n ∈ N} = ∅. Thus, ab ab ab p∗ (3) ≤ 3. Since itisclearthat p∗ (3) ≥ 3, wehavep∗ (3) = 3. α α α Remark 4.2. We do not know whether there exist #A = r ≥ 3 and α ∈ AN which is recurrent and aperiodicby projectionand suchthat ab p∗ (k) = (r −1)k +1(k = 1,2,···). α Let A = {0,1,··· ,r − 1} and Ω = ∪r−2{i,i + 1}N. Then, it is readily verified that p∗ab(k) = i=0 Ω (r −1)k +1 (k = 1,2,···). ButΩisnot equalto O(α)forany choiceof α ∈ AN. ab Theorem 6. Let α ∈ AN be a rotation word with #A = r. Then, we have p∗ (k) = rk (k = α 1,2,···). Remark 4.3. For a rotation word α ∈ AN with #A = r, it is known [5] that p∗(k) = rk (k = α 1,2,···). Hence,Theorem6showsthattheabelianizationdoesnotdecreasethecomplexityinthe caseofrotationwordson morethan 2 letters. ab Proofof Theorem 6. Since p∗ (k) ≤ p∗(k) = rk (k = 1,2,···), it is sufficient to prove that α α ab p∗ (k) ≥ rk (k = 1,2,···). Let θ is an irrationalnumberand c < c < ··· < c < c be real α 0 1 r−1 r numbers with cr = c0 +1. Let A = {0,1,··· ,r −1}. We may assume that α ∈ AN is such that α(n) = iwhenevernθ ∈ [c ,c ) (mod 1) i i+1 Fix0 < ε < mini(ci+1 −ci).Set N = {N0 < N1 < ···} ⊂ N suchthat ε > {N θ} > {N θ} > ··· > 0 0 1 and lim {N θ} = 0.Here {} denotesthefractional part. Then, itis easy toseethat n→∞ n r−1 {α[n+N]; n ∈ N} = [{(i+1)ni∞; n ∈ N}, i=0 whereweidentify r with0 asletters. Thus,forany k = 1,2,···, wehave r−1 {α[n+Nk]; n ∈ N} = [{(i+1)nik−n; 0 ≤ n ≤ k}, i=0 ab where N = {N < N < ··· < N }. There are exactly rk words as above. Thus, p∗ (k) ≥ k 0 1 k−1 α rk (k = 1,2,···),which completestheproof. (cid:3) ABELIANMAXIMAL PATTERNCOMPLEXITYOFWORDS 9 REFERENCES [1] E.M.CovenandG.A.Hedlund.Sequenceswithminimalblockgrowth.MathematicalSystemsTheory,7:138– 153,1973. [2] R. McCutcheon, Elementary Methods in Ergodic Ramsey Theory, Lecture Note in Mathematics 1722, Springer,1999(inChapter2) [3] T.KamaeandL.Q.Zamboni,Sequenceentropyandthemaximalpatterncomplexityofinfinitewords,Ergod. Th.&Dynam.Sys.22(2002),pp.1191-1199. [4] T.KamaeandL.Q.Zamboni,Maximalpatterncomplexityfordiscretesystems,Ergod.Th.&Dynam.Sys.22 (2002),pp.1201-1214. [5] T.Kamae,H.Rao,Maximalpatterncomplexityoverℓletters,EuropeanJ.Combin.27(2006),pp.125-137. [6] T.Kamae,Uniformsetsandsuper-stationarysetsovergeneralalphabets,Ergod.Th.&Dynam.Sys.31(2011), pp.1445-1461. [7] M.MorseandG.A.Hedlund.SymbolicDynamicsII:Sturmiantrajectories.Amer.J.Math.,62(1):1–42,1940. [8] G. Richomme, K. SaariandL.Q. Zamboni,Abeliancomplexityofminimalsubshifts, J. LondonMath.Soc. (2),83(2011),pp.79–95. ADVANCEDMATHEMATICALINSTITUTE,OSAKACITY UNIVERSITY, OSAKA, 558-8585JAPAN E-mailaddress:[email protected] DEPARTMENTOFMATHEMATICSGENERALACADEMICSBUILDING4351155UNIONCIRCLE#311430DEN- TON,TX 76203-5017,USA E-mailaddress:[email protected] INSTITUT CAMILLE JORDAN, UNIVERSITE´ CLAUDE BERNARD LYON 1, 43 BOULEVARD DU 11 NOVEMBRE 1918,F69622VILLEURBANNECEDEX,FRANCE AND DEPARTMENTOFMATHEMATICSANDTURKUCEN- TREFOR COMPUTERSCIENCE, UNIVERSITY OFTURKU, 20014TURKU, FINLAND E-mailaddress:[email protected]