View source for Lazard set

<!--
l1100901.png
$#A+1 = 35 n = 0
$#C+1 = 35 : ~/encyclopedia/old_files/data/L110/L.1100090 Lazard set
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

A subset  $  T $
of the [[Free magma|free magma]]  $  M ( A ) $, 
i.e. the free non-associative structure over  $  A $ (cf. also [[Associative rings and algebras|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|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 ]  \qquad (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}{l}
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|Hall set]]). Thus, they give bases of the free Lie algebra over  $  A $; 
that is, one may associate a [[Lie polynomial|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|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 [[#References|[a1]]] in order to unify combinatorial constructions of bases of the free Lie algebra. The Lyndon basis (see [[Lyndon word|Lyndon word]]) was thought to be of a different nature from the one considered by M. Hall [[#References|[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|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|Hall word]].

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