Return time complexity of Sturmian sequences

AbstractLet Rn(s) be the recurrence time of the initial n-word of an infinite sequence s. We have that s is periodic if and only if there exists M such that Rn(s)≤n for all n>M. For non-periodic sequences, therefore, Rn(s)≤n+1 is the possible lowest upper bound for Rn. We show that if Rn(s)≤n+1 for all n, then s is Sturmian. The opposite does not hold in general and we completely classify such Sturmian sequences