list of Hall basis - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T10:21:26Z http://mathoverflow.net/feeds/question/97703 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/97703/list-of-hall-basis list of Hall basis jim stasheff 2012-05-22T22:00:37Z 2012-05-23T14:36:51Z <p>Anyone know a place where the standard Hall basis is listed up to at lest 5 fold brackets? and for gradedLie algebras?</p> <p>The rules are clear but I'd rather not turn the crank myself. Google search did not get me there quickly.</p> http://mathoverflow.net/questions/97703/list-of-hall-basis/97725#97725 Answer by Adrien for list of Hall basis Adrien 2012-05-23T08:05:31Z 2012-05-23T14:36:51Z <p>These are easily obtained with <a href="http://www.sagemath.org/" rel="nofollow">SAGE</a>:</p> <pre><code>for i in range(1,6): for w in StandardBracketedLyndonWords(2, i): print w </code></pre> <p><strong>Edit:</strong> And for the graded case, since the function which generates Lyndon words knows what a <a href="http://en.wikipedia.org/wiki/Composition_%28number_theory%29" rel="nofollow">composition</a> is, you can use the function </p> <pre><code>WeightedIntegerVectors(d,[d1,..,dk]) </code></pre> <p>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,</p> <pre><code>LyndonWords(L): </code></pre> <p>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$. <strong><em>Warning</em></strong>: 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... </p> <p>Example:</p> <pre><code>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) </code></pre> <p>gives</p> <pre><code>degree 1 1 degree 2 2 degree 3 [1, 2] degree 4 [1, [1, 2]] degree 5 [[1, 2], 2] [1, [1, [1, 2]]] </code></pre> <p>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.</p> <hr> <p>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:</p> <pre><code>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) </code></pre>