On \(k\)-abelian palindromes (Q1753996)

A finite word is called a \textit{palindrome} if it is equal to its reversal, that is, if it is the same when read from left to right or from right to left. It is well known that a finite word of length \(n\) can contain at most \(n+1\) distinct palindromes as its factors. Finite words having the maximal number of distinct factors that are palindromes are called \textit{rich}. Similarly, an infinite rich word is a word such that each of its factors is rich. On the other hand, infinite words containing only finitely many distinct palindroms as their factors are called \textit{poor}. It is known that there exist poor words even when the set of factors is closed under reversal. In this paper the authors consider a \(k\)-abelian modification of these notions. Two words are called \(k\)-\textit{abelian equivalent} if they contain the same number of occurrences of each factor of length at most \(k\). Thus, the classical notion of abelian equivalence corresponds to \(1\)-abelian equivalence. A word is a \(k\)-\textit{abelian palindrome} if it is \(k\)-abelian equivalent to its reversal. In this paper the authors deal with the question: how many distinct \(k\)-palindromes can a (finite or infinite) word contain? A \(k\)-\textit{abelian palindromic poor word} is defined as an infinite word containing only finitely many \(k\)-abelian palindromes. One of the main results of the paper is a complete classification of the pairs \((k, \ell)\), for existence of \(k\)-poor words for an alphabet of cardinality \(\ell\). It is shown that: -- for \(k=1\) and for the pairs \((2,2), (3,2)\) it is not possible to have \(k\)-abelian palindromic poor words; -- for the pairs \((2,3), (4,2)\) there exist \(k\)-abelian poor words, but there are no \(k\)-abelian palindromic poor words having a set of factors closed under \(k\)-abelian reversal; -- for all the other cases it is possible to construct uniformly recurrent \(k\)-abelian palindromic poor words having a set of factors that is closed under reversal. This last construction uses self-avoiding fractal curves. The authors also define \(k\)-\textit{abelian palindromic rich words} as finite words of length \(n\) containing at least \(\frac{n^2}{4k}\) inequivalent \(k\)-abelian palindromes. This definition comes from another main result proved in the paper, stating that there exist finite words of length \(n\) which have \(\Theta(n^2)\) inequivalent \(k\)-abelian palindromic factors.