On growth and fluctuation of \(k\)-abelian complexity (Q2400973): Difference between revisions

Two words are abelian equivalent if each alphabet symbol occurs in both of them the same number of times (they yield the same Parikh vector). This equivalence can be generalized as follows. Let \(k\geq1\). Two words are \(k\)-abelian equivalent if each word of length at most \(k\) occurs in both of them the same number of times. The abelian complexity \(\mathcal{P}_{w}\left( n\right) \) of an infinite word \(w\) counts the number of factors of length \(n\) that are commutatively pairwise inequivalent. The \(k\)-abelian complexity \(\mathcal{P}_{w}^{k}\left( n\right) \) counts the number of equivalence classes of factors of \(w\) of length \(n\). The authors first investigate how much higher the \(\left( k+1\right) \)-abelian complexity of an infinite word can be compared to its \(k\)-abelian complexity. They show that if \(\operatorname{nec}_{m,k}\left( n\right) \) denotes the number of \(k\)-abelian equivalence classes of words of length \(n\) over an \(m\)-letter alphabet then, for \(k\geq2\), there is a word \(w\) such that \(\mathcal{P}_{w}^{k}\left( n\right) \) is bounded, but \(\mathcal{P}_{w} ^{k+1}\left( n\right) =\Theta\left( \operatorname{nec}_{m,k+1}\left( n\right) /\operatorname{nec}_{m,k}\left( n\right) \right) \). Next they provide the following result on the scope of fluctuation of \(k\)-abelian complexity. Let \(a_{1},a_{2},\ldots;\) \(b_{1},b_{2},\ldots;\) \(c_{1},c_{2},\ldots;\) \(d_{1},d_{2},\ldots\) be strictly increasing sequences of natural numbers. Then one can construct words \(w_{1}\) and \(w_{2}\) such that \(\mathcal{P}_{w_{1}}^{k}\left( a_{n}\right) =\Omega\left( g\left( a_{n}\right) \right)\), \(\mathcal{P}_{w_{1}}^{k}\left( b_{n}\right) =O\left( 1\right)\), \(\mathcal{P}_{w_{2}}^{k}\left( c_{n}\right) =\Omega\left( \operatorname{nec}_{m,k}\left( c_{n}\right) \right)\), \(\mathcal{P}_{w_{2}}^{k}\left( d_{n}\right) =O\left( d_{n}\right) \), where \(g\left( n\right) =o\left( \operatorname{nec}_{m,k}\left( n\right) \right) \).