The following claim can be found, without proof, in A Formula for the Determinant of a Sum of Matrices by Reutenauer and Schützenberger, (I am paraphrasing):

In the algebra of noncommutative power series with indeterminates from a set $A$ with integer coefficients, we have, $$ (1 - a_1 - \ldots - a_k)^{-1} = \prod_{l} (1 - l)^{-1}, $$ where the product is taken over all Lyndon words in decreasing order.

Here, $A$ is a finite totally ordered set $A=\{a_1, \ldots, a_k\}$ satisfying $a_1 < \ldots < a_k$, whereas $l$ stands for a Lyndon word, and the product is taken over all Lyndon words. In particular, the right-hand side is an infinite product.

My question is: how can one prove this fact?

It is easy to see that when $A$ is a singleton set $A = \{a_1\}$, the fact above reduces to the geometric series. However, I do not see how to generalize the geometric series to multiple variables.

Any help is appreciated!

  • $\begingroup$ Perhaps I don't understand, but isn't this just the same fact as the uniqueness of the standard factorisation of a string as a product of Lyndon words? $\endgroup$ Jul 14, 2021 at 6:58
  • $\begingroup$ In the sources I have found, these two facts are claimed to be equivalent. However, I do not see how the uniqueness of Lyndon-factorizations implies the equation above. $\endgroup$
    – Leo
    Jul 14, 2021 at 19:42

1 Answer 1


[Let me try it as an answer: if it's shot down I will remove it.]

The terms of the (formal) expansion of the LHS are exactly the words on the (ordered) alphabet $A$.

The terms of the (formal) product/expansion of the RHS are exactly the concatenations of Lyndon words in non-increasing order.

By the Chen–Fox–Lyndon theorem (see Wikipedia) each term on the LHS corresponds to precisely one term on the RHS.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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