Generalization of the geometric series to multiple variables using Lyndon words

129 Views Asked by At

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!

1

There are 1 best solutions below

0
On

[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.