Hall word

Last updated March 13, 2023

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.^[1]^[2] Hall sets were introduced by Marshall Hall based on work of Philip Hall on groups.^[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.

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},\ldots ,a_{n}}$ 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 with leaves marked by elements of $A$ .

The Hall set $H\subseteq M(A)$ can be constructed recursively (in increasing order) as follows:

The elements of $A$ are given an arbitrary total order.
The Hall set contains the generators: $A\subseteq H.$
A formal commutator $[x,y]\in H$ $Hall word$ if and only if $x\in H$ $Hall word$ and $y\in H$ $Hall word$ and $x>y$ $Hall word$ and:
- Either $x\in A$ (and thus $y\in A$ ),
- Or $x=[u,v]$ with $u\in H$ and $v\in H$ and $v\leq y$ .
The commutators can be ordered arbitrarily, provided that $y<[x,y]$ always holds.

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 difference is that no mention of groups is required. These definitions all coincide with that of X. Viennot.^[4] Note that some authors reverse the order of the inequality. Note also that one of the conditions, the $v\leq 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 $\{a,b\}.$ Define $a>b$ and write $xy$ for $[x,y]$ to simplify notation, using parenthesis only as needed. The initial members of the Hall set are then (in order)

{\begin{aligned}&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{aligned}}

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)\ =\ {1 \over k}\sum _{d\,|\,k}\mu \!\left({k \over d}\right)n^{d}={1 \over k}\sum _{d\,|\,k}\mu \!\left({d}\right)n^{k/d}

where $\mu$ is the classic Möbius function. The sum is a Dirichlet convolution.

Definitions and Lemmas

Some basic definitions are useful. Given a tree $t=[x,y]$ , 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$ . An extreme right subtree 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=[x,y]$ , then $v\leq 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: given the free monoid $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 words provided by the Chen–Fox–Lyndon theorem.

More precisely, every word $w\in A^{*}$ can be written as a concatenation of Hall words

w=h_{1}h_{2}\cdots h_{k}

with each Hall word $h_{j}$ being totally ordered by the Hall ordering:

h_{1}\leq h_{2}\leq \cdots \leq 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 $A^{*}$ , given by $f:a\mapsto a$ for $a\in A$ and $f:[x,y]\mapsto 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=[x,y]\in H$ be a Hall tree, and $w=f([x,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}\leq y_{2}\leq \cdots \leq y_{n}\leq y.

This and the subsequent development below are given by Guy Melançon.^[5]

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})\leq \cdots \leq f(t_{n})

