A property of Lyndon words.

Question

A word is a Lyndon word if it is strictly smaller than any of its proper right factors. Let $A$ be an alphabet and $L$ be the set of all Lyndon words over $A$. For a word $w \in L-A$, the pair $(l, m)$, $l, m \in L$, such that $w=lm$ and $m$ is of maximal length is called the standard factorization of $w$ and it is denoted by $\sigma(w) = (l,m)$.

In the book Combinatorics on words, on page 67, there is a proposition left as an excise:

Let $w \in L - A$, and $\sigma(w) = (l, m)$ be its standard factorization. Then for any $n \in L$ such that $w < n$, the pair $(w,n)$ is the standard factorization of $wn \in L$ if and only if $n \le m$.

The necessary condition is proved as follows. Suppose that $n>m$. Then $mn \in L$. The length of $mn$ is larger than the length of $n$. Therefore $(w,n)$ is not the standard factorization of $wn$.

How to prove the sufficient condition? Thank you very much.

Answer 1

This is Lemma 1.6 in K. T. Chen, R. H. Fox & R. C. Lyndon. Free Differential Calculus, IV. The Quotient Groups of the Lower Central Series (1958). Annals of Mathematics 68(1), 86. Below I rewrite their proof with notation and terminology following the conventions of the book you mention. (Citations for posterity: D. Perrin, Factorizations of Free Monoids (chapter 5 in Combinatorics on words (1983). Cambridge Univ. Press, edited by M. Lothaire)). (The terminology in the Chen–Fox–Lyndon paper is certainly nicer and simpler though, in my opinion at least.)

Suppose that $e$ is a proper right factor of $wn$ that is longer than $n$. We will show that $e\notin L$. Either (1) $e=fn$ where $f$ is a proper right factor of $m$, or (2) $e=mn$, or (3) $e=gmn$ where $g$ is a proper right factor of $l$. (You should now try proving it before looking at the solution.)

(1) If $e=fn$, we have $m<f$ as $m\in L$. Thus $n\le m<f<fn$ and so $e\notin L$.

(2) If $e=mn$, we have $n\le m<mn$, so $e\notin L$.

(3) If $e=gmn$, we suppose for contradiction that $e\in L$, and that $g$ is the shortest proper right factor of $l$ for which $gmn\in L$. From cases (1) and (2) we see that $n$ must be the maximal proper right factor of $gmn$ that is Lyndon. As such, by Proposition 5.1.3, we see that $gm\in L$. But this contradicts the assumption that $m$ is the maximal proper right factor in $lm$ satisfying $m\in L$.

It follows that $n$ is the maximal proper right factor of $wn$; that is, $\sigma(wn)=(w,n)$.