Lyndon words

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

and

Department of Mathematics
University of Wisconsin, Madison
Madison, WI 53706 USA
ram@math.wisc.edu

Last updates: 2 March 2010

Lyndon words

The lexicographic order on words is given by

f_{1} < \dots < f_{r}

and

u < v if v = u v_{2} or 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_{1} \dots l_{k}, with l_{1} \geq l_{1} \geq \dots \geq l_{k} Lyndon.

(see [Lo, Thm 5.1.5] or [Re, Thm 4.9]).

If $α = 4 α_{1} + α_{2}$ , 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}) . f_{1}, (f_{1} f_{1} f_{2}) . f_{1} . f_{1}, (f_{1} f_{2}) . f_{1} . f_{1}, . f_{1}, and f_{2} . f_{1} . f_{1} . f_{1} . 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 iff $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

[BG] A. Braverman and D. Gaitsgory, Crystals via the affine Grassmanian, Duke Math. J. 107 no. 3, (2001), 561-575; arXiv:math/9909077v2, MR1828302 (2002e:20083)

page history