Topological invariants for words of linear factor complexity (Q2672961)

This paper studies a combinatorics problem dealing with infinite words \(\mathbf{w}\) over a finite alphabet. A factor \(x\) of such a word is a contiguous block sitting inside \(\mathbf{w}\), and the set of all factors of \(\mathbf{w}\) is written \(\operatorname{Fac}(\mathbf{w})\). The word \(\mathbf{w}\) is said to be \textit{recurrent} if every finite factor of \(\mathbf{w}\) occurs infinitely often in \(\mathbf{w}\), and is said to be \textit{uniformly recurrent} if it is recurrent and for all finite factors \(x\), every pair of consecutive occurrences of \(x\) in \(\mathbf{w}\) is separated by a constant number of symbols (depending on \(x\)). The \textit{factor complexity} function \(p_{\mathbf{w}} (n)\) counts the number of distinct length-\(n\) factors of \(\mathbf{w}\). The author declares two infinite words \(\mathbf{w}\), \(\mathbf{w}'\) to be equivalent if their sets of finite factors coincide; then \([\mathbf{w}]\) is the equivalence class corresponding to \(\mathbf{w}\). He then constructs a partial order wherein \([\mathbf{w}] \preceq [\mathbf{w}']\) if \(\operatorname{Fac}(\mathbf{w}) \supseteq\operatorname{Fac}(\mathbf{w}')\). He then defines \(\operatorname{Rec}(\mathbf{w}) = \{[\mathbf{z}]:[\mathbf{w}]\preceq [\mathbf{z}] \,\&\, \mathbf{z}\text{ recurrent}\}\) and, analogously, \(\operatorname{URec}(\mathbf{w})\) where \(\mathbf{w}\) is required to be uniformly recurrent. There are now two main results. Suppose \(p_{\mathbf{w}}(n) \leq Cn\) for all \(n \geq 1\). Then the cardinality of \(\operatorname{Rec}(\mathbf{w})\) is bounded above by a function of the first difference of the factor complexity of \(\mathbf{w}\) and \(C\), and a similar bound holds for \(\operatorname{URec}(\mathbf{w})\). The author obtains these bounds by a mixture of ingenious combinatorial and topological arguments. The reader will observe that in Definition (1.4) one needs to replace Rec with URec.