10
$\begingroup$

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?

$\endgroup$
6
  • 4
    $\begingroup$ 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$. $\endgroup$
    – 1001
    Commented Aug 29, 2023 at 19:42
  • $\begingroup$ @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 $\endgroup$
    – thematdev
    Commented Aug 29, 2023 at 20:11
  • 3
    $\begingroup$ 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 $\endgroup$ Commented Aug 29, 2023 at 20:48
  • 1
    $\begingroup$ Technically you didn't define the $<$ order on infinite words. $\endgroup$ Commented Aug 29, 2023 at 22:27
  • 3
    $\begingroup$ 1 and 2 are only equivalent if $x$ is nonempty. $\endgroup$ Commented Aug 30, 2023 at 8:57

1 Answer 1

7
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ You need $x$ to be nonempty in the converse argument. $\endgroup$ Commented Aug 30, 2023 at 9:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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