Aperiodic two-dimensional words of small abelian complexity (Q2327230)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Aperiodic two-dimensional words of small abelian complexity
scientific article

    Statements

    Aperiodic two-dimensional words of small abelian complexity (English)
    0 references
    0 references
    14 October 2019
    0 references
    The paper contains several results on abelian complexity of two-dimensional words. Here, for a two-dimensional word \(w\), the abelian complexity \(a_w(m,n)\) is defined as the number of different Parikh vectors (that is, vectors of the number of occurrences of symbols) of factors of \(w\) of size \(m \times n\). For one-dimensional words it is known that if \(a_w(n)=1\) for some \(n\), then the word is periodic, and the words with \(a_w(n)\equiv 2\) are exactly Sturmian words. For two-dimensional words, as usual, the situation can be more complicated. The results of the paper are the following. First, a construction of an aperiodic two-dimensional word consisting of blocks of the form \(\begin{matrix} 0 &1\\ 1&0\end{matrix}\) and \(\begin{matrix} 1 &0\\ 0&1\end{matrix}\) such that its abelian complexity \(a_w(4m,2n)\) is equal to \(1\) for all integers \(m\), \(n\). This is also a word of abelian complexity bounded by \(3\). Second, a proof that, despite the simple non-recurrent example of a word containing only one \(1\) and all the other symbols equal to \(0\), a recurrent aperiodic two-dimensional word cannot have the abelian complexity bounded by \(2\), or even have only a finite number of pairs \((m,n)\) such that \(a_w(m,n)>2\). On the other hand, the author gives a rather general construction of recurrent (very) aperiodic words of abelian complexity always equal to \(2\) or \(3\).
    0 references
    abelian complexity
    0 references
    Nivat conjecture
    0 references
    two-dimensional word
    0 references
    0 references

    Identifiers