On a generalization of Abelian equivalence and complexity of infinite words

Abstract

In this paper we introduce and study a family of complexity functions of infinite words indexed by $k \in \ints ^+ \cup {+\infty}.$ Let $k \in \ints ^+ \cup {+\infty}$ and $A$ be a finite non-empty set. Two finite words $u$ and $v$ in $A^{\ast }$ are said to be $k$-Abelian equivalent if for all $x\in A^{\ast }$ 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 ${\sim }_k$ on $A^{\ast },$ bridging the gap between the usual notion of Abelian equivalence (when $k=1$) and equality (when $k=+\infty ).$ 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 $ω\in A^\nats,$ we consider the associated complexity function $\mathcal {P}^{(k)}_ω:\nats \rightarrow \nats$ which counts the number of $k$-Abelian equivalence classes of factors of $\omega$ of length $n.$ We show that the complexity function ${\mathcal{P}}^{(k)}$ is intimately linked with periodicity. More precisely we define an auxiliary function $q^k: \nats \rightarrow \nats$ and show that if ${\mathcal{P}}_{\omega }^{(k)}(n)<q^k(n)$ for some $k \in \ints ^+ \cup {+\infty}$ and $n\ge 0,$ the $\omega$ is ultimately periodic. Moreover if $\omega$ is aperiodic, then ${\mathcal{P}}_{\omega }^{(k)}(n)=q^k(n)$ if and only if $\omega$ is Sturmian. We also study $k$-Abelian complexity in connection with repetitions in words. Using Szemerédi's theorem, we show that if $\omega$ has bounded $k$-Abelian complexity, then for every $D\subset \nats$ with positive upper density and for every positive integer $N,$ there exists a $k$-Abelian $N$ power occurring in $\omega$ at some position $j\in D.$