HOME

TheInfoList



OR:

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 A= be a set of generators, and let M(A) be the free magma over A. The free magma is simply the set of non-associative strings in the letters of 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 whose leaves are elements of A. The Hall set H\subseteq M(A) can be constructed recursively as follows: * The elements of A are given an arbitrary total order. * The Hall set contains the generators: A\subseteq H. * A formal commutator ,yin H if and only if x\in H and y\in H and x>y and: ** Either x\in A (and thus y\in A), ** Or x= ,v/math> with u\in H and v\in H and v\le y. * The commutators can be ordered arbitrarily, provided that y < ,y/math> always holds. The construction and notation used below are nearly identical to that used in 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 ...
, and so can be directly compared; the weights are the string-lengths. The difference is that no mention of groups is required. These definitions all coincide with that of X. Viennot. Note that some authors reverse the order of the inequality. Note also that one of the conditions, the v\le y, may feel "backwards"; this "backwardness" is what provides the descending order required for factorization. Reversing the inequality does ''not'' reverse this "backwardness".


Example

Consider the generating set with two elements \. Define a>b and write xy for ,y/math> to simplify notation, using parenthesis only as needed. The initial members of the Hall set are then (in order) :\begin &b, a, \\ &ab, \\ &(ab)b, \;\;(ab)a, \\ &((ab)b)b, \;\;((ab)b)a,\;\; ((ab)a)a, \\ &(((ab)b)b)b, \; (((ab)b)b)a, \; (((ab)b)a)a, \; (((ab)a)a)a,\; ((ab)b)(ab),\; ((ab)a)(ab), \\ & \cdots \end Notice that there are 2,1,2,3,6,\ldots elements of each distinct length. This is the beginning sequence of the necklace polynomial in two elements (described next, below).


Combinatorics

A basic result is that the number of elements of length k in the Hall set (over n generators) is given by the necklace polynomial : M_n(k) \ =\ \sum_\mu\!\left(\right)n^d = \sum_\mu\!\left(\right)n^ where \mu is the classic
Möbius function The Möbius function is a multiplicative function in number theory introduced by the German mathematician August Ferdinand Möbius (also transliterated ''Moebius'') in 1832. It is ubiquitous in elementary and analytic number theory and most of ...
. The sum is a
Dirichlet convolution In mathematics, the Dirichlet convolution is a binary operation defined for arithmetic functions; it is important in number theory. It was developed by Peter Gustav Lejeune Dirichlet. Definition If f , g : \mathbb\to\mathbb are two arithmetic fun ...
.


Definitions and Lemmas

Some basic definitions are useful. Given a tree t= ,y/math>, the element x is called the immediate left subtree, and likewise, y is the immediate right subtree. A right subtree is either y itself, or a right subtree of either x or y. This is in contrast to the extreme right subtree, which is either y itself, or an extreme right subtree of y. A basic lemma is that if v is a right subtree of a Hall tree t= ,y/math>, then v\le y.


Hall words

Hall words are obtained from the Hall set by "forgetting" the commutator brackets, but otherwise keeping the notion of total order. It turns out that this "forgetting" is harmless, as the corresponding Hall tree can be deduced from the word, and it is unique. That is, the Hall words are in one-to-one correspondence with the Hall trees. The total order on the Hall trees passes over to a total order on the Hall words. This correspondence allows a
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 ...
: given 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 ...
A^*, any element of A^* 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 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 provided by the
Chen–Fox–Lyndon theorem 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 tha ...
. More precisely, every word w\in A^* can be written as a concatenation of Hall words :w=h_1h_2\cdots h_k with each Hall word h_j being totally ordered by the Hall ordering: :h_1\le h_2\le\cdots\le h_k. In this way, the Hall word ordering extends to a total order on the monoid. The lemmas and theorems required to provide the word-to-tree correspondence, and the unique ordering, are sketched below.


Foliage

The foliage of a magma M(A) is the canonical mapping f:M(A)\to A^* from the magma to 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 ...
A^*, given by f:a\mapsto a for a\in A and f: ,ymapsto f(x)f(y) otherwise. 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.


Factorization of Hall words

