Lyndon words

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au

Last update: 15 March 2013

Lyndon words

The lexicographic order on words is given by $f_{1} < \dots < f_{r}$ and $u < v if v = u v_{2} or if u = u_{1} f_{i} u_{2} and v = u_{1} f_{j} v_{2} with f_{i} < f_{j} .$ A word is Lyndon if it is smaller than all its proper right factors.

Any word $u$ has a unique factorisation $u = l_{1} l_{2} \dots l_{k} with l_{1} \geq l_{2} \geq \dots \geq l_{k} Lyndon.$ (see [Lo, Thm 5.1.5] or [Re, Thm 4.9]).

If $γ = 4 α_{1}^{\lor} + α_{2}^{\lor}$ , the words in the set $Γ^{γ}$ (displayed in their nonincreasing Lyndon factorisation) are $f_{1} f_{1} f_{1} f_{1} f_{2}, (f_{1} f_{1} f_{1} f_{2}) \cdot f_{1}, (f_{1} f_{1} f_{2}) \cdot f_{1} \cdot f_{1}, (f_{1} f_{2}) \cdot f_{1} \cdot f_{1} \cdot f_{1}, and f_{2} \cdot f_{1} \cdot f_{1} \cdot f_{1} \cdot f_{1} .$

A word is good if there is a homogeneous element $a \in U_{q} 𝔫^{-}$ such that $g$ is the maximal word appearing in $a$ . The following proposition gives a characterisation of good words and good Lyndon words.

[Le, Prop 17, Prop 25] and [LR, Cor 2.5]

A word $g$ is good if and only if $g = l_{1} \dots l_{k} with l_{1} \geq l_{2} \geq \dots \geq l_{k} good Lyndon words.$
Let $R^{+}$ be the set of positive roots and let $ℛ^{+}$ be the set of good Lyndon words. Then the map $\begin{array}{rcl} R^{+} & \to & ℛ^{+} \\ β & \mapsto & l (β) \end{array} is a bijection,$ where $l (β) = \max {l (β_{1}) l (β_{2}) | β_{1}, β_{2} \in R^{+}, β = β_{1} + β_{2}, l (β_{1}) < l (β_{2})}$

References

Notes and References

This page is partially based on joint work with P. Lalonde and A. Kleshchev.

page history