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?

  • 1
    $\begingroup$ 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$. $\endgroup$ – Willard Zhan Mar 1 '18 at 0:34
  • 1
    $\begingroup$ 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$. $\endgroup$ – 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}$.

| cite | improve this answer | |
  • $\begingroup$ After simplifying my solution, it is identical to the one by OmG. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ I don't understand how $x^2w = w'y$ and $|w'| = |x|$ leads to $w'=x$. Could you please clarify more on that step? $\endgroup$ – Vishhvak Srinivasan Feb 28 '18 at 23:44
  • $\begingroup$ @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'$. $\endgroup$ – OmG Feb 28 '18 at 23:55
  • $\begingroup$ Yes, got that. Thank you so much for the crisp answer! $\endgroup$ – Vishhvak Srinivasan Feb 28 '18 at 23:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.