String Rearrangement Inequalities and
a Total Order Between Primitive Words ^††thanks: Corresponding author: Kai Jin (). Supported by National Natural Science Foundation of China 62002394.

This result should be well-known. A simple proof is as follows.

This is a trivial fact and is implied by Lemma 1 (condition 1); proof omitted.

Proof: The prefix and suffix of $A$ with length $|A|-|\mathsf{root}(A)|$ are the same, which implies that $j\geq|A|-|\mathsf{root}(A)|$. Consequently, $|\mathsf{root}(A)|\geq|A|-j=k$.

Proof: Denote $S=\mathsf{root}(A)$ and assume $|S|<|A|$. Therefore, $A=S^{d}~{}(d\geq 2)$. Suppose to the opposite that $k<|\mathsf{root}(A)|$. Let $B$ be the prefix of $S$ with length $k$, and $B^{\prime}$ be the suffix of $S$ such that $S=BB^{\prime}$. As $k<|S|$, we have $j>|A|-|S|\geq|S|$. Further since the suffix of $A$ with length $j$ (which starts with $B^{\prime}B$) equals to the prefix of $A$ with length $j$ (which starts with $S=BB^{\prime}$), we get $S=B^{\prime}B$. Applying Fact 1, $\mathsf{root}(A)=S$ is non-primitive. Contradictory.

We are ready to prove the lemma. When $|A|$ is a multiple of $k$, $A$ is a power of its prefix of length $k$, which means $|\mathsf{root}(A)|\leq k$. Further by Claim 1, $|\mathsf{root}(A)|=k$. Next, assume $|A|$ is not a multiple of $k$. Since $|A|$ is a multiple of $|\mathsf{root}(A)|$, we see $|\mathsf{root}(A)|\neq k$. Further by Claims 1 and 2, it follows that $|\mathsf{root}(A)|=|A|$. ∎

Assume that $A,B$ are words that consist of the decimal symbols ‘0’,…,‘9’. The proof can be easily extended to the more general case.

Let $\alpha,\beta$ denote the number represented by strings $A,B$. For example, string ‘89’ represents number 89. Denote $a=|A|$ and $b=|B|$. Observe that

Moreover,

So, $AB<BA\Leftrightarrow 0.\dot{\alpha}<0.\dot{\beta}\Leftrightarrow R(A)<R(B).$ Similarly, (5) and (6) hold. ∎

Consider the comparison of $R(A_{i})$ and $R(A_{j})$. Assume $|A_{i}|\leq|A_{j}|$. Otherwise it is symmetric.

First, consider the case $R(A_{i})=R(A_{j})$. Let $m_{1}=|A_{j}|$ and $m_{2}=|A_{i}|$. We know $A_{i}^{m_{1}}=A_{j}^{m_{2}}$ because $R(A_{i})=R(A_{j})$. Applying Lemma 1 (condition 3), $A_{i}=C^{k}$ and $A_{j}=C^{l}$ for some $C,k,l$. Further since $A_{i},A_{j}$ are primitive, $A_{i}=C=A_{j}$. It follows that $M_{i}=M_{j}$. Next, assume that $R(A_{i})\neq R(A_{j})$.

Let $p=\deg_{A_{j}}(A_{i})$. Thus, $A_{j}=A_{i}^{p}S$, where $p\geq 0$ and $A_{i}$ is not a prefix of $S$. Be aware that $p\leq\deg_{\mathcal{A}}(A_{i})$ by the definition of $\deg_{\mathcal{A}}(A_{i})$.

According to Lemma 3, the comparison of $R(A_{i})$ and $R(A_{j})$ equals to the comparison of $A_{i}A_{j}$ and $A_{j}A_{i}$. Further since $A_{j}=A_{i}^{p}S$, it equals to the comparison of $A_{i}^{p}A_{i}S$ and $A_{i}^{p}SA_{i}$. In the following, we discuss two subcases.

Recall that $A_{i}$ is not a prefix of $S$. In this subcase, we will find an unequal letter if we compare $A_{i}$ with $S$ (starting from the leftmost letter). Comparing $A_{i}^{p}A_{i}S$ and $A_{i}^{p}SA_{i}$ is thus equivalent to comparing the prefixes $A_{i}^{p}A_{i}$ and $A_{i}^{p}S$.

Notice that $A_{i}^{p}A_{i}=A_{i}^{p+1}$ and $A_{i}^{p}S=A_{j}$ are also prefixes of $M_{i}$ and $M_{j}$, respectively (note that $A_{i}^{p+1}$ is a prefix of $M_{i}$ because $M_{i}$ is the $(\deg_{\mathcal{A}}(A_{i})+2)$-th power of $A_{i}$ and $\deg_{\mathcal{A}}(A_{i})\geq p$ as mentioned above). Therefore, comparing $M_{i}$ and $M_{j}$ is also equivalent to comparing the two prefixes $A_{i}^{p}A_{i}$ and $A_{i}^{p}S$.

Altogether, comparing $R(A_{i}),R(A_{j})$ is equivalent to comparing $M_{i},M_{j}$.

Assume $A_{i}=ST$. Comparing $A_{i}^{p}A_{i}S$ and $A_{i}^{p}SA_{i}$ is just the same as comparing $A_{i}^{p}STS$ and $A_{i}^{p}SST$. It reduces to proving that comparing $M_{i}$ and $M_{j}$ also reduces to comparing $A_{i}^{p}STS$ and $A_{i}^{p}SST$.

First, we argue that $ST\neq TS$. Suppose to the opposite that $ST=TS$. Applying Lemma 1 (condition 1), $S=C^{k}$ and $T=C^{l}$ for some $C,k,l$. This implies that $A_{i}$ and $A_{j}$ are both powers of $C$, and hence $R(A_{i})=R(A_{j})$, contradictory.

