Lyndon words

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia

Last update: 15 March 2013

Lyndon words

The lexicographic order on words is given by f1<< fr and u<vif v=uv2 or if u=u1fi u2 and v=u1 fjv2 with fi<fj . A word is Lyndon if it is smaller than all its proper right factors.

Any word u has a unique factorisation u=l1 l2lk with l1l2 lk 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 f1f1 f1f1 f2, (f1f1 f1f2) f1, (f1f1 f2) f1 f1, (f1f2) f1 f1 f1, and f2 f1 f1 f1 f1.

A word is good if there is a homogeneous element aUq 𝔫- 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]

  1. A word g is good if and only if g=l1 lk with l1l2 lk good Lyndon words.
  2. Let R+ be the set of positive roots and let + be the set of good Lyndon words. Then the map R+ + β l(β) is a bijection, where l(β) =max{ l(β1) l(β2) | β1, β2 R+, β= β1+β2, l(β1) <l(β2)}


Notes and References

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

page history