In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, in the areas of
group theory
In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups.
The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ...
and
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...
, Hall words provide a unique
monoid factorisation In mathematics, a factorisation of a free monoid is a sequence of subsets of words with the property that every word in the free monoid can be written as a concatenation of elements drawn from the subsets. The Chen– Fox–Lyndon theorem states th ...
of the
free monoid In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero ele ...
. They are also
totally ordered
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexive ...
, and thus provide a total order on the monoid. This is analogous to the better-known case of
Lyndon word
In mathematics, in the areas of combinatorics and computer science, a Lyndon word is a nonempty string that is strictly smaller in lexicographic order than all of its rotations. Lyndon words are named after mathematician Roger Lyndon, who in ...
s; 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
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexive ...
subset of a free non-associative algebra, that is, a
free magma. In this form, the Hall trees provide a basis for
free Lie algebra In mathematics, a free Lie algebra over a field ''K'' is a Lie algebra generated by a set ''X'', without any imposed relations other than the defining relations of alternating ''K''-bilinearity and the Jacobi identity.
Definition
The definition ...
s, and can be used to perform the commutations required by the
Poincaré–Birkhoff–Witt theorem
In mathematics, more specifically in the theory of Lie algebras, the Poincaré–Birkhoff–Witt theorem (or PBW theorem) is a result giving an explicit description of the universal enveloping algebra of a Lie algebra. It is named after Henri Poi ...
used in the construction of a
universal enveloping algebra
In mathematics, the universal enveloping algebra of a Lie algebra is the unital associative algebra whose representations correspond precisely to the representations of that Lie algebra.
Universal enveloping algebras are used in the represent ...
. 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 In group theory, a branch of mathematics, the commutator collecting process is a method for writing an element of a group as a product of generators and their higher commutators arranged in a certain order. The commutator collecting process was in ...
, 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 In group theory, a branch of mathematics, the commutator collecting process is a method for writing an element of a group as a product of generators and their higher commutators arranged in a certain order. The commutator collecting process was in ...
was described first, in 1934, by
Philip Hall
Philip Hall FRS (11 April 1904 – 30 December 1982), was an English mathematician. His major work was on group theory, notably on finite groups and solvable groups.
Biography
He was educated first at Christ's Hospital, where he won the Thomps ...
and explored in 1937 by
Wilhelm Magnus
Hans Heinrich Wilhelm Magnus known as Wilhelm Magnus (February 5, 1907 in Berlin, Germany – October 15, 1990 in New Rochelle, New York) was a German-American mathematician. He made important contributions in combinatorial group theory, Lie alge ...
. Hall sets were introduced by
Marshall Hall based on work of Philip Hall on groups.
[
]
Subsequently,
Wilhelm Magnus
Hans Heinrich Wilhelm Magnus known as Wilhelm Magnus (February 5, 1907 in Berlin, Germany – October 15, 1990 in New Rochelle, New York) was a German-American mathematician. He made important contributions in combinatorial group theory, Lie alge ...
showed that they arise as the
graded Lie algebra In mathematics, a graded Lie algebra is a Lie algebra endowed with a gradation which is compatible with the Lie bracket. In other words, a graded Lie algebra is a Lie algebra which is also a nonassociative graded algebra under the bracket oper ...
associated with the
filtration on a
free group
In mathematics, the free group ''F'S'' over a given set ''S'' consists of all words that can be built from members of ''S'', considering two words to be different unless their equality follows from the group axioms (e.g. ''st'' = ''suu''−1' ...
given by the
lower central series
In mathematics, especially in the fields of group theory and Lie theory, a central series is a kind of normal series of subgroups or Lie subalgebras, expressing the idea that the commutator is nearly trivial. For groups, the existence of a centra ...
. This correspondence was motivated by
commutator identities in
group theory
In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups.
The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ...
due to Philip Hall and
Ernst Witt
Ernst Witt (26 June 1911 – 3 July 1991) was a German mathematician, one of the leading algebraists of his time.
Biography
Witt was born on the island of Alsen, then a part of the German Empire. Shortly after his birth, his parents moved the ...
.
Hall set
The Hall set is a
totally ordered
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexive ...
subset of a free non-associative algebra, that is, a
free magma. Let
be a set of generators, and let
be the free magma over
. The free magma is simply the set of non-associative strings in the letters of
, 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 whose leaves are elements of
.
The Hall set
can be constructed recursively as follows:
* The elements of
are given an arbitrary total order.
* The Hall set contains the generators:
* A formal commutator
if and only if
and
and
and:
** Either
(and thus
),
** Or