Form of elements of a Lie algebra How can we write the elements of a free Lie algebra? Is there any reference concerning  this subject?
 A: The key words are "Lyndon words". A reference is Free Lie Algebras by C. Reutenauer.
A: Yes, as was said previously the key is Lyndon words and the reference is Reutenauer's book "Free Lie algebras". Your free Lie algebra reads $L_R<X>$ where $X$ is an alphabet (i.e. a set) and $R$ is a unitary ring. If your (free Lie) algebra is given by $L(V)$ where $V$ is a free module over $R$, take for $X$ any basis of $V$. Now you need :


*

* a total order on $X$ and its associated lexicographic (total) order $\prec_{lex}$

* the set $Lyn(X)$ of Lyndon words which are strict minima of their conjugacy class or, equivalently,
$$
Lyn(X)=\{w\in X^+| (w=uv\ ;\ u\in X^+)\Longrightarrow w\prec_{lex} v\} 
$$
where $X^+$  is the set of non empty words on $X$ which can be phased as 
>Lyndon words is the set of non empty words that are smaller than all their proper right factors.  

* as a lemma, one shows that every Lyndon word $l$ which is not a letter can be written (in sevral ways in general) as $l=l_1l_2$ with $l_1\prec_{lex}l_2$, one notes $\sigma(l)$ the factorisation with $|l_2|$ maximal. This is called the _canonical factorisation_ 

* The Lyndon basis $(P_l)_{l\in Lyn(X)}$ ($L(V)$ is a free module over $R$ and this basis is a linear basis of $L(V)$) is constructed by 

*

* $P_x=x$ if $x\in X$

* $P_l=[P_{l_1},P_{l_2}]$ otherwise and with $\sigma(l)=(l_1,l_2)$
   

* **Decomposition** Every Lie polynomial "begins" lexicographically by a Lyndon word and one can show that $P_l=l+\ \mathrm{higher\ terms}$. You get therefore 

*

* a test to know whether a polynomial is Lie (independant of the characteristic and even of the ring $R$)

* an algorithm for the decomposition

  

Addition. This algorithm has many applications. One of them is to compute the multiplication table of the Free Lie algebra (combinatorial problem still open) i.e. the structure constants 
$$
[P_{l_1},P_{l_2}]=\sum_{l\in Lyn(X)}\gamma_{l_1,l_2}^l\,P_l
$$  
A: "Lie Algebras: Theory and Algorithms" by Willem A. De Graaf has a chapter dealing with the more general problem of explicit construction of a basis of a finitely presented Lie algebra (free Lie algebra modulo an ideal), perhaps it is what you are looking for.
