list of Hall basis

Question

Anyone know a place where the standard Hall basis is listed up to at least 5-fold brackets? And for graded Lie algebras?

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

Answer 1

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)

Answer 2

much of the computational work in rough path theory relies on working with Hall bases. You can find an interactive web page that generates Hall bases for you at https://coropa.sourceforge.io/ Half way down the opening page. It is quite old but I think it still works. (the most up to date version of the code is in the source distribution on pypi for the package esig.

As others said, there is no unique hall basis.

Answer 3

There are many hall sets, hall bases. They are important because there is no natural or easy choice of linear basis for the free lie algebra in terms of brackets of the letters that generate it as a Lie algebra. The anti-symmetry and the Jacobi identities both provide linear relations between elements and make the goal of finding a good basis more challenging.

Hall, Reutenhauer, Bourbaki, all provide examples of sufficient conditions on a set of brackets of brackets of … of letters to ensure they are linear basis for the free Lie algebra.

Often, in calculations, it is simply important that one has a basis and that there is an efficient method to calculate the lie bracket of any two basis elements as a linear combination of basis elements. Hall bases provide the first and a convenient recursive definition that exploits the Jacobi identity for the second.

Coropa aimed at solving differential equations and needed these bases in real time; the app lists "A" hall basis for any depth and dimension but it is not "THE" hall basis. The underlying code libalgebra is still maintained and uses this basis for the Lie elements.

The C++ code can be found at https://github.com/terrylyons/libalgebra/blob/master/libalgebra/lie_basis.h and the member function inline void growup(DEG desired_degree) builds it inductively and is pretty simple. The basis is an array of pairs of integers. The initial entry (0,0) is not a member of the basis, the letters are (0,1),...(0,n). All other elements are the indexes of two earlier elements built in a natural inductive way. (Caution, you need to flip the orders to get the standard definition of hall order)

The Lyndon basis is another basis for the Lie elements. It does not respect the degree but has other properties. Reutenhauer and Bourbaki are both good references for the theory.

If you want to have your own code use libalgeba look at the unit tests for hall set.

Answer 4

java application for calculations in free Lie algebra https://github.com/shma2001gmailcom/lie-fe/tree/master/src/main/java/org/misha