## Complexity of infinite words associated with beta-expansions

^{1}
LIAFA, CNRS UMR 7089,
2 place Jussieu, 75251 Paris Cedex 05, France; christiane.frougny@liafa.jussieu.fr.

^{2}
Université Paris 8.

^{3}
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

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*is finite we provide a simple description of the structure of special factors of the word

_{β}(1) = t_{1}t_{2}...t_{m}*u*. When

_{β}*t*=1 we show that

_{m}*C(n) = (m - 1)n + 1*. In the cases when

*t*or

_{1}= t_{2}= ... t_{m-1}*t*max

_{1}>*{t*} we show that the first difference of the complexity function

_{2},...,t_{m-1}*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*. On the example of

_{β}(1) = tt...t1*β = 1 + 2*cos(2π/7), solution of

*X*, we illustrate that the structure of special factors is more complicated for

^{3}= 2X^{2}+ X - 1*d*(1) infinite eventually periodic. The complexity for this word is equal to

_{β}*2n+1*.

Mathematics Subject Classification: 11A63 / 11A67 / 37B10 / 68R15

Key words: Beta-expansions / complexity of infinite words.

*© EDP Sciences, 2004*