Hall word

Consider the generating set with two elements ${\displaystyle \{a,b\}.}$ Define ${\displaystyle a>b}$ and write ${\displaystyle xy}$ for ${\displaystyle [x,y]}$ to simplify notation, using parenthesis only as needed. The initial members of the Hall set are then (in order)

${\displaystyle {\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 ${\displaystyle 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).

A basic result is that the number of elements of length ${\displaystyle k}$ in the Hall set (over ${\displaystyle n}$ generators) is given by the necklace polynomial

${\displaystyle 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 ${\displaystyle \mu }$ is the classic Möbius function. The sum is a Dirichlet convolution.

Some basic definitions are useful. Given a tree ${\displaystyle t=[x,y]}$, the element ${\displaystyle x}$ is called the immediate left subtree, and likewise, ${\displaystyle y}$ is the immediate right subtree. A right subtree is either ${\displaystyle y}$ itself, or a right subtree of either ${\displaystyle x}$ or ${\displaystyle y}$. An extreme right subtree is either ${\displaystyle y}$ itself or an extreme right subtree of ${\displaystyle y}$.

A basic lemma is that if ${\displaystyle v}$ is a right subtree of a Hall tree ${\displaystyle t=[x,y]}$, then ${\displaystyle v\leq y.}$

The foliage of a magma ${\displaystyle M(A)}$ is the canonical mapping ${\displaystyle f:M(A)\to A^{*}}$ from the magma to the free monoid ${\displaystyle A^{*}}$, given by ${\displaystyle f:a\mapsto a}$ for ${\displaystyle a\in A}$ and ${\displaystyle 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.

Let ${\displaystyle t=[x,y]\in H}$ be a Hall tree, and ${\displaystyle w=f([x,y])}$ be the corresponding Hall word. Given any factorization of a Hall word ${\displaystyle w=uv}$ into two non-empty strings ${\displaystyle u}$ and ${\displaystyle v}$, then there exists a factorization into Hall trees such that ${\displaystyle u=f(x_{1})\cdots f(x_{m})}$ and ${\displaystyle v=f(y_{1})\cdots f(y_{n})}$ with

${\displaystyle x_{1},\ldots ,x_{m}>y_{1}}$

and

${\displaystyle 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]

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 ${\displaystyle t}$ is a Hall tree, and the corresponding Hall word ${\displaystyle f(t)}$ factorizes as

${\displaystyle f(t)=f(t_{1})\cdots f(t_{n})}$

with

${\displaystyle f(t_{1})\leq \cdots \leq f(t_{n})}$

then ${\displaystyle 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.

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

A sequence of Hall words ${\displaystyle (w_{1},w_{2},\ldots ,w_{n})}$ is said to be a standard sequence if each ${\displaystyle w_{i}}$ is either a letter, or a standard factorization ${\displaystyle w_{i}=u_{i}v_{i}}$ with ${\displaystyle v_{i}\leq w_{i+1},\cdots ,w_{n}.}$ Note that increasing sequences of Hall words are standard.

The unique factorization of any word ${\displaystyle w\in A^{*}}$ into a concatenation of an ascending sequence of Hall words ${\displaystyle w=h_{1}h_{2}\cdots h_{k}}$ with ${\displaystyle 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 ${\displaystyle (h_{1},h_{2},\ldots ,h_{n})}$ of Hall words is a pair ${\displaystyle (h_{i},h_{i+1})}$ such that ${\displaystyle 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 ${\displaystyle 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:

${\displaystyle (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:

${\displaystyle (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.

A total order can be provided on the words ${\displaystyle w\in A^{*}.}$ This is similar to the standard lexicographic order, but at the level of Hall words. Given two words ${\displaystyle u,v}$ factored into ascending Hall word order, i. e. that

${\displaystyle u=u_{1}u_{2}\cdots u_{m}\quad }$ and ${\displaystyle \quad v=v_{1}v_{2}\cdots v_{n}}$

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

${\displaystyle m<n\quad }$ and ${\displaystyle \quad u_{1}=v_{1},\,u_{2}=v_{2},\,\cdots ,u_{m}=v_{m}}$

or if

${\displaystyle u_{1}=v_{1},\,u_{2}=v_{2},\,\ldots ,u_{k}=v_{k}\quad }$ and ${\displaystyle \quad u_{k+1}<v_{k+1}.}$