Lyndon words and Hall basis

Question

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$?

Answer 1

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.)