In mathematics, in the areas of group theory and combinatorics, Hall words provide a unique monoid factorisation of the free monoid. They are also totally ordered, and thus provide a total order on the monoid. This is analogous to the better-known case of Lyndon words; in fact, the Lyndon words are a special case, and almost all properties possessed by Lyndon words carry over to Hall words. Hall words are in one-to-one correspondence with Hall trees. These are binary trees; taken together, they form the Hall set. This set is a particular totally ordered subset of a free non-associative algebra, that is, a free magma. 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. As such, this generalizes the same process when done with the Lyndon words. 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. It can be shown that Lazard sets coincide with Hall sets. 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. Hall sets were introduced by Marshall Hall based on work of Philip Hall on groups. 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.
Notational preliminaries The setting for this article is the free magma in n {\displaystyle n} generators. This is simply a set containing n {\displaystyle n} elements, along with a binary operator ∙ {\displaystyle \bullet } that allows any two elements to be juxtaposed, next to each other. The juxtaposition is taken to be non-associative and non-commutative, so that parenthesis must necessarily be used, when juxtaposing three or more elements. Thus, for example, ( a ∙ b ) ∙ c {\displaystyle (a\bullet b)\bullet c} is not the same as a ∙ ( b ∙ c ) {\displaystyle a\bullet (b\bullet c)} . In this way, the magma operator ∙ {\displaystyle \bullet } provides a convenient stand-in for any other desired binary operator that might have additional properties, such as group or algebra commutators. Thus, for example, the magma juxtaposition can be mapped to the commutator of a non-commutative algebra:
a ∙ b ↦ [ a , b ] = a b − b a {\displaystyle a\bullet b\mapsto [a,b]=ab-ba}
or to a group commutator:
a ∙ b ↦ a b a − 1 b − 1 {\displaystyle a\bullet b\mapsto aba^{-1}b^{-1}}
The above two maps are just magma homomorphisms, in the conventional sense of a homomorphism; the objects on the right just happen to have more structure than a magma does. To avoid the awkward typographical mess that is ∙ {\displaystyle \bullet } , it is conventional to just write a b {\displaystyle ab} for ( a ∙ b ) {\displaystyle (a\bullet b)} . The use of parenthesis is mandatory, however, since ( a b ) c ≠ a ( b c ) {\displaystyle (ab)c\neq a(bc)} as already noted. If a {\displaystyle a} is a compound object, one might sometimes write ( a ) {\displaystyle (a)} as needed, to disambiguate usage. Of course, one can also write [ a , b ] {\displaystyle [a,b]} in place of a b {\displaystyle ab} , but this can lead to a proliferation of square brackets and commas. Keeping this in mind, one can otherwise be fluid in the notation.
Hall set The Hall set is a totally ordered subset of a free non-associative algebra, that is, a free magma. Let A = { a 1 , … , a n } {\displaystyle A=\{a_{1},\ldots ,a_{n}\}} be a set of generators, and let M ( A ) {\displaystyle M(A)} be the free magma over A {\displaystyle A} . The free magma is simply the set of non-associative strings in the letters of A {\displaystyle A} , with parenthesis retained to show grouping. 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 A {\displaystyle A} . The Hall set H ⊆ M ( A ) {\displaystyle H\subseteq M(A)} can be constructed recursively (in increasing order) as follows:
The elements of A {\displaystyle A} are given an arbitrary total order. The Hall set contains the generators: A ⊆ H . {\displaystyle A\subseteq H.}
… excerpt ends here. Continue reading the full article.
