Pensieve header: A BCH-Lyndon Question; also at http://mathoverflow.net/questions/116137/the-bch-series-in-terms-of-lyndon-words.

The Question

Recently I did some explicit computations that involved the BCH series, log((e^x)(e^y)). Here x and y are non-commuting variables, and the BCH series lives in the graded completion FL(x,y) of the free Lie algebra generated by x and y.

Mostly by chance I found that when BCH is written in the Lyndon basis of FL(x,y), the number of Lyndon words that occur in its degree n piece is {2, 1, 2, 1, 6, 5, 18, 17, 55, 55, 186, 185, 630, 629, 2181, 2181, 7710, 7709, 27594, 27593, 99857, 99857}, for n running from 1 to 22.

There is an obvious pattern in this sequence - it seems that the odd-numbered terms are almost equal to the even-numbered terms that follow them, with a decline of one in 2/3 of the times, and with precise equality in the remaining 1/3 of the times. I have no idea why this is so. Perhaps you do?

Why care? The truth is that I’m curious but I don’t care much; I just stumbled upon this by chance. Yet Lyndon words are a very effective tool for computations in free Lie algebras, and the BCH formula appears in many of these computations. The fact that there is some unexpected symmetry in the Lyndon word description of BCH suggests that BCH contains less information than one might think, possibly leading to some computational advantage. Though in (my) reality, the computational bottlenecks are anyway elsewhere.

Some further observations:

The number of Lyndon words of length n, for n between 1 and 22, is {2, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, 630, 1161, 2182, 4080, 7710, 14532, 27594, 52377, 99858, 190557}. For the even n’s, this is much more than the number of Lyndon words that occur within BCH. For the odd n’s, this is mostly equal to the number of Lyndons in BCH, with exceptions at n=9,15,21. In those cases the BCH formula is missing exactly one Lyndon word. These missing words are “xxxxxyxxy”, “xxxxxxxxxyxxxxy”, and “xxxxxxxxxxxxxyxxxxxxy”.

The actual BCH formula, written in Lyndon words, is displayed below to degree 8. Further down is the list of Lyndon words that occur / do not occur in the BCH formula to degree 12.

Initialization

This notebook as well as the file “FreeLie.m” are available at http://drorbn.net/AcademicPensieve/2012-12/.

SetDirectory["C:\\drorbn\\AcademicPensieve\\2012-12"];
<< FreeLie.m;
BCH[n_Integer] := BCH[⟨"x"⟩,⟨"y"⟩][n];
BCHWords[n_Integer] := Cases[BCH[n], _LW, Infinity];
AllLyndonWords[n_Integer] := AllLyndonWords[n, {"x", "y"}];

BCH in Lyndon words

Table[BCH[n], {n, 8}]

Some Counts

Length /@ BCHWords /@ Range[21]

(The degree 22 computation is time consuming and was done elsewhere. Comes out 99857)

Length /@ AllLyndonWords /@ Range[22]

The Lyndon words in BCH

Do[
Print[{n, Length[BCHWords[n]],BCHWords[n]}];
If[EvenQ[n],Print["————"]],
{n,12}
]

On the MathOverflow question site, Hugh Thomas observed:

It looks to me (from the data in the linked pdf) like there are two different perhaps not-so-related things that are happening: at n odd, BCH gets all possible Lyndon words except one of them when n=6k+3 (k>0), in which case it misses (x^(4k+1))(yx^(2k))y, and at n=2k, the Lyndon words that appear in BCH are exactly those obtainable from the Lyndon words of length 2k-1 by prepending x, except that (x^(2k-1))y does not appear. I have no explanations, though.

He is right:

SymmetricDifference[A_List, B_List] := {
Complement[A,B], Complement[B,A]
};
Table[
SymmetricDifference[
b[⟨"x"⟩, #]& /@ BCHWords[2n-1],
BCHWords[2n]
],
{n,2,10}
] // ColumnForm

The Lyndon words not in BCH

Odd n:

Table[{n,Complement[AllLyndonWords[n], BCHWords[n]]}, {n, 1, 21, 2}]

TopBracketForm[{⟨"xxxxxyxxy"⟩, ⟨"xxxxxxxxxyxxxxy"⟩, ⟨"xxxxxxxxxxxxxyxxxxxxy"⟩}]

Even n:

Table[{n,Complement[AllLyndonWords[n], BCHWords[n]]}, {n, 2, 12, 2}]

Table[{n,Complement[AllLyndonWords[n], BCHWords[n]]}, {n, 2, 10, 2}] // TopBracketForm