Languages invariant under more symmetries: Overlapping factors versus palindromic richness

Factor complexity CC and palindromic complexity PP of infinite words with language closed under reversal are known to be related by the inequality P(n)+P(n+1)≤2+C(n+1)−C(n)P(n)+P(n+1)≤2+C(n+1)−C(n) for every n∈Nn∈N . Words for which the equality is attained for every nn are usually called rich in palindromes. We show that rich words contain infinitely many overlapping factors. We study words whose languages are invariant under a finite group GG of symmetries. For such words we prove a stronger version of the above inequality. We introduce the notion of GG-palindromic richness and give several examples of GG-rich words, including the Thue–Morse word as well.