On a generalization of Abelian equivalence and complexity of infinite words

In this paper we introduce and study a family of complexity functions of infinite words indexed by k∈Z+∪{+∞}. Let k∈Z+∪{+∞} and A be a finite non-empty set. Two finite words u and v in A⁎ are said to be k-Abelian equivalent if for all x∈A⁎ of length less than or equal to k, the number of occurrences of x in u is equal to the number of occurrences of x in v. This defines a family of equivalence relations ∼k on A⁎, bridging the gap between the usual notion of Abelian equivalence (when k=1) and equality (when k=+∞). We show that the number of k-Abelian equivalence classes of words of length n grows polynomially, although the degree is exponential in k. Given an infinite word ω∈AN, we consider the associated complexity function Pω(k):N→N which counts the number of k-Abelian equivalence classes of factors of ω of length n. We show that the complexity function P(k) is intimately linked with periodicity. More precisely we define an auxiliary function qk:N→N and show that if Pω(k)(n)