Another generalization of abelian equivalence: binomial complexity of infinite words (Q496049): Difference between revisions

Two words are abelian-equivalent if they induce the same Parikh vector, i.e., one can be obtained by permutation of symbols of the other. A generalization of this term is \(k\)-abelian equivalence, introduced by Karhumäki. Two words are \(m\)-abelian-equivalent, \(m\geq0\), if any of their factors of length at most \(m\) occurs in both words the same number of times. Another generalization -- \(m\)-binomial equivalence -- is obtained if occurrences of scattered subwords (subsequences) instead of occurrences of factors are counted. The number of occurrences of a scattered subword \(v\) in a word \(u\) is denoted as \(\binom {u}{v}\), since these counts have properties similar to those of binomial numbers. The \(m\)-binomial complexity of an infinite word \(x\) is a function \(\mathbf{b}_{x}^{\left( m\right) }\left( n\right) \) expressing the number of \(m\)-binomial equivalence classes containing a factor of \(x\) of length \(n\). The paper deals with \(m\)-binomial complexity of two classes of infinite words. If \(x\) is a Sturmian word then it is known that \(x\) has constant abelian complexity, in particular, \(\mathbf{b}_{x}^{\left( 1\right) }\left( n\right) =2\) for \(n\geq0\). The authors prove a general result stating that \(\mathbf{b}_{x}^{\left( m\right) }\left( n\right) =n+1\) for \(m\geq 2\), \(n\geq0\). If \(x\) is a fixed point of a Parikh-constant morphism (as the word of Thue-Morse) they prove that, for any \(m\geq2,\) there is a constant \(C_{x,m}\) such that \(\mathbf{b}_{x}^{\left( m\right) }\left( n\right) \leq C_{x,m}\) for all \(n\geq0\). They show as well that if an infinite recurrent word (a word where each finite factor occurs infinitely many times) \(x_{0}x_{1}\cdots\) has bounded \(2\)-binomial complexity, then the frequency \(\lim_{n\rightarrow\infty}\frac{\binom{x_{0}x_{1}\cdots x_{n-1}}{a}}{n}\) of each of its symbols \(a\) exists and is rational. Finally, the authors introduce a morphism mapping words to matrices and word concatenation to matrix product. The values occurring in the matrix assigned to a word \(v\) are of the form \(\binom{v}{z}\) where \(z\) is a prefix of a fixed word \(u\). The morphism is different from the well-known Parikh matrix morphism.