Discrete Mathematics & Theoretical Computer Science, Vol 12, No 3 (2010)

Font Size:  Small  Medium  Large

On the support of the free Lie algebra: the Schützenberger problems

Ioannis Michos


M.-P. Schützenberger asked to determine the support of the free Lie algebra Lm(A) on a finite alphabet A over the ring ℤm of integers &bmod;m and all pairs of twin and anti-twin words, i.e., words that appear with equal (resp. opposite) coefficients in each Lie polynomial. We characterize the complement of the support of Lm(A) in A* as the set of all words w such that m divides all the coefficients appearing in the monomials of l*(w), where l* is the adjoint endomorphism of the left normed Lie bracketing l of the free Lie ring. Calculating l*(w) via the shuffle product, we recover the well known result of Duchamp and Thibon (Discrete Math. 76 (1989) 123-132) for the support of the free Lie ring in a much more natural way. We conjecture that two words u and v of common length n, which lie in the support of the free Lie ring, are twin (resp. anti-twin) if and only if either u = v or n is odd and u = v (resp. if n is even and u = v), where v denotes the reversal of v and we prove that it suffices to show this for a two-lettered alphabet. These problems can be rephrased, for words of length n, in terms of the action of the Dynkin operator ln on λ-tabloids, where λ is a partition of n. Representing a word w in two letters by the subset I of [n] = { 1, 2, …, n } that consists of all positions that one of the letters occurs in w, the computation of l*(w) leads us to the notion of the Pascal descent polynomial pn(I), a particular commutative multi-linear polynomial which is equal to the signed binomial coefficient when |I| = 1. We provide a recursion formula for pn(I) and show that if m ∤ Σi ∈I (-1)i-1 n-1, i-1, then w lies in the support of Lm(A).

Full Text: PDF PostScript