then $n=1$ . In other words, Hall words cannot be factored into a descending sequence of other Hall words.^[5] 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([x,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 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_{i}v_{i}$ with $v_{i}\leq w_{i+1},\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_{1}h_{2}\cdots h_{k}$ with $h_{1}\leq h_{2}\leq \cdots \leq h_{k}$ 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.

A drop in a sequence $(h_{1},h_{2},\ldots ,h_{n})$ of Hall words is a pair $(h_{i},h_{i+1})$ such that $h_{i}>h_{i+1}.$ If the sequence is a standard sequence, then the drop is termed a legal drop if one also has that $h_{i+1}\leq h_{i+2},\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_{i}h_{i+1},\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_{i-1},h_{i+1},h_{i},h_{i+2},\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, but at the level of Hall words. Given two words $u,v$ factored into ascending Hall word order, i. e. that

u=u_{1}u_{2}\cdots u_{m}\quad

and

\quad v=v_{1}v_{2}\cdots v_{n}

with each $u_{i},v_{j}$ a Hall word, one has an ordering that $u<v$ if either

m<n\quad

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_{k+1}<v_{k+1}.

Properties

Hall words have a number of curious properties, many of them nearly identical to those for Lyndon words. 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 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 words, 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 on a group.

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.^[6]

History

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

Related Research Articles

In mathematics, the commutator gives an indication of the extent to which a certain binary operation fails to be commutative. There are different definitions used in group theory and ring theory.

In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0.

Independence is a fundamental notion in probability theory, as in statistics and the theory of stochastic processes. Two events are independent, statistically independent, or stochastically independent if, informally speaking, the occurrence of one does not affect the probability of occurrence of the other or, equivalently, does not affect the odds. Similarly, two random variables are independent if the realization of one does not affect the probability distribution of the other.

In mathematics, an embedding is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup.

The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946. Because it is simpler than the halting problem and the Entscheidungsproblem it is often used in proofs of undecidability.

In statistics, a statistic is sufficient with respect to a statistical model and its associated unknown parameter if "no other statistic that can be calculated from the same sample provides any additional information as to the value of the parameter". In particular, a statistic is sufficient for a family of probability distributions if the sample from which it is calculated gives no additional information than the statistic, as to which of those probability distributions is the sampling distribution.

In mathematics, a linear form is a linear map from a vector space to its field of scalars.

In mathematics, a differential operator is an operator defined as a function of the differentiation operator. It is helpful, as a matter of notation first, to consider differentiation as an abstract operation that accepts a function and returns another function.

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.

In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring formed from the set of polynomials in one or more indeterminates with coefficients in another ring, often a field.

In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero elements, often called the empty string and denoted by ε or λ, as the identity element. The free monoid on a set A is usually denoted A^∗. The free semigroup on A is the subsemigroup of A^∗ containing all elements except the empty string. It is usually denoted A⁺.

In mathematics, the Fredholm determinant is a complex-valued function which generalizes the determinant of a finite dimensional linear operator. It is defined for bounded operators on a Hilbert space which differ from the identity operator by a trace-class operator. The function is named after the mathematician Erik Ivar Fredholm.

Verma modules, named after Daya-Nand Verma, are objects in the representation theory of Lie algebras, a branch of mathematics.

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.

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 investigated them in 1954, calling them standard lexicographic sequences. Anatoly Shirshov introduced Lyndon words in 1953 calling them regular words. Lyndon words are a special case of Hall words; almost all properties of Lyndon words are shared by Hall words.

Parikh's theorem in theoretical computer science says that if one looks only at the number of occurrences of each terminal symbol in a context-free language, without regard to their order, then the language is indistinguishable from a regular language. It is useful for deciding that strings with a given number of terminals are not accepted by a context-free grammar. It was first proved by Rohit Parikh in 1961 and republished in 1966.

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 that the Lyndon words furnish a factorisation. The Schützenberger theorem relates the definition in terms of a multiplicative property to an additive property.

In stochastic analysis, a rough path is a generalization of the notion of smooth path allowing to construct a robust solution theory for controlled differential equations driven by classically irregular signals, for example a Wiener process. The theory was developed in the 1990s by Terry Lyons. Several accounts of the theory are available.

In the mathematical field of group theory, an Artin transfer is a certain homomorphism from an arbitrary finite or infinite group to the commutator quotient group of a subgroup of finite index. Originally, such mappings arose as group theoretic counterparts of class extension homomorphisms of abelian extensions of algebraic number fields by applying Artin's reciprocity maps to ideal class groups and analyzing the resulting homomorphisms between quotients of Galois groups. However, independently of number theoretic applications, a partial order on the kernels and targets of Artin transfers has recently turned out to be compatible with parent-descendant relations between finite p-groups, which can be visualized in descendant trees. Therefore, Artin transfers provide a valuable tool for the classification of finite p-groups and for searching and identifying particular groups in descendant trees by looking for patterns defined by the kernels and targets of Artin transfers. These strategies of pattern recognition are useful in purely group theoretic context, as well as for applications in algebraic number theory concerning Galois groups of higher p-class fields and Hilbert p-class field towers.

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 introduced by Philip Hall in 1934 and articulated by Wilhelm Magnus in 1937. The process is sometimes called a "collection process".

References

↑ Hall, Philip (1934), "A contribution to the theory of groups of prime-power order", Proceedings of the London Mathematical Society, 36: 29–95, doi:10.1112/plms/s2-36.1.29
↑ W. Magnus, (1937) "Über Beziehungen zwischen höheren Kommutatoren", J. Grelle177, 105-115.
1 2 Hall, Marshall (1950), "A basis for free Lie rings and higher commutators in free groups", Proceedings of the American Mathematical Society , 1 (5): 575–581, doi: 10.1090/S0002-9939-1950-0038336-7 , ISSN 0002-9939, MR 0038336
↑ X. Viennot, (1978) "Algèbres de Lie libres et monoïdes libres" , Lecture Notes in Mathematics, 691 , Springer–Verlag
1 2 3 Guy Melançon, (1992) "Combinatorics of Hall trees and Hall words", Journal of Combinatorial Theory, 59A(2) pp. 285–308.
↑ Guy Melançon and C. Reutenauer (1989), "Lyndon words, free algebras and shuffles", Canadian Journal of Mathematics. 41, No. 4, pp. 577-591.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Hall, Philip (1934), "A contribution to the theory of groups of prime-power order", Proceedings of the London Mathematical Society, 36: 29–95, doi:10.1112/plms/s2-36.1.29

[2] W. Magnus, (1937) "Über Beziehungen zwischen höheren Kommutatoren", J. Grelle177, 105-115.

[mhall-3] 1 2 Hall, Marshall (1950), "A basis for free Lie rings and higher commutators in free groups", Proceedings of the American Mathematical Society , 1 (5): 575–581, doi: 10.1090/S0002-9939-1950-0038336-7 , ISSN 0002-9939, MR 0038336

[4] X. Viennot, (1978) "Algèbres de Lie libres et monoïdes libres" , Lecture Notes in Mathematics, 691 , Springer–Verlag

[melancon-5] 1 2 3 Guy Melançon, (1992) "Combinatorics of Hall trees and Hall words", Journal of Combinatorial Theory, 59A(2) pp. 285–308.

[6] Guy Melançon and C. Reutenauer (1989), "Lyndon words, free algebras and shuffles", Canadian Journal of Mathematics. 41, No. 4, pp. 577-591.

[1]

[2]

[3]

[4]

[5]

[6]