Arithmetical Complexity of Infinite Words
S. V. Avgustinovich, Dmitry Fon-Der-Flaass, Anna E. Frid · 2003
We introduce a new notion of the arithmetical complexity of a word, that is the number of words of a given length which occur in it in arithmetical progressions. The arithmetical complexity is related to a well-known function of subword complexity and cannot be less than it. However, our main results show that the behavour of the arithmetical complexity is not determined only by the subword complexity growth: if the latter grows linearly, the arithmetical complexity can increase both linearly and exponentially. To prove it, we consider a family of D0L words with high arithmetical complexity and a family of Toeplitz words with low one. In particular, we nd the arithmetical complexity of the Thue-Morse word and of the paperfolding word. 1