Namespaces
Variants
Actions

Difference between revisions of "Hall set"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
A Hall set over generators <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h1100401.png" /> is a totally ordered subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h1100402.png" /> of the [[Free magma|free magma]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h1100403.png" />, i.e. the free non-associative structure over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h1100404.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/h/h110/h110040/h1100405.png" /> correspond to completely bracketed words over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h1100406.png" /> (or rooted planar binary trees with leaves labelled by generators <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h1100407.png" />; cf. also [[Binary tree|Binary tree]]). These are defined recursively as brackets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h1100408.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h1100409.png" /> are bracketed words of lower weight; the bracketed words of weight one correspond to the generators <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004010.png" />.
+
{{TEX|done}}
 +
A Hall set over generators $A=\{a_1,a_2,\dots\}$ is a [[totally ordered set|totally ordered]] subset $H$ of the [[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',t'']$, where $t',t''$ are bracketed words of lower weight; the bracketed words of weight one correspond to the generators $a_1,a_2,\dots$.
  
The total order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004011.png" /> on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004012.png" /> is required to satisfy the condition:
+
The total order $<$ on $H$ is required to satisfy the condition:
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004013.png" />) for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004014.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004015.png" />.
+
$H_0$) for any $t=[t',t'']\in H$, $t<t''$.
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004016.png" /> be a totally ordered subset such that condition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004017.png" />) is fulfilled. Then the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004018.png" /> is a Hall set if and only if the following conditions are satisfied:
+
Let $H\subset M(A)$ be a totally ordered subset such that condition $H_0$) is fulfilled. Then the set $H$ is a Hall set if and only if the following conditions are satisfied:
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004019.png" />) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004020.png" />;
+
$H_1$) $A\subset H$;
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004021.png" />) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004022.png" /> if and only if
+
$H_2$) $t=[t',t'']\in H$ if and only if
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004023.png" />) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004024.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004025.png" />; and
+
$H_{2.1}$) $t',t''\in H$ with $t'<t''$; and
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004026.png" />) either <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004027.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004028.png" />, and then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004029.png" />.
+
$H_{2.2}$) either $t'\in A$ or $t'=[s',s'']$, and then $s''\geq t''$.
  
This definition is from [[#References|[a1]]]. M. Hall's original definition replaces condition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004030.png" />) by simply imposing that brackets of lower weight be smaller with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004031.png" />. Many authors proposed generalizations of Hall's construction by relaxing condition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004032.png" />) in many different ways. Viennot's definition acted as a unifying framework for the various proposed generalizations; see [[#References|[a2]]] for details. Observe that the definition of a Hall set admits symmetries, with respect to the order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004033.png" />; for instance, one could invert the order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004034.png" /> and write <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004035.png" /> instead. It must be noted, however, that conditions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004036.png" />) and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004037.png" />) must be coherent; that is, the sequence of elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004038.png" /> must either be increasing (as is the case here) or decreasing. Hence, there are four possible equivalent definitions for Hall sets.
+
This definition is from [[#References|[a1]]]. M. Hall's original definition replaces condition $H_0$) by simply imposing that brackets of lower weight be smaller with respect to $<$. Many authors proposed generalizations of Hall's construction by relaxing condition $H_0$) in many different ways. Viennot's definition acted as a unifying framework for the various proposed generalizations; see [[#References|[a2]]] for details. Observe that the definition of a Hall set admits symmetries, with respect to the order $<$; for instance, one could invert the order $<$ and write $>$ instead. It must be noted, however, that conditions $H_1$) and $H_2$) must be coherent; that is, the sequence of elements $t'',s'',t'$ must either be increasing (as is the case here) or decreasing. Hence, there are four possible equivalent definitions for Hall sets.
  
An example of a Hall set is the set of basic commutators (cf. [[Basic commutator|Basic commutator]]), the basic commutator Hall set. It has the total order reversed with respect to the definition above. Another symmetry involves writing bracketed words from right to left instead of from left to right. For example, the  "Hall set"  described in [[#References|[a4]]], Sect. 2.10, arises from the basic commutator Hall set in this way. Another Hall set can be defined using Lyndon words (cf. [[Lyndon word|Lyndon word]]).
+
An example of a Hall set is the set of basic commutators (cf. [[Basic commutator]]), the basic commutator Hall set. It has the total order reversed with respect to the definition above. Another symmetry involves writing bracketed words from right to left instead of from left to right. For example, the  "Hall set"  described in [[#References|[a4]]], Sect. 2.10, arises from the basic commutator Hall set in this way. Another Hall set can be defined using Lyndon words (cf. [[Lyndon word|Lyndon word]]).
  
Elements of a Hall set are used to obtain a basis of the free Lie algebra over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004039.png" /> (cf. [[Lie algebra, free|Lie algebra, free]]; [[Hall polynomial|Hall polynomial]]). X. Viennot [[#References|[a1]]] has shown that his definition not only gives a unifying framework but is also, in a certain sense, optimal: Any subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004040.png" /> satisfying <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004041.png" />) and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004042.png" />), leading to a basis of the free Lie algebra, must satisfy condition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110040/h11004043.png" />).
+
Elements of a Hall set are used to obtain a basis of the free Lie algebra over $A$ (cf. [[Lie algebra, free|Lie algebra, free]]; [[Hall polynomial|Hall polynomial]]). X. Viennot [[#References|[a1]]] has shown that his definition not only gives a unifying framework but is also, in a certain sense, optimal: Any subset $H\subset M(A)$ satisfying $H_1$) and $H_2$), leading to a basis of the free Lie algebra, must satisfy condition $H_0$).
  
Hall sets may be shown to coincide with Lazard sets (cf. [[Lazard set|Lazard set]]). The combinatorics of Hall sets is also studied in [[#References|[a2]]] and [[#References|[a3]]].
+
Hall sets may be shown to coincide with Lazard sets (cf. [[Lazard set]]). The combinatorics of Hall sets is also studied in [[#References|[a2]]] and [[#References|[a3]]].
  
 
See also [[Hall word|Hall word]].
 
See also [[Hall word|Hall word]].
  
 
====References====
 
====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">  G. Melançon,  "Combinatorics of Hall trees and Hall words"  ''J. Combin. Th.'' , '''59A''' :  2  (1992)  pp. 285–308</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><TR><TD valign="top">[a4]</TD> <TD valign="top">  N. Bourbaki,  "Groupes et algèbres de Lie" , '''II. Algèbres de Lie libres''' , Hermann  (1972)</TD></TR></table>
+
<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) {{ZBL|0395.17003}}</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  G. Melançon,  "Combinatorics of Hall trees and Hall words"  ''J. Combin. Th.'' , '''59A''' :  2  (1992)  pp. 285–308</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><TR><TD valign="top">[a4]</TD> <TD valign="top">  N. Bourbaki,  "Groupes et algèbres de Lie" , '''II. Algèbres de Lie libres''' , Hermann  (1972)</TD></TR></table>

Latest revision as of 18:40, 5 October 2023

A Hall set over generators $A=\{a_1,a_2,\dots\}$ is a totally ordered subset $H$ 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',t'']$, where $t',t''$ are bracketed words of lower weight; the bracketed words of weight one correspond to the generators $a_1,a_2,\dots$.

The total order $<$ on $H$ is required to satisfy the condition:

$H_0$) for any $t=[t',t'']\in H$, $t<t''$.

Let $H\subset M(A)$ be a totally ordered subset such that condition $H_0$) is fulfilled. Then the set $H$ is a Hall set if and only if the following conditions are satisfied:

$H_1$) $A\subset H$;

$H_2$) $t=[t',t'']\in H$ if and only if

$H_{2.1}$) $t',t''\in H$ with $t'<t''$; and

$H_{2.2}$) either $t'\in A$ or $t'=[s',s'']$, and then $s''\geq t''$.

This definition is from [a1]. M. Hall's original definition replaces condition $H_0$) by simply imposing that brackets of lower weight be smaller with respect to $<$. Many authors proposed generalizations of Hall's construction by relaxing condition $H_0$) in many different ways. Viennot's definition acted as a unifying framework for the various proposed generalizations; see [a2] for details. Observe that the definition of a Hall set admits symmetries, with respect to the order $<$; for instance, one could invert the order $<$ and write $>$ instead. It must be noted, however, that conditions $H_1$) and $H_2$) must be coherent; that is, the sequence of elements $t'',s'',t'$ must either be increasing (as is the case here) or decreasing. Hence, there are four possible equivalent definitions for Hall sets.

An example of a Hall set is the set of basic commutators (cf. Basic commutator), the basic commutator Hall set. It has the total order reversed with respect to the definition above. Another symmetry involves writing bracketed words from right to left instead of from left to right. For example, the "Hall set" described in [a4], Sect. 2.10, arises from the basic commutator Hall set in this way. Another Hall set can be defined using Lyndon words (cf. Lyndon word).

Elements of a Hall set are used to obtain a basis of the free Lie algebra over $A$ (cf. Lie algebra, free; Hall polynomial). X. Viennot [a1] has shown that his definition not only gives a unifying framework but is also, in a certain sense, optimal: Any subset $H\subset M(A)$ satisfying $H_1$) and $H_2$), leading to a basis of the free Lie algebra, must satisfy condition $H_0$).

Hall sets may be shown to coincide with Lazard sets (cf. Lazard set). The combinatorics of Hall sets is also studied in [a2] and [a3].

See also Hall word.

References

[a1] X. Viennot, "Algèbres de Lie libres et monoïdes libres" , Lecture Notes in Mathematics , 691 , Springer (1978) Zbl 0395.17003
[a2] G. Melançon, "Combinatorics of Hall trees and Hall words" J. Combin. Th. , 59A : 2 (1992) pp. 285–308
[a3] C. Reutenauer, "Free Lie algebras" , London Math. Soc. Monographs New Ser. , 7 , Oxford Univ. Press (1993)
[a4] N. Bourbaki, "Groupes et algèbres de Lie" , II. Algèbres de Lie libres , Hermann (1972)
How to Cite This Entry:
Hall set. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Hall_set&oldid=11448
This article was adapted from an original article by G. Melançon (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article