Let t= ,yin H be a Hall tree, and w=f( ,y be the corresponding Hall word. Given any factorization of a Hall word w=uv into two non-empty strings u and v, then there exists a factorization into Hall trees such that u=f(x_1)\cdots f(x_m) and v=f(y_1)\cdots f(y_n) with :x_1,\ldots ,x_m > y_1 and :y_1 \le y_2 \le \cdots \le y_n \le y. This and the subsequent development below are given by Guy Melançon. Guy Melançon, (1992)
Combinatorics of Hall trees and Hall words
, ''Journal of Combinatorial Theory'', 59A(2) pp. 285–308.


Correspondence

The converse to the above factorization establishes the correspondence between Hall words and Hall trees. This can be stated in the following interesting form: if t is a Hall tree, and the corresponding Hall word f(t) factorizes as :f(t)=f(t_1)\cdots f(t_n) with :f(t_1)\le \cdots \le f(t_n) then n=1. In other words, Hall words ''cannot'' be factored into a descending sequence of other Hall words. This implies that, given a Hall word, the corresponding tree can be uniquely identified.


Standard factorization

The total order on Hall trees passes over to Hall words. Thus, given a Hall word w=f( ,y, it can be factorized as w=f(x)f(y) with f(x)>f(y). This is termed the standard factorization.


Standard sequence

A
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
of Hall words (w_1, w_2, \ldots, w_n) is said to be a standard sequence if each w_i is either a letter, or a standard factorization w_i=u_iv_i with v_i\le w_,\cdots, w_n. Note that increasing sequences of Hall words are standard.


Term rewriting

The unique factorization of any word w\in A^* into a concatenation of an ascending sequence of Hall words w=h_1h_2\cdots h_k with h_1\le h_2\le\cdots\le h_k can be achieved by defining and recursively applying a simple
term rewriting system In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. Such methods may be achieved by rewriting systems (also known as rewrite systems, rewrite engines, or red ...
. The uniqueness of the factorization follows from the
confluence In geography, a confluence (also: ''conflux'') occurs where two or more flowing bodies of water join to form a single channel. A confluence can occur in several configurations: at the point where a tributary joins a larger river (main stem); o ...
properties of the system. The rewriting is performed by the exchange of certain pairs of consecutive Hall words in a sequence; it is given after these definitions. A drop in a sequence (h_1, h_2, \ldots, h_n) of Hall words is a pair (h_i, h_) such that h_i > h_. If the sequence is a standard sequence, then the drop is termed a legal drop if one also has that h_\le h_,\ldots,h_n. Given a standard sequence with a legal drop, there are two distinct rewrite rules that create new standard sequences. One concatenates the two words in the drop: :(h_1, h_2, \ldots, h_n)\to (h_1, h_2, \ldots, h_ih_, \ldots, h_n) while the other permutes the two elements in the drop: :(h_1, h_2, \ldots, h_n)\to (h_1, h_2, \ldots, h_, h_, h_i, h_, \ldots, h_n) It is not hard to show that both rewrites result in a new standard sequence. 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.


Total order

A total order can be provided on the words w\in A^*. This is similar to the standard
lexicographic order In mathematics, the lexicographic or lexicographical order (also known as lexical order, or dictionary order) is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of a ...
, but at the level of Hall words. Given two words u, v factored into ascending Hall word order, ''i. e.'' that :u=u_1u_2\cdots u_m\quad and \quad v=v_1v_2\cdots v_n with each u_i, v_j a Hall word, one has an ordering that u if either :m and \quad u_1=v_1,\,u_2=v_2,\,\cdots, u_m=v_m or if :u_1=v_1,\,u_2=v_2,\,\ldots, u_k=v_k\quad and \quad u_


Properties

Hall words have a number of curious properties, many of them nearly identical to those for
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. The first and most important property is that Lyndon words are a special case of Hall words. That is, the definition of a Lyndon word satisfies the definition of the Hall word. This can be readily verified by direct comparison; note that the direction of the inequality used in the definitions above is exactly the reverse of that used in the customary definition for Lyndon words. The set of Lyndon trees (which follow from the standard factorization) is a Hall set. Other properties include: * Hall words are acyclic, also known as primitive. That is, they cannot be written in the form w=x^n for some word x\in A^* and n>1. * A word w\in A^* is a Hall word if and only if for any factorization of w=uv into non-empty words obeys w > vu. In particular, this implies that no Hall word is a conjugate of another Hall word. Note again, this is exactly as it is for a Lyndon word: Lyndon words are the least of their conjugacy class; Hall words are the greatest. * A word w\in A^* is a Hall word if and only if it is larger than any of its proper right factors. This follows from the previous two points. * Every primitive word w\in A^* is conjugate to a Hall word. That is, there exists a
circular shift In combinatorial mathematics, a circular shift is the operation of rearranging the entries in a tuple, either by moving the final entry to the first position, while shifting all other entries to the next position, or by performing the inverse oper ...
of w that is a Hall word. Equivalently, there exists a factorization w=uv such that vu is a Hall word. This conjugate is unique, since no Hall word is a conjugate of another Hall word. * Every word w\in A^* is the conjugate of a power of a unique Hall word.


Implications

There is a similar term rewriting system for
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, this is how the factorization of a monoid is accomplished with Lyndon words. Because the Hall words can be placed into Hall trees, and each Hall tree can be interpreted as a commutator, the term rewrite can be used to perform 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 ...
on a group. Another very important application of the rewrite rule is to perform the commutations that appear in 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 ...
. A detailed discussion of the commutation is provided in the article on
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 ...
s. Note that term rewriting with Lyndon words can also be used to obtain the needed commutation for the PBW theorem. Guy Melançon and C. Reutenauer (1989), "Lyndon words, free algebras and shuffles", ''Canadian Journal of Mathematics''. 41, No. 4, pp. 577-591.


History

Hall sets were introduced by Marshall Hall based on work of
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 ...
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 ...
.


See also

* Hall–Petresco identity *
Markov odometer In mathematics, a Markov odometer is a certain type of topological dynamical system. It plays a fundamental role in ergodic theory and especially in orbit theory of dynamical systems, since a theorem of H. Dye asserts that every ergodic nonsingu ...


References

Formal languages Combinatorics on words