# Proving that $xy=yx$ iff $x^2y^2=z^2$

I was given the following problem as homework:

Let $x$, $y$ be words over an alphabet $Σ$. Prove that $xy = yx$ iff there exists a word $z$ such that $x^2y^2 = z^2$.

I was hinted that I am supposed to approach this problem using structural induction. Considering the case where $|x| = |y|$, you obviously get $x=y=z$, as commutativity of concatenation satisfies only under that case.

Taking the case of $|x| < |y|$, we can conclude that $x$ is a prefix of $y$, assuming the induction hypothesis ($xy=yx$), and we can further say that $y=xt$, where $t$ can be assumed to be the trailing symbols of $y$ after the prefix $x$, and hence using $xy=yx$, we get $xxt = xtx$. And I'm stuck here. Can somebody guide me?

• Think of filling the blank $x\underline{\ \ \ }\ y=z^2$ where the blank has length $|x|+|y|$. You have to copy $y$ to the first half and copy $x$ to the second half: the only possibility of the blank is $yx$, so $yx=xy$. – Willard Zhan Mar 1 '18 at 0:34
• I think @WillardZhan gives an elegant solution! If $xxyy=zz$ then $|z| = |x|+|y|$ and $z$ begins with $x$ and ends with $y$. Thus $z=xy$ and $xxyy=xyxy$, so $xy=yx$. – Hendrik Jan Mar 1 '18 at 22:45

One direction is easy: if $xy = yx$ then $x^2y^2 = xxyy = xyxy = (xy)^2$.

In the other direction, we split into cases. If $|x|=|y|$ then, as you mention, $x = y$.

If $|x|<|y|$ then let $y=y_1y_2$, where $|y_1|=|y|-|x|$ and $|y_2|=|x|$. We have $z = x^2y_1$ and $z = y_2y = y_2y_1y_2$. Since $|x| = |y_2|$, it follows that $x = y_2$. Substituting this, we obtain $y_2^2 y_1 = y_2y_1y_2$, and so $y_2y_1 = y_1y_2$. This implies that $xy = y_2y_1y_2 = y_1y_2y_2 = yx$.

If $|y| < |x|$, then notice that $(y^R)^2(x^R)^2 = (z^R)^2$ (where $w^R$ is the reverse of $w$) and $|y^R| < |x^R|$, so we can apply the previous case to deduce that $y^R x^R = x^R y^R$ and so $xy = yx$.

Let us use this opportunity to characterize when $xy=yx$, by proving that there exist a word $w$ and integers $n,m$ such that $x = w^n$ and $y = w^m$ iff $x^2y^2$ is a square.

One direction is easy: if $x = w^n$ and $y = w^m$ then $x^2y^2 = w^{2n+2m} = (w^{n+m})^2$.

In the other direction, we use induction on $|x|+|y|$. The base case $x=y=\epsilon$ is trivial. For the inductive case, we split into cases. If $|x| = |y|$ then $x = y$ and so we can take $w = x = y$.

If $|x| < |y|$ then as before we get that $y = y_1 x = x y_1$, which implies that $y_1^2 x^2 = (y_1 x)^2$. The inductive hypothesis shows that there exist $w,n,m$ such that $y_1 = w^n$ and $x = w^m$. Then $y = y_1 x = w^{n+m}$.

We have shown that $xy = yx$ iff there exists a word $w$ and integers $n,m$ such that $x = w^n$ and $y = w^m$.

Equivalently, let us define the radical $\sqrt{x}$ of a word $x$ as the shortest word such that $x$ is a power of $\sqrt{x}$. Then $xy = yx$ iff $\sqrt{x} = \sqrt{y}$.

Indeed, if $\sqrt{x} = \sqrt{y}$ then clearly $xy = yx$. Conversely, suppose that $xy = yx$. Then there exist $w,n,m$ such that $x = w^n$ and $y = w^m$. We can assume that $w = \sqrt{w}$. I claim that $\sqrt{x} = w$. Otherwise, there exists a word $z$ shorter than $w$ and an integer $\ell$ such that $x = z^\ell$. The word $x$ thus has both $|w|$ and $|z|$ as periods ($p$ is a period of $x$ if $x_i = x_{i+p \bmod |x|}$ for all $i$), and so $|w| \bmod |z|$ is also a period. If $|w| \bmod |z| \neq 0$ then this contradicts the fact that $z$ is the radical of $x$ (since $x$ is a power of $x_1 \ldots x_{|w| \bmod |z|}$). If $|z|$ divides $|w|$ then $w = z^{|w|/|z|}$, contradicting the assumption $w = \sqrt{w}$. We reach a contradiction either way, and so $\sqrt{x} = w$. By the same reasoning, $\sqrt{y} = w$, and so $\sqrt{x} = \sqrt{y}$.

• After simplifying my solution, it is identical to the one by OmG. – Yuval Filmus Feb 28 '18 at 23:30

From $xy = yx$, we can say $x^2y^2 = x (xy) y = x (yx) y = (xy)^2$, Hence $z = xy$. Hence, first part is proved.

Now, suppose there exists a word $z$ such that $x^2 y^2 = z^2$. Moreover, suppose $|x| < |y|$ w.l.o.g. Hence there is a $w$ such that $x^2w = w'y$, $ww'=y$, $|w| = |y|-|x|$, and $|w'| = |x|$. As $x^2w = w'y$ and $|w'|=|x|$, we can say $w' = x$. Hence, $x^2w = x xw = xy$. Therefore, $xw = y$. Also, $y = ww'$ and we know that $w' = x$, so $y = wx$.

From the above argument $xy = x(xw)$ and $yx = (xw) x = x(wx) = x (xw) = xy$. Here, the proof is completed.

• I don't understand how $x^2w = w'y$ and $|w'| = |x|$ leads to $w'=x$. Could you please clarify more on that step? – Vishhvak Srinivasan Feb 28 '18 at 23:44
• @Vish As these two strings are equal, so first $|x|$ characters of should be equal. as $|x|$ first characters of $w'y$ is $w'$, so $w' = x'$. – OmG Feb 28 '18 at 23:55
• Yes, got that. Thank you so much for the crisp answer! – Vishhvak Srinivasan Feb 28 '18 at 23:56