# list of Hall basis

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.

• Have you checked Reutenauer's book Free Lie algebras"? Commented May 22, 2012 at 22:28
• For the non-graded case here is webpage that can compute them: coropa.sourceforge.net/#cgi Commented May 23, 2012 at 2:25
• What do you call "graded"? there are many incompatible uses of this word.
– YCor
Commented Oct 14, 2018 at 9:12

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)

• This gives you the Lyndon basis, not the Hall basis. Compare with the output of this webapp: coropa.sourceforge.net/#cgi Commented May 23, 2012 at 10:09
• In fact I'm not sure there is "one" Hall basis, but rather many basis associated to so-called "Hall Sets" (en.wikipedia.org/wiki/Hall_set#Hall_sets) of which the set of Lyndon word is a particular (algorithmically efficient) example. Commented May 23, 2012 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. Commented May 23, 2012 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.) Commented May 23, 2012 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. Commented May 23, 2012 at 15:25

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.

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.

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