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 ω ∈ A N , 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 q k : N → N and show that if P ω ( k ) ( n ) < q k ( n ) for some k ∈ Z + ∪ { + ∞ } and n ⩾ 0 , then ω is ultimately periodic. Moreover if ω is aperiodic, then P ω ( k ) ( n ) = q k ( n ) if and only if ω is Sturmian. We also study k-Abelian complexity in connection with repetitions in words. Using Szemerédiʼs theorem, we show that if ω has bounded k-Abelian complexity, then for every D ⊂ N with positive upper density and for every positive integer N, there exists a k-Abelian N-power occurring in ω at some position j ∈ D .