MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Anyone know a place where the standard Hall basis is listed up to at lest 5 fold brackets? and for gradedLie algebras?

The rules are clear but I'd rather not turn the crank myself. Google search did not get me there quickly.

share|cite|improve this question
Have you checked Reutenauer's book ``Free Lie algebras"? – Jim Conant May 22 '12 at 22:28
Edited the tags – David Roberts May 23 '12 at 0:10
For the non-graded case here is webpage that can compute them: – Omar Antolín-Camarena May 23 '12 at 2:25

These are easily obtained with SAGE:

for i in range(1,6):
 for w in StandardBracketedLyndonWords(2, i):
     print w

Edit: And for the graded case, since the function which generates Lyndon words knows what a composition is, you can use the function


which find all positive solutions of $$\sum \lambda_i d_i=d$$ for a given $d$. Then for any given solution $L=[\lambda_1,\dots,\lambda_n]$ in the form of a Python list,


will return all the Lyndon words on $n$ letters containing exactly $\lambda_i$ times the $i$th letter. You'll get this way all Lyndon words of degree $d$. Warning: there is just a small issue: the LyndonWords function seems to have trouble with lists beginning by 0, so the code below use a modified function, see the end of this post...


for i in range(1,6):
print "degree "+str(i)
for l in L:
     for w in MyLyndon(list(l)):
         print sage.combinat.lyndon_word.standard_bracketing(w)


degree 1
degree 2
degree 3
[1, 2]
degree 4
[1, [1, 2]]
degree 5
[[1, 2], 2]
[1, [1, [1, 2]]]

Since Omar pointed this out, let me recall that standard bracketing of Lyndon words provides a Hall basis, maybe not "the" Hall basis you have in mind.

If I'm not wrong, a Lyndon word o composition $(0,\dots,0,k_{j+1},\dots,k_n)$ with $j$ 0's at the beginning is the same as a Lyndon word of composition $(k_{j+1},\dots,k_n)$ with letters shifted by $j$ (since it has to be a Lyndon basis of the sub-Lie algebra generated by $x_{j+1},\dots,x_n$. So hopefully the following code will do the trick:

def myLyndon(e):
if e == []:
while (e[k]==0):
for z in sage.combinat.necklace._sfc(e[k:], equality=True):
    yield LyndonWord([i+k+1 for i in z], check=False)
share|cite|improve this answer
This gives you the Lyndon basis, not the Hall basis. Compare with the output of this webapp: – Omar Antolín-Camarena May 23 '12 at 10:09
In fact I'm not sure there is "one" Hall basis, but rather many basis associated to so-called "Hall Sets" ( of which the set of Lyndon word is a particular (algorithmically efficient) example. – Adrien May 23 '12 at 11:21
With the name I learned (which I'm not sure are standard), there is something called a "generalized Hall basis" of which both the Lyndon and Hall basis are examples. But in the terminology I learned, the Hall basis is definitely a specific basis and is different from the Lyndon basis. Just to repeat, the web app I linked computes the thing I was told to call the Hall basis. – Omar Antolín-Camarena May 23 '12 at 15:05
(I should say, my first thought to check if SAGE had a function to compute the Hall basis and I was a little surprised to see in the docs that it had the StandardBracketedLyndonWords function, but no function for the Hall basis. Since I thought Stasheff meant the other basis specifically --which may or may not be true-- I googled a bit more until I found CoRoPa, which does compute it.) – Omar Antolín-Camarena May 23 '12 at 15:08
It seems to me that Hall basis differ only in the (rather arbitrary) choice of some total ordering on the set of previously computed elements. I think Hall gave some specific choice in his paper, which is maybe what is called "the" Hall basis, while the Lyndon one is "a" Hall basis basically relying on the lexicographic order. Hence, I would say that the Hall basis is the first one historically speaking, but doesn't enjoy other specific properties which would make it more usefull than another one. of course I may be wrong. – Adrien May 23 '12 at 15:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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