In this form, the Hall trees provide a basis for free Lie algebras, and can be used to perform the commutations required by the Poincaré–Birkhoff–Witt theorem used in the construction of a universal enveloping algebra.
Hall trees can also be used to give a total order to the elements of a group, via the commutator collecting process, which is a special case of the general construction given below.
The historical development runs in reverse order from the above description.
The commutator collecting process was described first, in 1934, by Philip Hall and explored in 1937 by Wilhelm Magnus.
[3] Subsequently, Wilhelm Magnus showed that they arise as the graded Lie algebra associated with the filtration on a free group given by the lower central series.
This correspondence was motivated by commutator identities in group theory due to Philip Hall and Ernst Witt.
The juxtaposition is taken to be non-associative and non-commutative, so that parenthesis must necessarily be used, when juxtaposing three or more elements.
provides a convenient stand-in for any other desired binary operator that might have additional properties, such as group or algebra commutators.
The free magma is simply the set of non-associative strings in the letters of
Parenthesis may be written with square brackets, so that elements of the free magma may be viewed as formal commutators.
Equivalently, the free magma is the set of all binary trees with leaves marked by elements of
can be constructed recursively (in increasing order) as follows: The construction and notation used below are nearly identical to that used in the commutator collecting process, and so can be directly compared; the weights are the string-lengths.
The initial members of the Hall set are then (in order) Notice that there are
It turns out that this "forgetting" is harmless, as the corresponding Hall tree can be deduced from the word, and it is unique.
can be uniquely factorized into a ascending sequence of Hall words.
This is analogous to, and generalizes the better-known case of factorization with Lyndon words provided by the Chen–Fox–Lyndon theorem.
The lemmas and theorems required to provide the word-to-tree correspondence, and the unique ordering, are sketched below.
The foliage is just the string consisting of the leaves of the tree, that is, taking the tree written with commutator brackets, and erasing the commutator brackets.
[5] This implies that, given a Hall word, the corresponding tree can be uniquely identified.
Note that increasing sequences of Hall words are standard.
can be achieved by defining and recursively applying a simple term rewriting system.
The uniqueness of the factorization follows from the confluence properties of the system.
[5] The rewriting is performed by the exchange of certain pairs of consecutive Hall words in a sequence; it is given after these definitions.
In general, it is most convenient to apply the rewrite to the right-most legal drop; however, it can be shown that the rewrite is confluent, and so one obtains the same results no matter what the order.
This is similar to the standard lexicographic order, but at the level of Hall words.
Another very important application of the rewrite rule is to perform the commutations that appear in the Poincaré–Birkhoff–Witt theorem.
A detailed discussion of the commutation is provided in the article on universal enveloping algebras.
Note that term rewriting with Lyndon words can also be used to obtain the needed commutation for the PBW theorem.
[3] Subsequently, Wilhelm Magnus showed that they arise as the graded Lie algebra associated with the filtration on a free group given by the lower central series.
This correspondence was motivated by commutator identities in group theory due to Philip Hall and Ernst Witt.