On a generalization of Abelian equivalence and complexity of infinite words

Juhani Karhumaki, Aleksi Saarela, Luca Q. Zamboni

Published 2013-01-22Version 1

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^*$ are said to be $k$-Abelian equivalent if for all $x\in 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 $\thicksim_k$ on $A^*,$ 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 $\omega \in A^\nats,$ we consider the associated complexity function $\mathcal {P}^{(k)}_\omega :\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}^{(k)}_{\omega}(n)<q^k(n)$ for some $k \in \ints ^+ \cup {+\infty}$ and $n\geq 0,$ the $\omega$ is ultimately periodic. Moreover if $\omega$ is aperiodic, then $\mathcal {P}^{(k)}_{\omega}(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\'edi'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.$