Observe that $A_{i}^{p}STS$ is a prefix of $A_{i}^{p}STST=A_{i}^{p+2}$, which is a prefix of $M_{i}$ (because $M_{i}$ is the $(\deg_{\mathcal{A}}(A_{i})+2)$-th power of $A_{i}$ and $\deg_{\mathcal{A}}(A_{i})+2\geq p+2$).

Observe that $p>0$. Otherwise $A_{j}=A_{i}^{0}S$ is shorter than $A_{i}$, which contradicts our assumption $|A_{i}|\leq|A_{j}|$. As a corollary, $A_{i}$ is a prefix of $A_{j}=A_{i}^{p}S$. Therefore, $A_{i}^{p}SST=A_{i}^{p}SA_{i}=A_{j}A_{i}$ is a prefix of $A_{j}^{2}$, which is a prefix of $M_{j}$.

To sum up, $M_{i}$ and $M_{j}$ admit $A_{i}^{p}STS$ and $A_{i}^{p}SST$ as prefixes, respectively. Further since $TS\neq ST$, comparing $M_{i},M_{j}$ reduces to comparing $A_{i}^{p}STS$ and $A_{i}^{p}SST$, which is equivalent to comparing $R(A_{i}),R(A_{j})$ as mentioned above. ∎

First, we argue that $N_{1},\ldots,N_{n}$ are distinct. Suppose that $N_{i}=N_{j}~{}(i\neq j)$. Recall that $N_{i}=A_{i}^{m}$ (for $m=\deg_{\mathcal{A}}(A_{i})$) and $N_{j}=A_{j}^{n}$ (for $n=\deg_{\mathcal{A}}(A_{j})$). Applying Lemma 1 (condition 3), $A_{i}=C^{k}$ and $A_{j}=C^{l}$. Further since $A_{i},A_{j}$ are primitive, $A_{i}=C=A_{j}$, which contradicts the assumption that $A_{i}\neq A_{j}$.

We say $N_{i}$ extremal if it is not a prefix of any word in $\{N_{1},\ldots,N_{n}\}\setminus\{N_{i}\}$. Partition $N_{1},\ldots,N_{n}$ into several groups such that (a) for elements in the same group, one of them is the prefix of the other, and (b) the longest element in each group is extremal. (It is obvious that such a partition exists: we can first distribute the extremal ones to different groups, and then distribute the non-extremal ones to suitable group (each non-extremal one is a prefix of some extremal ones).

Now, consider any such group, e.g., $N_{i_{1}},\ldots,N_{i_{x}}$. It suffices to prove that (X) $|N_{i_{1}}|+\ldots+|N_{i_{x}}|=O(|A_{i_{1}}|+\ldots+|A_{i_{x}}|)$, and we prove it in the following. Without loss of generality, assume that $N_{i_{j}}$ is a prefix of $N_{i_{j+1}}$ for $j<x$.

We state two important formulas: (i) $N_{i_{x}}=A_{i_{x}}$. (ii) $|N_{i_{j}}|<|A_{i_{j}}|+|A_{i_{j+1}}|$ for $j<x$. Equation (X) above follows from formulas (i) and (ii) immediately.

∎

It remains to showing that $\mathsf{root}(A_{i})$ can be computed in $O(|A_{i}|)$ time.

Applying Lemma 2, computing $\mathsf{root}(A)$ reduces to finding the largest $j<|A|$ such that the prefix of $A$ with length $j$ equals the suffix of $A$ with length $j$. Moreover, the famous KMP algorithm [10] finds this $j$ in $O(|A|)$ time. ∎

Consider any concatenation $A_{\pi_{1}}\ldots A_{\pi_{n}}$. If $A_{1}$ is not at the leftmost position, we swap it with its left neighbor $A_{x}$. Note that $R(A_{1})\leq R(A_{x})$ by assumption. According to Lemma 3, $A_{1}A_{x}\leq A_{x}A_{1}$. This means that the entire string becomes smaller or remains unchanged after the swapping. Applying several such swappings, $A_{1}$ will be on the leftmost position. Then, we swap $A_{2}$ to the second place. So on and so forth. It follows that $A_{1}\ldots A_{n}\leq A_{\pi_{1}}\ldots A_{\pi_{n}}$.

The other inequality in (7) can be proved symmetrically; proof omitted. ∎

It follows from Lemma 6 and the fact that $R(A_{1}),\ldots,R(A_{n})$ are distinct (see Proposition 1 below).∎

Recall that when $A$ and $B$ are primitive and $R(A)=R(B)$, we can infer that $A=B$ (as proved in the second paragraph of the proof of Lemma 4). Therefore, if $A$ and $B$ are primitive and distinct, $R(A)\neq R(B)$. ∎

Assume that $A\neq B$; otherwise we have $R(A)=R(B)$ and so $A\leq_{\infty}B$.

By the assumption $A\leq B$, we know $A<B$. Consider two cases:

Combining the assumption $A<B$ with the condition of this case, we can see that the relation between $AB,BA$ is the same as that between $A,B$: In comparing $AB$ and $BA$, the result is settled before the $\min\{|A|,|B|\}$-th character.

Assume that $B=AC$ where $C$ is nonempty. Because $B$ is a Lyndon word by assumption, $AC<CA$. Therefore, $AB=AAC<ACA=BA$.

In both cases, we obtain $AB<BA$. It further implies that $R(A)<R(B)$ by Lemma 3. This means $A\leq_{\infty}B$. ∎