COMPLEXITY OF INFINITE WORDS ASSOCIATED WITH BETA-EXPANSIONS

摘要

We study the complexity of the infinite word u_β associated with the Renyi expansion of 1 in an irrational base β > 1. When β is the golden ratio, this is the well known Fibonacci word, which is Sturmian, and of complexity C(n) = n + 1. For β such that d_β(1) = t_1t_2 ... t_m is finite we provide a simple description of the structure of special factors of the word up. When t_m = 1 we show that C(n) = (m - 1)n + 1. In the cases when t_1 = t_2 = ··· = t_(m-1) or t_1 > max{t_2, ···, t_(m-1)} we show that the first difference of the complexity function C(n+1) -C(n) takes value in {m - 1,m} for every n, and consequently we determine the complexity of u_β. We show that u_β is an Arnoux-Rauzy sequence if and only if d_β(1) = tt ··? t 1. On the example of β= 1 + 2 cos(2π/7), solution of X~3 = 2X~2+X -1, we illustrate that the structure of special factors is more complicated for d_β(1) infinite eventually periodic. The complexity for this word is equal to 2n + 1.