This paper explores words (finite strings over a fixed finite alphabet Σ with at least two letters) that are k-abelian equivalent to their reversals. Two words are k-abelian equivalent if and only if their multisets of factors of length no greater than k are the same. Thus aaba and abaa are 2-equivalent with factors {ε, a(3), b, aa, ab, ba}, but not 3-equivalent. That means aaba is a 2-abelian palindrome, but not a 3-abelian palindrome. (Note that the empty word ε is always a factor--and a palindrome.) On the other hand, baba is not a 2-palindrome, although it is a 1-palindrome (every word is). A real palindrome is a k-palindrome for all k.

The authors extend known counting results for palindromes to k-palindromes. One of the elegant tools is a non-self-intersecting fractal path defined by word substitution. It is used to specify, for all k ≥ 2 (except when k = 2 or 3 and |Σ| = 2), an infinite sequence with only finitely many distinct k-palindromes among its factors (finite subwords). For ordinary palindromes, such sequences are called “poor.” Thus, there are analogous k-poor sequences for k-palindromes. Actually, (abc)^ω is ≥2-poor trivially, with only four ≥2-palindromes: ε, a, b, c. The authors’ results are far more technically nuanced. For example, if k ≥ 3 and |Σ| ≥ 3, then there is a uniformly recurrent (every factor occurs infinitely often with bounded gaps between) k-poor sequence whose factors are closed under reversal.

The other principal result is analogous for rich words. A word of length n can have no more than n+1 distinct palindromic factors, and the limit is strict; words with n+1 palindromic factors are called “rich.” In the case of k-palindromes, a word of length n contains at most 1+n(n+1)/2 factors total, so a k-abelian rich word of length n cannot contain more than Θ(n²) k-palindromes. The authors prove that there are k-rich words with at least that many: for all k ≥ 2, there is a positive constant C such that for each n ≥ k there exists a word v of length n containing at least Cn² k-palindromes. In fact, C can be taken as 1/(4k). The word sought is constructed as v = a^p(ba^k-1)^m, where m is the closest integer to (n-k+1)/(2k) and p = n-km.

There are minor errors: at the end of line 8b on page 93, (4,2) should be (2,4). Occurrences of the superscript ∞ should be changed to ω for uniformity.

For the most part, the exposition is abundantly clear, and the rest just takes some satisfying rereading. There are more jewels like the ones mentioned, and this is an important contribution to the growing interest and development in counting palindromes and similar issues.