# Bracket of lyndon words?

Here is a simple question regarding the standard Lyndon basis for the free Lie Algebra. Suppose I take two lyndon words $m$ and $n$ and their standard bracketings $B(m)$ and $B(n)$ as elements in the free Lie algebra. Suppose further that $m < n$, so that $mn$ is a Lyndon word.

My question is when we express the bracket $[B(m),B(n)]$ in the Lyndon basis, is it of the form

$[B(m),B(n)] = B(mn) + \sum_{l>mn, |l| = |m|+|n|} a_{m,n}^{(l)} B(l)$

• No combinatorists out there? I think this is a basic enough question! Feb 5 '13 at 17:14
• Yes it is basic but up to my knowledge very little is known on these structure constants. Do you know more now ? Jun 7 '15 at 9:18
• If anybody's still following this question: Mr Duchamp, you say "little is known on these structure constants". Could you tell us what is known (and where to find it)? More specifically, I'm searching for a formula/algorithm that gives me $[B(a),B(w)] = \sum_u \alpha_u B(u)$ with $a$ a letter, $w$ and the $u$'s Lyndon words, and the $\alpha_u$ numbers (which I understand will be integers). Nov 17 '16 at 8:14
• @DavidVercauteren I am now far from closely monitoring this subject, sorry. What you can remark is that, to each Lyndon word is associated a binary tree (see Lothaire, Combinatorics on Words Chapter 5.3). Jun 21 '18 at 3:24

Yes it is of this form because any Lie polynomial "begins" by a Lyndon word, in particular, the least monomial of $B(l)$ is $l$. Then $$B(m)=m+\sum_{m<u\atop |u|=|m|} \alpha^{(u)}u;\ B(n)=n+\sum_{m<v\atop |v|=|n|} \alpha^{(v)}v\qquad \mathbf{(LB)}$$
then $[B(m),B(n)]$ has only words of length $|m|+|n|$ and its least word is $mn$.

Computationally

1. $$B(m)B(n)=mn+[\sum_{m<v\atop |v|=|n|} \alpha^{(v)}mv+\sum_{m<u\atop |u|=|m|} \alpha^{(u)}un]=mn+[sb1]$$ all the monomials within square brackets are of same length and strictly greater than $mn$
2. $$B(n)B(m)=nm+[\sum_{m<v\atop |v|=|n|} \alpha^{(v)}vm+\sum_{m<u\atop |u|=|m|} \alpha^{(u)}nu]=nm+[sb2]$$ all the monomials within square brackets are of same length and strictly greater than $nm$.
3. But, $mn<nm$ because $mn$ is Lyndon and then $$[B(m),B(n)]=mn+[sb1]-nm-[sb2]=mn+[sb3]$$ where the square bracket $[sb3]$ is a linear combination of monomials that are greater than $mn$ or $nm$

Hence all (monomials of $[sb3]$) are greater than $mn$ which is the form you required.

One can say a little bit more From property $\mathbf{(LB)}$, and the fact that $[B(m),B(n)]$ is a multihomogeneous Lie polynomial, one has ($\underline{w}$ being the commutative image of $w$) $$[B(m),B(n)]=B(mn) + \sum_{mn<l\atop l\ \mathrm{Lyndon};\ \underline{l}=\underline{mn}} \gamma_{m,n}^{(l)}B(l)$$
the coefficients $\gamma_{m,n}^{(l)}$ are the structure constants of the free Lie algebra w.r.t. the Lyndon-Sirsov basis (they are integers, universal, i.e. characteristic free) and, up to my knowledge, their combinatorics is widely unknown.

As far as I can see, your statement is equivalent to Lemma 3.5 in http://arxiv.org/pdf/0804.1254.pdf .

• Yes, equivalent up to a reversal (just to clarify in order that readers be not misled). In the statement, a Lyndon word is the (strict) minimum of a (primitive) conjugacy class as in Reutenauer's book Free Lie algebras (which I believe has become standard convention now) whereas in the paper you cite (Lemma 3.5), a Lyndon-Sirsov word is the (strict) maximum of a (primitive) conjugacy class as was used in the former "école de Lille" around Gérard Jacob. Jun 8 '15 at 7:02
• See, for instance <a href="sciencedirect.com/science/article/pii/S0012365X99001247" target="_blank">sciencedirect.com/s<wbr>cience/article/pii/…>. It seems that the question of structure constants is still widely open. Jun 8 '15 at 7:11
• This, of course, does not withdraw any parcel of the merit of Sirsov who was the first to point out these words (rediscovered as explained in Bokut's paper independently by Fox and Lyndon). Jun 8 '15 at 7:22
• @DuchampGérardH.E. Yes, I don't think much understood about structure constants. I feel however that the OP was asking a question about a sort of triangularity property with some structure constants, which is indeed very easy. Jun 8 '15 at 7:41
• OK, if it is this, any of us can answer Jun 8 '15 at 8:06