Recurrence in infinite partial words

The recurrence functionRw(n) of an infinite word w was introduced by Morse and Hedlund in relation to symbolic dynamics. It is the size of the smallest window such that, wherever its position on w, all length n subwords of w will appear at least once inside that window. The recurrence quotientρ(w) of w, defined as limsupRw(n)n, is useful for studying the growth rate of Rw(n). It is known that if w is periodic, then ρ(w)=1, while if w is not, then ρ(w)⩾3. A long standing conjecture from Rauzy states that the latter can be improved to ρ(w)⩾5+52∼3.618, this bound being true for each Sturmian word and being reached by the Fibonacci word. In this paper, we study in particular the spectrum of values taken by the recurrence quotients of infinite partial words, which are sequences that may have some undefined positions. In this case, we determine exactly the spectrum of values, which turns out to be 1, every real number greater than or equal to 2, and ∞. More precisely, if an infinite partial word w is “ultimately factor periodic”, then ρ(w)=1, while if w is not, then ρ(w)⩾2, and we give constructions of infinite partial words achieving each value.