Abelian powers and repetitions in Sturmian words

被引:14
作者
Fici, Gabriele [1 ]
Langiu, Alessio [2 ]
Lecroq, Thierry [3 ]
Lefebvre, Arnaud [3 ]
Mignosi, Filippo [4 ]
Peltomaki, Jarkko [5 ]
Prieur-Gaston, Elise [3 ]
机构
[1] Univ Palermo, Dipartimento Matemat & Informat, I-90133 Palermo, Italy
[2] Kings Coll London, Dept Informat, London WC2R 2LS, England
[3] Univ Rouen, Normandie Univ, LITIS EA4108, FR CNRS Normast 3638, F-76821 Mont St Aignan, France
[4] Univ Aquila, DISIM, I-67100 Laquila, Italy
[5] Univ Turku, Dept Math & Stat, Turku Ctr Comp Sci, TUCS, SF-20500 Turku, Finland
关键词
Sturmian word; Abelian power; Abelian period; Lagrange constant; Critical exponent; EPISTURMIAN WORDS; ALGEBRAIC-NUMBERS; COMPLEXITY;
D O I
10.1016/j.tcs.2016.04.039
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Richomme, Saari and Zamboni (2011) [39] proved that at every position of a Sturmian word starts an abelian power of exponent k for every k > 0. We improve on this result by studying the maximum exponents of abelian powers and abelian repetitions (an abelian repetition is an analogue of a fractional power) in Sturmian words. We give a formula for computing the maximum exponent of an abelian power of abelian period m starting at a given position in any Sturmian word of rotation angle alpha. By considering all possible abelian periods m, we recover the result of Richomme, Saari and Zamboni. As an analogue of the critical exponent, we introduce the abelian critical exponent A(s(alpha)) of a Sturmian word s(alpha) of angle alpha as the quantity A(s(alpha)) = lim sup k(m)/m = lim sup k'(m)/m, where k(m) (resp. k'(m)) denotes the maximum exponent of an abelian power (resp. of an abelian repetition) of abelian period m (the superior limits coincide for Sturmian words). We show that A(s(alpha)) equals the Lagrange constant of the number alpha. This yields a formula for computing A(s(alpha)) in terms of the partial quotients of the continued fraction expansion of alpha. Using this formula, we prove that A(s(alpha)) >= root 5 and that the equality holds for the Fibonacci word. We further prove that A(s(alpha)) is finite if and only if alpha has bounded partial quotients, that is, if and only if s(alpha) is beta-power-free for some real number beta. Concerning the infinite Fibonacci word, we prove that: i) The longest prefix that is an abelian repetition of period F-j, j > 1, has length F-j(Fj+1 + Fj-1 + 1) - 2 if j is even or F-j(Fj+1 + Fj-1) - 2 if j is odd, where F-j is the jth Fibonacci number; ii) The minimum abelian period of any factor is a Fibonacci number. Further, we derive a formula for the minimum abelian periods of the finite Fibonacci words: we prove that for j >= 3 the Fibonacci word f(j), of length F-j, has minimum abelian period equal to F-left perpendicularj/2right perpendicular if j = 0, 1, 2 mod 4 or to F1+left perpendicularj/2right perpendicular if j = 3 mod 4. (C) 2016 Elsevier B.V. All rights reserved.
引用
收藏
页码:16 / 34
页数:19
相关论文
共 43 条
[1]   On the complexity of algebraic numbers I. Expansions in integer bases [J].
Adamczewski, Boris ;
Bugeaud, Yann .
ANNALS OF MATHEMATICS, 2007, 165 (02) :547-565
[2]   On the complexity of algebraic numbers, II. Continued fractions [J].
Adamczewski, Boris ;
Bugeaud, Yann .
ACTA MATHEMATICA, 2005, 195 (01) :1-20
[3]  
Alessandri P., 1998, ENSEIGN MATH, V44, P103
[4]  
[Anonymous], 2002, LECT NOTES MATH, DOI DOI 10.1007/B13861
[5]  
[Anonymous], 1995, INTRO DIOPHANTINE AP
[6]  
[Anonymous], 1879, Math. Ann, V15, P381, DOI DOI 10.1007/BF02086269
[7]   ON ABELIAN VERSIONS OF CRITICAL FACTORIZATION THEOREM [J].
Avgustinovich, Sergey ;
Karhumaki, Juhani ;
Puzynina, Svetlana .
RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2012, 46 (01) :3-15
[8]  
Berstel J., 1999, JEWELS ARE FOREVER, P287
[9]  
Berstel J., 2008, CRM MONOGR SER, V27
[10]  
Berstel J, 2007, LECT NOTES COMPUT SC, V4728, P23