Hall set

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