Solving the conjugacy equation $xy=yx$ in the free monoid

Question

I'm having some trouble on showing this:

Let $\sum$ be a finite alphabet, $x,\ y \in \sum^{*}$. Show: $$(xy=yx) \iff \exists s \in \sum^{*} ,\ i,j \in \mathbb{N}, (x = s^{i}, y = s^{j})$$

If we suppose xy = yx and $n<m$ then for the right implication I've done this (I'm not pretty sure):

Let $x,\ y \in \sum^{*}$ $$x = a_{1}a_{2}...a_{n}$$ $$y = b_{1}b_{2}...b_{n}$$ $$a_{1}a_{2}...a_{n}b_{1}b_{2}...b_{n} = b_{1}b_{2}...b_{n}a_{1}a_{2}...a_{n}$$ $$\implies a_{i} = b_{i}\ \forall i \in \{ 1,2,...,n \}$$ $$ b_{i} = b_{n+i} \forall i \in \{ 1,2,...,m-n \} $$ $$a_{i} = b_{n+i} \forall i \in \{ 1,2,...,m-n \}$$

But I don't know how to show that that $s$ exists.

I can see it has something to do with the gcd (greatest common divisor of the length of the two strings)

$$x = abaaba$$ $$y = abaabaaba$$ $$|x|= n \ \ \ |y|= m$$ $$xy = abaaba\bullet abaabaaba = abaabaaba\bullet abaaba = yx$$ Obviously $n < m$ and $gcd(n,m) = 3$

Do I need to use gcd to show that? What can I do next? Any suggestions?

Also... if someone has a better title for this question (and better tags) and edit it I'll be gratefull

Thanks in advance

Answer 1

Well, the proof I came up with looks fairly laborious, so I'll only sketch it here.

The $\Leftarrow$ implication is thankfully a trivial verification.

To prove the tougher reverse implication, essentially you can apply Levi's lemma repeatedly creating a sort of emulation of Euclid's algorithm (for gcd) as you correctly guessed (in part).

Assume without loss of generality, $|x|\leq |y|$, i.e. $x$ is not longer than $y$ (the other case is simlar). If $x$ is empty you are done ($i=0, s=y$). Otherwise, by Levi's lemma there exists a (possibly empty) string $w_1$ such that $y= w_1x = xw_1$. If $w_1$ is empty you are obviously done ($s=x=y$). If not, then apply the same reasoning repeatedly to obtain $y=xx\cdots xw_n = w_nx\cdots xx$ stopping (this phase of the proof) when $|w_n|<|x|$. The proof may well end here if $|w_n|=0$. If that's not the case, now you have to solve the shorter equation $xw_n = w_nx$ "the other way around", i.e. "unwinding" $x$ thus entering a 2nd phase of the proof, a phase which ends with an expansion of $x = w_nw_n\cdots w_nz_m = z_mw_n\cdots w_nw_n$ with $|z_m|<|w_n|$. A third phase (if necessary) would be solving $w_nz_m = z_mw_n$ and so forth. There are as many phases in the proof as there are non-zero remainders in the Euclid algorithm applied to $(|x|,|y|)$. The last non-zero-length "remainder" string (e.g. $z_m$ in the second phase detailed above is the desired $s$.)

(Note that I've used $n$ and $m$ with a different meaning than in your proof attempt.)

To give an example how the proof would work on a particular instance, say $x=a^3$ and $y=a^8$, it would first expand $y=xxa^2 = a^2xx$, then solve $xa^2 = a^2x$ by expanding $x=a^2a = a a^2$, so $s=a$. For $x=a^2$ and $y=a^8$ it would stop one phase sooner with $s=a^2$ ($x$ itself is the first "remainder").

EDIT: Besides my hackish proof, it turns out there are nicer ones in Proposition 1.4.3 of Luca & Varricchio's book Finiteness and Regularity in Semigroups and Formal Languages (1999); one way to prove it is as a consequence of Fine and Wilf's theorem... which is more or less the proof I gave above but more nicely broken into intermediate results. Let me know if you want me to expand on this point... Here's their other, direct proof though:

Proposition 1.4.3. Let $x, y \in A^+$ be such that $xy = yx$. Then there exists $t \in A^+$ such that $x,y \in t^*$.

Proof. Let $x, y \in A^+$ and $xy = yx$. We give the proof by induction on $|xy|$. If $|xy| =2$, then the only possibility is $x, y \in A$ and the statement is true for $t = x = y$. Let $|xy| > 2$ and suppose $|x| \leq |y|$. If $|x| = |y|$, then $x = y$ and also in this case one can take $t =x =y$. If $|x| < |y|$, then there exists $\mu \in A^+$ such that $x\mu =y =\mu x$. Since $|\mu x| < |xy|$, by the induction hypothesis there exists $t \in A^+$ such that $x, \mu \in t^*$. Since $y = \mu x$, one has also $y \in t^*$.

Note that this proof, unlike the more laborious one explicitly based on (or incorporating) Fine and Wilf's theorem doesn't immediately tell you that the length of $t$ is $\gcd(|x|,|y|)$.

And as point of terminology, two words $u, v$ of the form $u = xy$ and $v = yx$ are called conjugate, and the ensuing (reflexive and symmetric) binary relation is called conjugacy, which is why I changed the title that way.

Also on the issue of naming, the result that you ask a proof for is sometimes called the Lyndon-Schutzenberger theorem [1962], although not everyone seems to call it by that name; in fact most sources I've looked at don't do that. It preceded Fine and Wilf's slightly stronger result, itself dated to 1965.

N.B. Practically same short proof appears in Allouche and Shallit's (2003) book; there's free preview in Google Books for that one; see p. 12.

What I've done with my hackish proof was basically directly solving the word equation $xy=yx$ with $x$ and $y$ as unknowns. In general, all word equations where every unknown appear at most twice (aka quadratic word equation) is solvable this way, i.e. by repeatedly applying Levi's lemma (which in this context is also called the Nielsen transformation, by analogy with the one for groups.) Finding a solution in terms of some substring(s) and integer periods (exponents) is basically showing that the equation is parametrizable, which is what the right-hand side of your problems says. For more on solving word equation see chapter 9 in Lothaire's Combinatorics on Words (1983/1997), which actually starts with $xy=yx$ as the motivating example.