I am looking for an algorithm to produce Hall basis from Lyndon words. First I will recall the definition of the Hall set following Serre's presentation.

Let $X$ be a finite set and let $M(X)$ be the free Magma on $X$. Length of any word in $M(X)$ is denoted by $\ell(w)$ and let $M^n(X)$ denote the set of elements of $M(X)$ of length $n$. A Hall set relative to $X$ is a totally ordered subset $H$ of $M(X)$ satisfying the following conditions:

  1. If $u \in H$, $v\in H$ and $\ell(u) < \ell(v)$, then $u < v$ in the total order.
  2. $X \subseteq H$ and $H \cap M^2(X)$ consists of the products $[x, y]$ with $x, y$ in $X$ and $x < y$.
  3. An element $w$ of $M(X)$ of length $\geq 3$ belongs to $H$ if and only if it is of the form $[a, [b, c]]$ with $a, b, c$ in $H$, $[b, c] \in H$, $b \leq a < [b, c]$ and $b < c$.

One can show that $H$ is a basis for the free Lie algebra on $X$. For instance: $$1,\, 2,\, [1,2],\, [1,[1,2]],\, [2,[1,2]]$$ are elements of the Hall basis of length at most $3$. One can obtain another basis for a free algebra using bracketing Lyndon words. For instance $$[1,1,1,2,2]$$ is a Lyndon word and its bracketing produces the following element in the free Lie algebra $$[1,[1,[[1,2],2]]]$$ which does not belong to the Hall basis. Is their any concrete bijection between Lyndon words on $X$ and the Hall basis on $X$?


There is no simple connection. Note that there are many different Hall sets H. The Lyndon basis is not such a Hall basis.

However, one can easily relax the definition of Hall set slightly in such a way as the Lyndon basis becomes included, and I think the relaxed definition is now the more common one. See https://www.encyclopediaofmath.org/index.php/Hall_set (but note that the order of [,] is flipped and < and > are flipped compared to the convention you mention.)

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.