*-Sturmian words and complexity (Q558168)

Given an infinite sequence, the complexity function \(p(n,w)\) counts the number of different subwords of \(w\) with size \(n\). Since Hedlund and Morse, it is known that when one considers a binary sequence, the sequence is ultimately periodic if and only if \(p(n,w) \leq n\) for a given \(n\). Non-periodic sequences with the lowest complexity satisfy \(p(n,w)=n+1\) for every \(n\); they are called Sturmian sequences. They have zero entropy and correspond to the discrete coding of lines with irrational slope in \({\mathbb R}^2\). In this paper, the authors introduce a new complexity function \(p_{\star}(n,w)\) which counts the number of different subwords of \(w\) that appear infinitely often in \(w\). Then, \(p_{\star}(n,w) \leq p(n,w)\), with equality when \(w\) is a Sturmian sequence for instance. The authors define \({\star}\)-Sturmian sequences to be infinite words \(w\) satisfying \(| | A| _1 - | B| _1| \leq 1\) for any subword \(A\), \(B\) having the same size and appearing infinitely often in \(w\). They prove that this is equivalent with \(p_{\star}(n,w) \leq n+1\) for any \(n\). Moreover, such sequences are either Sturmian or codings of lines with rational slopes. A class of examples with explicit complexity is described. In general, such sequences can have a large complexity (examples are given with \(p(n,w) \geq 2^{n^{1-\varepsilon}}\)) but they always have a zero entropy.