Lyndon basis

Summary

The Lyndon basis is a basis of a free Lie algebra indexed by Lyndon words. A Lyndon word is a word that is strictly smaller, in lexicographic order, than each of its proper suffixes. Each Lyndon word gets a bracketing from its standard factorization, and these brackets form a basis. It is a Hall basis. It explains why the number of Lyndon words of length $n$ equals the dimension of the degree $n$ part of the free Lie algebra.