Aperiodic Two-Dimensional Words of Small Abelian Complexity

Abstract

In this paper we prove an abelian analog of the famous Nivat's conjecture linking complexity and periodicity for two-dimensional words: We show that if a two-dimensional recurrent word contains at most two abelian factors for each pair $(n,m)$ of integers, then it has a periodicity vector. Moreover, we show that a two-dimensional aperiodic recurrent word must have more than two abelian factors infinitely often. On the other hand, there exist aperiodic recurrent words with abelian complexity bounded by $3$, as well as aperiodic words having abelian complexity $1$ for some pairs $(m,n)$.