Lazard set

A subset $T$ of the free magma $M ( A )$, i.e. the free non-associative structure over $A$( cf. also Associative rings and algebras). The elements of $M ( A )$ correspond to completely bracketed words over $A$( or rooted planar binary trees with leaves labelled by generators $a _ {1} , a _ {2} , \dots$; cf. also Binary tree). These are defined recursively as brackets $t = [ t ^ \prime , t ^ {\prime \prime } ]$ where $t ^ \prime , t ^ {\prime \prime }$ are bracketed words of lower weight; bracketed words of weight one correspond to the generators $a _ {1} , a _ {2} , \dots$. A subset $E \subset M ( A )$ is said to be closed, if for each element $t = [ t ^ \prime , t ^ {\prime \prime } ] \in E$ one has $t ^ \prime , t ^ {\prime \prime } \in E$. Given two elements $s, t \in M ( A )$, one writes $[ st ^ {p} ]$ to denote the element

$$[ \dots [ [ s, t ] , t ] \dots t ] ( p \textrm{ closing brackets } ) .$$

Consider trees $t _ {0} \dots t _ {n}$ and subsets $T _ {0} \dots T _ {n + 1 } \subset M ( A )$ defined as follows:

$$\tag{a1 } \left . \begin{array}{cttt} t _ {0} \in T _ {0} = A, &t _ {1} \in T _ {1} = \left \{ {[ tt _ {0} ^ {p} ] } : {p \geq 0, t \in T _ {0} \setminus t _ {0} } \right \} , &\dots \dots &t _ {n} \in T _ {n} = \left \{ {[ tt _ {n - 1 } ^ {p} ] } : {p \geq 0, t \in T _ {n - 1 } \setminus t _ {n - 1 } } \right \} , \\ t _ {1} \in T _ {1} = \left \{ {[ tt _ {0} ^ {p} ] } : {p \geq 0, t \in T _ {0} \setminus t _ {0} } \right \} , &\dots \dots &t _ {n} \in T _ {n} = \left \{ {[ tt _ {n - 1 } ^ {p} ] } : {p \geq 0, t \in T _ {n - 1 } \setminus t _ {n - 1 } } \right \} , \\ \end{array} \right \}$$

A Lazard set is a subset $L \subset M ( A )$ such that for any finite, non-empty and closed subset $E \subset M ( A )$ one has:

$$L \cap E = \{ t _ {0} > \dots > t _ {n} \}$$

for some $n \geq 0$, (a1) holds and, moreover, $T _ {n + 1 } \cap E = \emptyset$.

Lazard sets may be shown to coincide with Hall sets (cf. Hall set). Thus, they give bases of the free Lie algebra over $A$; that is, one may associate a Lie polynomial $\psi ( t )$ to each element $t \in L$ of a Lazard set such that the free Lie algebra ${\mathcal L} ( A )$( over $A$; cf. Lie algebra, free) is freely generated (as a module over a commutative ring $K$) by the Lie polynomials $\{ {\psi ( t ) } : {t \in L } \}$. Lazard's elimination process may then be phrased as follows: One has the direct sum decomposition (as a module over a commutative ring $K$):

$${\mathcal L} ( A ) = K \psi ( t _ {0} ) \oplus \dots \oplus K \psi ( t _ {n} ) \oplus {\mathcal L} _ {n + 1 } ,$$

where ${\mathcal L} _ {n + 1 }$ is the Lie subalgebra freely generated by $T _ {n + 1 }$.

Lazard sets were introduced by X. Viennot [a1] in order to unify combinatorial constructions of bases of the free Lie algebra. The Lyndon basis (see Lyndon word) was thought to be of a different nature from the one considered by M. Hall [a2], and generalizations of it were proposed by many authors. Viennot gave a unifying framework for all these constructions. One may present Lazard sets in terms of words, rather than trees in $M ( A )$. It can then be shown that a unique tree structure is attached to every word of a Lazard set. Moreover, a Lazard set of words is totally ordered, as is a Lazard set of trees, and it is a complete factorization of the free monoid. That is, every word is a unique non-increasing product of Lazard words. This result makes explicit the link between bases of free Lie algebras and complete factorizations of free monoids.

See also Hall word.

References

[a1]	X. Viennot, "Algèbres de Lie libres et monoïdes libres" , Lecture Notes in Mathematics , 691 , Springer (1978)
[a2]	M. Hall, "A basis for free Lie rings and higher commutators in free groups" Proc. Amer. Math. Soc. , 1 (1950) pp. 57–581
[a3]	C. Reutenauer, "Free Lie algebras" , London Math. Soc. Monographs New Ser. , 7 , Oxford Univ. Press (1993)