Three palindromes

Created at 2023-08-24

Are there words $X, Y, Z \in \Sigma^*$ over some alphabet $\Sigma$ such that $XYZ$, $YZX$ and $ZXY$ are pairwise distinct palindromes?

What follows is an informal answer to this question (don't be spoiled before taking a hit at the problem yourself!). A nice, more rigorous formulation has been written down by my friend Markus Himmel.

There is a very natural geometic way to rephrase the situation given three words $X, Y, Z$. Imagine $n \coloneqq \left|XYZ\right|$ points placed on a circle with equal angles. Start at some point and assign the characters of the word $XYZ$ to the points in clockwise direction. Depending on where you start to read, you will be able to find, among others, the words $YZX$ and $ZXY$ written on the circle because they are *rotations* of $XYZ$.

Here is another observation. If you draw a line that cuts the circle in half and intersects the circle (at least once) exactly in the middle of two adjacent points and characters on opposite sides of the line are equal, then the word that is written on the circle starting and ending at these points is a palindrome. This means that being a palindrome is a *reflection* symmetry of a word written on a circle. In the image to the right, you can see how this plays out for the palindrome Aibohphobia.

What happens if we have two axes of symmetry, i.e. two lines we can reflect on without changing the assignment of characters to the points? Then executing both reflections one after the other does not change the the assignment of characters either -- and together these reflections form a rotation! This means that any circular word with two different axes of symmetry is repetitive: No matter where you cut it into a word, the word consists of some subsequence of letters repeated at least twice.

In the given situation, we have three axes of symmetry: the ones proving that $XYZ$, $YZX$ and $ZXY$ are palindromes. We will not assume that these axes are distinct for now. If we number the letters in $XYZ$ from $0$ to $n-1$ and set $a \coloneqq \left|X\right|$ and $b \coloneqq \left|XY\right|$, then the three axes of symmetry lie to the left of the $0$th, the $a$th, and the $b$th letter, and combining the reflections, we see that the circle of letters is kept unchanged if we rotate it by $2a$ or $2b$ letters.

Now, let $g \coloneqq \operatorname{gcd}(a, b)$ be the greatest common divisor of $a$ and $b$. A mathematical result called Bezout's identity shows that there are integers $k, \ell$ such that $ka + \ell b = g$, and so $k(2a) + \ell(2b) = 2g$. In other words: We can rotate the circle by $2g$ characters by repeatedly rotating it by $2a$ and $2g$ characters, each time either clockwise or counterclockwise. So rotating $XYZ$ be $2g$ letters, or a multiple of $2g$ letters, keeps it unchanged!

If $a/g \in \mathbb{Z}$ is even, then $2g$ divides $a$, showing that $YZX$, which is obtained by rotating $XYZ$ by $a$ letters, is equal to $XYZ$. Similarly, if $b/g \in \mathbb{Z}$ is even, then $ZXY = XYZ$, and if $(a-b)/g \in \mathbb{Z}$ is even, then $YZX = ZXY$.

Let us consider: Is it possible that $XYZ$, $YZX$ and $ZXY$ are distinct? If that were the case, then $a$, $b$ and $(a - b)$ would all need to be odd. But if $a$ and $b$ are odd, $(a-b)$ is certainly even! This way we have proved that said three words cannot be distinct if they are all palindromes.