Namespaces
Variants
Actions

Difference between revisions of "Lyndon word"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX done)
Line 1: Line 1:
A [[Word|word]] is a sequence of letters <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l1102001.png" />, that is, elements chosen from a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l1102002.png" /> called an [[Alphabet|alphabet]]. A word is usually written as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l1102003.png" />, or abbreviated by a single symbol: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l1102004.png" />. The length of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l1102005.png" /> is equal to the number of letters in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l1102006.png" />, i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l1102007.png" />. One may concatenate two words <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l1102008.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l1102009.png" />, and this operation is concisely written as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020010.png" />. Words may be ordered lexicographically; more precisely, given a total [[Order|order]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020011.png" /> on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020012.png" />, one may extend it over the set of words by setting <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020013.png" /> if either <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020014.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020015.png" /> or there exists an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020016.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020017.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020018.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020019.png" />. This word order is sometimes referred to as alphabetical order. For more details, see [[#References|[a1]]].
+
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, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020020.png" /> is a Lyndon word if it is strictly less than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020021.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020022.png" /> (with respect to the [[Lexicographic order|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|Central series of a group]]). From the definition one can see that letters are Lyndon words. Equivalently, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020023.png" /> is a Lyndon word if it is strictly less than any of the circular shifts <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020024.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020025.png" />). One important characterization of these words yields a recursive process to generate them: a word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020026.png" /> is a Lyndon word if and only if there exists two Lyndon words <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020027.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020028.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020029.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020030.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020031.png" /> over a finite alphabet of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020032.png" /> may be explicitly computed, using Witt's formula:
+
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]].
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020033.png" /></td> </tr></table>
+
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.
 
 
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020034.png" /> is the [[Möbius function|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.
  
The applications of Lyndon words, in algebra and combinatorics, seem innumerable. For instance, there are as many Lyndon words over an alphabet of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020035.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020036.png" /> a prime) as there are irreducible polynomials over a finite field of characteristic <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020037.png" />; 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.  
  
Given any Lyndon word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020038.png" />, one may compute the factorization of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020039.png" /> as a product <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020040.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020041.png" /> is a Lyndon word of maximal length (less than the length of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020042.png" />). The strict suffix (or proper right factor) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020043.png" /> can also be characterized as the smallest strict suffix of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020044.png" />. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020045.png" /> is also a Lyndon word and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020046.png" />. This factorization of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020047.png" /> is called its right standard factorization. Similarly, one may define its left standard factorization. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020048.png" /> be a mapping from the set of Lyndon words into the [[Free associative algebra|free associative algebra]] on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020049.png" /> by setting <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020050.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020051.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020052.png" /> is its right standard factorization. The polynomial thus associated to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020053.png" /> is a [[Lie polynomial|Lie polynomial]], and the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020054.png" /> forms a linear basis of the free Lie algebra over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020055.png" /> (see [[Lie algebra, free|Lie algebra, free]]). Note that the iterated right standard factorizations recursively define a bracketing of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110200/l11020056.png" /> (see [[Binary tree|Binary tree]]), and thus define a [[Hall set|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|Shirshov basis]].
+
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]]].
 
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 word]]; [[Hall set|Hall set]]; [[Lazard set|Lazard set]].
+
See also [[Hall word]]; [[Hall set]]; [[Lazard set]].
  
 
====References====
 
====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)</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>
+
<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)</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}}

Revision as of 22:28, 11 January 2016

A word is a sequence of letters $(a_1,\ldots,a_n)$, that is, elements chosen from a set $A$ called an 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 [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 [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 [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 [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 [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 [a4]. The factorization theorem, when applied to permutations (considered as words without repetitions), yields a variant of the so-called Foata transform [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 [a1], Chap. 5. For applications of Lyndon words related to free Lie algebras, see [a4].

See also Hall word; Hall set; Lazard set.

References

[a1] "Combinatorics on words" M. Lothaire (ed.) , Addison-Wesley (1983)
[a2] 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
[a3] 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
[a4] C. Reutenauer, "Free Lie algebras" , London Math. Soc. Monographs New Ser. , 7 , Oxford Univ. Press (1993)
[a5] J.P. Duval, "Factorizing words over an ordered alphabet" J. Algorithms , 4 (1983) pp. 363–381
[a6] G. Melançon, C. Reutenauer, "Lyndon words, free algebras and shuffles" Canad. J. Math. , XLI : 4 (1989) pp. 577–591
How to Cite This Entry:
Lyndon word. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Lyndon_word&oldid=11373
This article was adapted from an original article by G. Melançon (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article