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


Your Answer

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

Browse other questions tagged or ask your own question.