# Elegant proof for $xy < yx \Leftrightarrow x^\mathbb{N} < y^\mathbb{N}$

Let $$x, y$$ be finite words over totally ordered alphabet and $$<$$ denote the lexicographical order, i.e for two not necessarily finite words we say $$x < y$$ iff one of the following holds

1. There are words $$u, x^\prime, y^\prime$$ and letters $$a < b$$ such that $$x = uax^\prime, y = uby^\prime$$
2. $$y = xu$$ for some non-empty word $$u$$

Then the following are equivalent

1. $$xy < yx$$
2. $$x^\mathbb{N} < y^\mathbb{N}$$, where $$x^\mathbb{N}$$ denotes infinite word $$xxxx\ldots$$

$$x <^* y$$ iff $$xy < yx$$ is a total order(which we're trying to prove by equivalence)

This new total order is another extension of "weak lexicographical order" where only first condition considered, i.e $$x$$ and $$xu$$ are incomparable for non-empty $$u$$(note that $$xy$$ and $$yx$$ always have the same length so we're not using "strong" order). It is naturally arising from the following problem:

Let $$x_1, \ldots, x_n$$ be finite words on totally ordered alphabet, find $$\sigma \in S_n$$ minimizing $$x_{\sigma(1)}x_{\sigma(2)}\ldots x_{\sigma(n)}$$

The solution is to sort $$x_i$$ with respect to order $$<^*$$. If the sequence is not sorted according to this order, then there are adjacent elements $$x, y$$ such that $$xy > yx$$, by swapping them we'll decrease word which we are minimizing.

But it might be tedious to prove that $$<^*$$ is transitive, so instead I suggest equivalent definition of $$<^*$$, that is $$x <^* y$$ iff $$x^\mathbb{N} < y^\mathbb{N}$$. Now transitivity is obvious.

But is there elegant and simple proof of equivalence not involving much of casework on $$|x| <> |y|$$, etc?

• Note sure if this elegant enough, but observe that for all $n \in \mathbb{N}$ the inequality $xy < yx$ implies that $$x^ny^n < y^nx^n$$ by repeatedly swapping pairs of $x$ and $y$. It follows that $x^\mathbb{N} \leq y^\mathbb{N}$. Note that inequality can only hold if the basic period of the infinite word divides both $x$ and $y$, in which case we would have $xy = yx$.
– 1001
Commented Aug 29, 2023 at 19:42
• @1001 yes, I think it's elegant enough, in some sense your claim is taking limit of both sides $\lim\limits_{n \to \infty} x^ny^n = x^\mathbb{N}$. You can post an answer if you prove 2 -> 1 too, your comment just proves 1 -> 2 Commented Aug 29, 2023 at 20:11
• But 2->1 follows from this: if 1 does not hold, then $xy\ge yx$, hence $x^ny^n\ge y^nx^n$ and taking the limit in $n$ we see that 2 also does not hold Commented Aug 29, 2023 at 20:48
• Technically you didn't define the $<$ order on infinite words. Commented Aug 29, 2023 at 22:27
• 1 and 2 are only equivalent if $x$ is nonempty. Commented Aug 30, 2023 at 8:57

Let $$x, y \in \Sigma^+$$.
Observe that for all $$n \in \mathbb{N}$$ the inequality $$xy implies that $$x^ny^n by repeatedly swapping pairs of $$x$$ and $$y$$. It follows that $$x^\mathbb{N}\leq y^\mathbb{N}$$ (i.e. the two infinite sequences are equal, or $$y^\mathbb{N}$$ is greater at the first position they differ). Note that equality can only hold if the basic period of the infinite word divides both $$|x|$$ and $$|y|$$, in which case we would have $$xy=yx$$.
Conversely, $$xy \geq yx$$ implies $$x^\mathbb{N} \geq y^\mathbb{N}$$.
• You need $x$ to be nonempty in the converse argument. Commented Aug 30, 2023 at 9:00