On the least number of palindromes in two-dimensional words (Q2286748)

The notion of palindromic factor in a word can be extended to bidimensional words (also called pictures) by extending the notion of reverse of a word to 2D arrays. The authors give tight bounds on the minimal number of 2D palindromes in a bidimensional word, depending on the alphabet size, both in the periodic and in the aperiodic case. In particular, they prove that any 2D infinite binary word must contain at least \(20\) distinct 2D palindromic sub-blocks, and this number becomes equal to the size of the alphabet for larger alphabets. In the case of aperiodic words, they show that the minimum is between \(20\) and \(28\) for 2D binary words, it is \(5\) for ternary words and it is equal to the size of the alphabet for larger alphabets.