Complexity of infinite words associated with beta-expansions

Abstract

We study the complexity of the infinite word uβ associated with the Rényi 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) = t1t2...tm is finite we provide a simple description of the structure of special factors of the word uβ. When tm=1 we show that C(n) = (m - 1)n + 1. In the cases when t1 = t2 = ... tm-1or t1 > max{t2,...,tm-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...t1. On the example of β = 1 + 2cos(2π/7), solution of X3 = 2X2 + 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.