# Lazard set

Jump to: navigation, search

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.

How to Cite This Entry:
Lazard set. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Lazard_set&oldid=47597
This article was adapted from an original article by G. MelanÃ§on (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article