Namespaces
Variants
Actions

Difference between revisions of "Lazard set"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
Line 1: Line 1:
A subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l1100901.png" /> of the [[Free magma|free magma]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l1100902.png" />, i.e. the free non-associative structure over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l1100903.png" /> (cf. also [[Associative rings and algebras|Associative rings and algebras]]). The elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l1100904.png" /> correspond to completely bracketed words over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l1100905.png" /> (or rooted planar binary trees with leaves labelled by generators <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l1100906.png" />; cf. also [[Binary tree|Binary tree]]). These are defined recursively as brackets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l1100907.png" /> where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l1100908.png" /> are bracketed words of lower weight; bracketed words of weight one correspond to the generators <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l1100909.png" />. A subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l11009010.png" /> is said to be closed, if for each element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l11009011.png" /> one has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l11009012.png" />. Given two elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l11009013.png" />, one writes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l11009014.png" /> to denote the element
+
<!--
 +
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.
 +
-->
  
<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/l110090/l11009015.png" /></td> </tr></table>
+
{{TEX|auto}}
 +
{{TEX|done}}
  
Consider trees <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l11009016.png" /> and subsets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l11009017.png" /> defined as follows:
+
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
  
<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/l110090/l11009018.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>
+
$$
 +
[ \dots [ [ s, t ] , t ] \dots t ]  ( p  \textrm{ closing  brackets  } ) .
 +
$$
  
A Lazard set is a subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l11009019.png" /> such that for any finite, non-empty and closed subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l11009020.png" /> one has:
+
Consider trees  $  t _ {0} \dots t _ {n} $
 +
and subsets  $  T _ {0} \dots T _ {n + 1 }  \subset M ( A ) $
 +
defined as follows:
  
<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/l110090/l11009021.png" /></td> </tr></table>
+
$$ \tag{a1 }
 +
\left .
  
for some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l11009022.png" />, (a1) holds and, moreover, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l11009023.png" />.
+
\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 \}
 +
$$
  
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l11009024.png" />; that is, one may associate a [[Lie polynomial|Lie polynomial]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l11009025.png" /> to each element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l11009026.png" /> of a Lazard set such that the free Lie algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l11009027.png" /> (over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l11009028.png" />; cf. [[Lie algebra, free|Lie algebra, free]]) is freely generated (as a module over a commutative ring <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l11009029.png" />) by the Lie polynomials <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l11009030.png" />. Lazard's elimination process may then be phrased as follows: One has the direct sum decomposition (as a module over a commutative ring <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l11009031.png" />):
+
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:
  
<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/l110090/l11009032.png" /></td> </tr></table>
+
$$
 +
L \cap E = \{ t _ {0} > \dots > t _ {n} \}
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l11009033.png" /> is the Lie subalgebra freely generated by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l11009034.png" />.
+
for some  $  n \geq  0 $,
 +
(a1) holds and, moreover,  $  T _ {n + 1 }  \cap E = \emptyset $.
  
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110090/l11009035.png" />. 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.
+
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]].
 
See also [[Hall word|Hall word]].

Revision as of 22:16, 5 June 2020


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)
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