list of Hall basis

2012-05-22T22:00:37Z

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.

Answer by Adrien for list of Hall basis

2012-05-23T08:05:31Z

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

WeightedIntegerVectors(d,[d1,..,dk])

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,

LyndonWords(L):

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

Example:

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

gives

degree 1
1
degree 2
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 == []:
    return
k=0
while (e[k]==0):
    k=k+1
for z in sage.combinat.necklace._sfc(e[k:], equality=True):
    yield LyndonWord([i+k+1 for i in z], check=False)

list of Hall basis - MathOverflow

list of Hall basis

Answer by Adrien for list of Hall basis