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?



Elegant proof for $xy < yx \Leftrightarrow x^\mathbb{N} < y^\mathbb{N}$
Let $x, y \in \Sigma^+$.


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}$ (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}$.


