I was trying to understand the proof of the Witt dimension formula for free Lie algebras. I was basically following this proof.

(I'm not posting the complete proof but just the piece where I'm currently stuck on.)

How do we prove the Witt dimension formula? Write $\ell_n = \dim L_n$. In each homogeneous subspace $L_n$ of the free Lie algebra choose an ordered basis $\{ f_{n1}, \dotsc, f_{n \ell_n} \}$. Put these finite bases together into an infinite ordered basis of $L$: $$f_{11}, \dotsc, f_{1 \ell_1}, f_{21}, \dotsc, f_{2 \ell_2}, f_{31}, \dotsc, f_{3 \ell_3}, \dotsc$$ For simplicity write this last basis as $$g_1, g_2, g_3, \dotsc, g_i, \dotsc$$ The PBW Theorem (after Poincaré, Birkhof and Witt) states that a basis for $A$ consists of all products of the form $$\tag{1} g_{i_1} g_{i_2} \dotsm g_{i_k} \qquad (i_1 \leq i_2 \leq \dotsb \leq i_k).$$ Now we need to do some combinatorics. There are $\ell_d$ Lie polynomials $g_i$ of degree $d$. Each $g_i$ contributes degree $d$ to the total degree of the associative word in $(1)$. But each $g_i$ may occur any number $k$ of times (consecutively) in $(1)$. The generating function for the contribution of these $k$ elements of degree $d$ to the total degree of $(1)$ is $$1 + x^d + x^{2d} + \dotsb + x^{kd} + \dotsb = \frac{1}{1-x^d} \cdotp$$

(Original image here.)

But I do not understand the meaning of the last 4 lines. Why isn't the total contribution to the degree of $(1)$ just $dk$? Where that generating function comes from? What is $x$ in that formula?

Unfortunately this seems to be the most clear proof of the Witt's formula I've found.

• I didn't ask for the meaning of the words. I asked to understand them in the context of the proof. For example, how to deduce the that generating formula from the above lines? Clearly $x$ is a variable, but why is there? What are the values it can assume? – W4cc0 Aug 23 '18 at 17:07
• See here; the coefficients (not the variable) give the numbers you are looking for, in this case $p(n)$. One can do the same for Witt's formula (see wiki proof for necklace polynomials). – Dietrich Burde Aug 23 '18 at 19:04
• There are many references for a proof of Witt's formula here. Most of them are really easy to understand. The PBW theorem itself might be more difficult, which you are using. – Dietrich Burde Aug 23 '18 at 19:10