MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 details and observations are at

share|cite|improve this question
For comparison, I wonder if you could remind us the total number of Lyndon words in each of these spaces? I assume it's growing much faster than the sequence you computed, but I could imagine that BCH essentially saturates some natural subspace of of FL(x,y), say the subspace with some obvious symmetry, and that the pattern is exactly the pattern of dimensions of those spaces. – Theo Johnson-Freyd Dec 12 '12 at 6:03
Ah, I see that you answer (at least) some of my question in the linked pdf, which I have only just started to read. – Theo Johnson-Freyd Dec 12 '12 at 6:04
Is it really periodic or something more like a sturmian sequence? Namely, if one writes "A" whenever the even and odd guys coincide, and then "B" whenever they don't, then one gets a (semi-)infinite word in two letters "A" and "B". Is this sequence ultimately periodic or sturmian (the later meaning that it is of minimal complexity among non-periodic words)? – DamienC Dec 12 '12 at 8:23
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. – Hugh Thomas Dec 12 '12 at 10:11
I tool a liberty to add this sequence to the OEIS as – Max Alekseyev Dec 16 '12 at 19:11
up vote 4 down vote accepted

This pattern of vanishing coefficients in the expansion of the Baker-Campbell-Hausdorff formula in the basis of Lyndon words is explained in section IV.C of the article An efficient algorithm for computing the Baker–Campbell–Hausdorff series and some of its applications of Fernando Casas and Ander Murua.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.