View source for Lyndon word

A [[word]] is a sequence of letters $(a_1,\ldots,a_n)$, that is, elements chosen from a set $A$ called an [[Alphabet|alphabet]]. A word is usually written as $a_1\ldots a_n$, or abbreviated by a single symbol: $u = a_1\ldots a_n$. The length of $u$ is equal to the number of letters in $u$, i.e. $|u| = n$. One may concatenate two words $u = a_1\ldots a_n$, $v = b_1\ldots b_m$, and this operation is concisely written as $uv = a_1\ldots a_n b_1\ldots b_m$ . Words may be ordered lexicographically (cf. [[Lexicographic order]]); more precisely, given a [[total order]] $<$ on $A$, one may extend it over the set of words by setting $a_1\ldots a_n < b_1\ldots b_m$ if either $n < m$ and $a_1 = b_1, \ldots, a_m = b_m$ or there exists an $i$ such that $1 \le i \le \min(m,n)$ with $a_1 = b_1, \ldots, a_{i-1} = b_{i-1}$ and $a_i < b_i$. This word order is sometimes referred to as alphabetical order. For more details, see [[#References|[a1]]].

Lyndon words are words strictly less than any of their non-empty proper right factors (or strict suffixes), that is, $a_1\ldots a_n$ is a Lyndon word if it is strictly less than $a_i\ldots a_n$ for $2 \le i \le n$ with respect to the lexicographic order. These were introduced by R.C. Lyndon [[#References|[a2]]] for constructing bases of the lower central series for free groups (cf. [[Central series of a group]]). From the definition one can see that single letters are Lyndon words. Equivalently, $a_1\ldots a_n$ is a Lyndon word if it is strictly less than any of the circular shifts $a_i\ldots a_n a_1\ldots a_{i-1}$ ($2 \le i \le n$). One important characterization of these words yields a recursive process to generate them: a word $w$ is a Lyndon word if and only if there exists two Lyndon words $u$,$v$ such that $u < v$  and $w = uv$. J.P. Duval [[#References|[a3]]] gave a beautiful, and clever, algorithm that generates Lyndon words of bounded length over a finite alphabet. The number of Lyndon words of length $n$ over a finite alphabet of cardinality $p$ may be explicitly computed, using Witt's formula:
$$
\frac{1}{n} \sum_{d | n} \mu(d) p^{n/d}
$$
where $\mu(n)$ is the [[Möbius function]].

A multi-homogeneous version of Witt's formula may be found in [[#References|[a4]]]. The central result about Lyndon words is the following Chen–Fox–Lyndon theorem: Any word can be expressed as a unique non-increasing product of Lyndon words. The preceding characterization suggests an algorithm to compute this factorization. Duval [[#References|[a5]]] gave a simple and efficient algorithm that factorizes a word in linear time.

The applications of Lyndon words, in algebra and combinatorics, seem innumerable. For instance, there are as many Lyndon words over an alphabet of cardinality $p$ ($p$ a prime) as there are irreducible polynomials over a finite field of characteristic $p$; see [[#References|[a4]]]. The factorization theorem, when applied to permutations (considered as words without repetitions), yields a variant of the so-called Foata transform [[#References|[a1]]], Chap. 10.

Given any Lyndon word $w$, one may compute the factorization of $w$ as a product $uv$, where $v$ is a Lyndon word of maximal length (less than the length of $w$). The strict suffix (or proper right factor) $v$ can also be characterized as the smallest strict suffix of $w$. Then $u$ is also a Lyndon word and $u < uv < v$. This factorization of $w$ is called its right standard factorization. Similarly, one may define its left standard factorization. 

Let $\lambda$ be a mapping from the set of Lyndon words into the [[free associative algebra]] on $A$ by setting $\lambda(a) = a$, and $\lambda(w) = \lambda(u)\lambda(v) - \lambda(v)\lambda(u)$, where $w = uv$ is its right standard factorization. The polynomial thus associated to $w$ is a [[Lie polynomial]], and the set $\{ \lambda(w) : w \,\text{a Lyndon word of}\,A \}$ forms a linear basis of the [[free Lie algebra]] over $A$. Note that the iterated right standard factorizations recursively define a bracketing of $w$ (see [[Binary tree]]), and thus define a [[Hall set]]. The corresponding basis is called the Chen–Fox–Lyndon basis, or simply the Lyndon basis. It is practically identical with the [[Shirshov basis]].

A good introduction to Lyndon words is [[#References|[a1]]], Chap. 5. For applications of Lyndon words related to free Lie algebras, see [[#References|[a4]]].

See also [[Hall word]]; [[Hall set]]; [[Lazard set]].

====References====
<table>
<TR><TD valign="top">[a1]</TD> <TD valign="top">  "Combinatorics on words"  M. Lothaire (ed.) , Addison-Wesley  (1983)</TD></TR>
<TR><TD valign="top">[a2]</TD> <TD valign="top">  K.T. Chen,   R.H. Fox,   R.C. Lyndon,   "Free differential calculus, IV. The quotient groups of the lower central series"  ''Ann. of Math.'' , '''68'''  (1958)  pp. 81–95</TD></TR>
<TR><TD valign="top">[a3]</TD> <TD valign="top">  J.P. Duval,   "Génération d'une section des classes de conjugaison et arbre de mots de Lyndon de longueur bornée"  ''Theor. Comput. Sci.'' , '''60'''  (1988)  pp. 255–283</TD></TR>
<TR><TD valign="top">[a4]</TD> <TD valign="top">  C. Reutenauer,   "Free Lie algebras" , ''London Math. Soc. Monographs New Ser.'' , '''7''' , Oxford Univ. Press  (1993) {{ZBL|0798.17001}}</TD></TR>
<TR><TD valign="top">[a5]</TD> <TD valign="top">  J.P. Duval,   "Factorizing words over an ordered alphabet"  ''J. Algorithms'' , '''4'''  (1983)  pp. 363–381</TD></TR>
<TR><TD valign="top">[a6]</TD> <TD valign="top">  G. Melançon,   C. Reutenauer,   "Lyndon words, free algebras and shuffles"  ''Canad. J. Math.'' , '''XLI''' :  4  (1989)  pp. 577–591</TD></TR>
</table>

{{TEX|done}}