The subword complexity of polynomial subsequences of the Thue-Morse sequence (Q2143625)

Let \((t(n))_{n \geq 0}\) denote the well-known Thue-Morse sequence over the binary alphabet. A result of \textit{Y. Moshe} [Theor. Comput. Sci. 389, No. 1--2, 318--329 (2007; Zbl 1135.68046)] states that, for all \(H \in \mathbb{Q}[T]\) with \(H(\mathbb{N}) \subseteq \mathbb{N}\) and \(\mathrm{deg}(H)=2\), all the subsequences \((t(H(n)))_{n \geq 0}\) attain the maximal subword complexity. This answered positively a question that was raised by \textit{J.-P. Allouche} and \textit{J. Shallit} [Automatic sequences. Theory, applications, generalizations. Cambridge: Cambridge University Press (2003; Zbl 1086.11015)] as to whether or not the subword complexity of the subsequence \((t(n^2))_{n \geq 0}\) attains the maximal value. In this paper, the author settles an open problem of Moshe by proving that, for \(H \in \mathbb{Q}[T]\) with \(H(\mathbb{N}) \subseteq \mathbb{N}\) and \(\mathrm{deg}(H)\geq 2\), the subword complexity of \((t(H(n)))_{n \geq 0}\) at \(m\) is \(2^m\) for all integers \(m \geq 1\), that is, the subword complexity of polynomial subsequences of the Thue-Morse sequence attains the maximal value.