Complexity of infinite words associated with beta-expansions

¹ LIAFA, CNRS UMR 7089, 2 place Jussieu, 75251 Paris Cedex 05, France; christiane.frougny@liafa.jussieu.fr.
² Université Paris 8.
³ Department of Mathematics, FNSPE, Czech Technical University, Trojanova 13, 120 00 Praha 2, Czech Republic; masakova@km1.fjfi.cvut.cz.,pelantova@km1.fjfi.cvut.cz.

Received: September 2003
Accepted: 12 February 2004

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) = t₁t₂...t_m is finite we provide a simple description of the structure of special factors of the word u_β. When t_m=1 we show that C(n) = (m - 1)n + 1. In the cases when t₁ = t₂ = ... t_m-1or t₁ > max{t₂,...,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...t1. On the example of β = 1 + 2cos(2π/7), solution of X³ = 2X² + 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.