On the S_n-module structure of the noncommutative harmonics
ON THE Sn-MODULE STRUCTURE OF THE
NONCOMMUTATIVE HARMONICS.
EMMANUEL BRIAND, MERCEDES ROSAS, AND MIKE ZABROCKI
Abstract. Using a noncommutative analog of Chevalley’s decomposi-
tion of polynomials into symmetric polynomials times coinvariants due
to Bergeron, Reutenauer, Rosas, and Zabrocki we compute the graded
Frobenius characteristic for their two sets of noncommutative harmon-
ics with respect to the left action of the symmetric group (acting on
variables). We use these results to derive the Frobenius series for the
enveloping algebra of the derived free Lie algebra in n variables.
In honor of Manfred Schocker (1970-2006). The authors would also like
to acknowledge the contributions that he made to this paper.
1. Introduction
A central result of Claude Chevalley [3] decomposes the ring of polyno-
mials in n variables (as graded representation of the symmetric group Sn)
as the tensor product of the symmetric polynomials times the coinvariants
of Sn (i.e., polynomials modulo symmetric polynomials with no constant
term).
The coinvariants of the symmetric group can also be defined as its har-
monics (the polynomials annhilated by all symmetric polynomial differen-
tial operators with no constant term). They admit as a basis the famous
Schubert polynomials of Schubert calculus, that play an important role in
algebraic combinatorics, see for instance [6].
The space of invariant polynomials in noncommutative variables was in-
troduced in 1936 by Wolf [16] where she found a noncommutative version of
the fundamental theorem of symmetric functions. This space has been stud-
ied from a modern perspective in [13, 1, 2]. On the other hand, two sets of
noncommutative harmonics for the symmetric group were introduced in [1]
that translated into two noncommutative analogues of Chevalley decompo-
sition for the ring of polynomials in noncommuting variables. The question
of decomposing as Sn–modules both kinds of noncommutative harmonics
was left open. This is the starting point in our investigations.
We begin the present work with the computation of the graded Frobenius
characteristic of noncommutative harmonics. We then use these calculations
Expanded version of a paper to appear in Journal of Combinatorial theory, series A,
http://www.elsevier.com/locate/jcta.
Emmanuel Briand is supported by a contract Juan de la Cierva, MEC. Mercedes Rosas
is supported by a contract Ramón y Cajal, MEC. Mike Zabrocki is supported by NSERC.
http://arxiv.org/abs/0704.1101v2
2 EMMANUEL BRIAND, MERCEDES ROSAS, AND MIKE ZABROCKI
to derive the Frobenius series for the enveloping algebra of the derived free
Lie algebra in n variables, A′n. This last computation is achieved by using
the existence of an isomorphism of GLn(Q)–modules between the space of
polynomials in noncommutative variables, and the tensor product of the
space of commuting polynomials with A′n. Such an isomorphism is presented
explicitly in the last section.
We conclude this introduction with some basic definitions and results
that we will be using in the following sections. Let Sn denote the sym-
metric group in n letters. Denote by Q[Xn] = Q[x1, x2, . . . , xn] the space
of polynomials in n commuting variables and by Q〈Xn〉 = Q〈x1, x2, . . . , xn〉
the space of polynomials in n noncommutative variables.
The space of symmetric polynomials in n variables will be denoted by
Symn and the space of noncommutative polynomials which are invariant
under the canonical action of the symmetric group Sn will be denoted by
NCSymn.
Given any polynomial f(Xn) ∈ Q[Xn], the notation f(∂Xn) represents
the polynomial turned into an operator with each of the variables replaced
by its corresponding derivative operator. Analogous notation will also hold
for f(Xn) ∈ Q〈Xn〉 except that there are two types of differential operators
acting on words in noncommutative variables. The first is the Hausdorff
derivative, ∂x, whose action on a word w is defined to be the sum of the
subwords of w with an occurrence of the letter x deleted. The second deriv-
ative is the twisted derivative, dx, which is defined on w to be w
′ if w = xw′,
and 0 otherwise. Both derivations are extended to polynomials by linearity.
It is interesting to remark (as does Lenormand in [8], section Séries comme
opérateurs) that these two operations are dual to the shuffle and concate-
nation products respectively, with respect to a scalar product where the
noncommutative monomials are self dual. That is,
〈∂xf, g〉 = 〈f, x⊔⊔g〉, and
〈dxf, g〉 = 〈f, xg〉.
Following [1], we introduce the following two sets of noncommutative ana-
logues of the harmonic polynomials. The canonical action of the symmetric
group endow them with the structure of Sn–modules.
MHarn = {f ∈ Q〈Xn〉 : p(∂Xn)f(Xn) = 0 for all p ∈ Mn}
NCHarn = {f ∈ Q〈Xn〉 : p(dXn)f(Xn) = 0 for all p ∈ Mn}
where Mn = {p ∈ NCSymn with p(0) = 0}.
We are now ready to state the two decompositions of Q〈Xn〉 as the ten-
sor product (over Q) of its invariants times its coinvariants that we have
described.
Proposition 1 ([1], Theorems 6.8 and 8.8). As graded Sn–modules,
Q〈Xn〉 ≃ MHarn ⊗ Symn,
Q〈Xn〉 ≃ NCHarn ⊗NCSymn.
NONCOMMUTATIVE HARMONICS 3
2. The Frobenius characteristic of noncommutative harmonics
In this section we compute the Frobenius characteristic of both kinds
of noncommutative harmonics. This section is based of the observation
that the graded Frobenius series for each of the Sn–modules appearing in
Proposition 1 is either known or can be deduced from the existence of the
isomorphisms described there.
The expressions for Frobenius images and characters will require a little
use of symmetric function notation and identities. We will follow Macdonald
[9] for the notation of the sλ Schur, hλ homogeneous, eλ elementary and pλ
power sums bases for the ring of symmetric functions Sym, that we identify
with Q[p1, p2, p3, . . .]. For convenience we will make use of some plethystic
notation.
For a symmetric function f , f [X] represents the symmetric function eval-
uated at an unspecified (possibly infinite) alphabet X. Then, f [X(1 − q)]
is the image of f under the algebra automorphism sending the power sum
symmetric function pk to (1 − q
k)pk[X]. Similarly, f
is the image
of the symmetric function f under the inverse automorphism (sending the
power sum pk to pk/(1− q
In our calculations, we use the Kronecker product ⊙ of symmetric func-
tions. This operation on symmetric functions corresponds, under the Frobe-
nius map, to the inner tensor product of representations of the symmetric
group (tensor product of representations with the diagonal action on the ten-
sors). It can also be defined directly on symmetric functions by the equation
pλ⊙ pµ = δλ,µ
i ni(λ)!i
ni(λ)
pλ where ni(λ) is the number of parts of size
i in λ, and then extended by bilinearity.
We introduce the notations
(q; q)k = (1− q)(1− q
2) · · · (1− qk),
{q; q}k = (1− q)(1− 2q) · · · (1− k q).
Then qd/{q; q}d is the generating function for the set partitions with length
d and qd/(q; q)d is the generating function for partitions with length d, [15].
Finally, since Symn and NCSymn are made of graded copies of the trivial
Sn-module we conclude that
FrobSn(NCSymn) = hn [X]
{q, q}d
FrobSn(Symn) = hn [X]
(q; q)n
= hn [X]
(q; q)d
In the following lemma we compute the graded Frobenius characteristic
for the module Q〈Xn〉.
4 EMMANUEL BRIAND, MERCEDES ROSAS, AND MIKE ZABROCKI
Lemma 2 (The Frobenius characteristic of Q〈Xn〉).
FrobSn(Q〈Xn〉) =
{q, q}d
h(n−d,1d)[X].
Proof. For each monomial xi1 · · · xir , we define its type ∇(xi1 · · · xir) to be
the set partition of [r] = {1, 2, . . . , r} such that a and b are in the same part
of the set partition if and only if ia = ib in the monomial. For a set partition
A with at most n parts, we will let MA equal the Sn submodule of Q〈Xn〉
spanned by all monomials of type A. As Sn–module,
Q〈Xn〉 ≃
A : ℓ(A)=d
where the second direct sum is taken over all set partitions A with d parts.
Fix a set partition A, and let d be the number of parts of A, and x~i =
xi1xi2 ...xir be the smallest monomial in lex order in M
A. It involves only
the variables x1, x2, . . . , xd. The representation M
A is the representation of
Sn induced by the action of the subgroup Sd×S
1 ≃ Sd on the subspace
Q[Sd] · x~i. The representation Q[Sd] · x~i of Sd is isomorphic to the regular
representation. We use the rule for a representation R of Sd induced to Sn,
FrobSn(R ↑
) = hn−d[X]FrobSd(R),
and conclude that the Frobenius characteristic of MA is h(n−d,1d)[X]. Hence
the graded Frobenius characteristic of Q〈Xn〉 is
FrobSn(Q〈Xn〉) =
A:ℓ(A)=d
q|A|h(n−d,1d)[X] =
{q, q}d
h(n−d,1d)[X].
We are now able to compute the Frobenius characteristic for MHarn and
NCHarn.
Theorem 3 (The Frobenius characteristic of the noncommutative harmon-
ics).
FrobSn(MHarn) = (q; q)n
{q, q}d
h(n−d,1d)[X]
FrobSn(NCHarn) =
{q, q}d
{q, q}d
h(n−d,1d)[X].
Proof. This follows since FrobSn(MHarn ⊗ Symn) = FrobSn(MHarn) ⊙
FrobSn(Symn). Since hn[X] is the unity for the Kronecker product on
symmetric functions of degree n, and since FrobSn(Symn) = hn[X]/(q; q)n,
we conclude that FrobSn(MHarn)/(q; q)n = FrobSn(Q〈Xn〉). We can now
solve for FrobSn(MHarn).
NONCOMMUTATIVE HARMONICS 5
A similar argument demonstrates the formula for FrobSn(NCHarn). We
have from Proposition 1 and Lemma 2,
{q, q}d
h(n−d,1d)[X] = FrobSn(Q〈Xn〉)
= FrobSn(NCHarn)⊙FrobSn(NCSymn)
{q, q}d
hn[X] ⊙FrobSn(NCHarn)
{q, q}d
FrobSn(NCHarn).
From this equation we can solve for FrobSn(NCHarn). �
As a corollary, we obtain the generating functions for the graded dimen-
sions of these spaces.
Corollary 4 (The Hilbert series of the noncommutative harmonics).
dimq(MHarn) =
(q; q)n
1− nq
dimq(NCHarn) =
(1− nq)
{q,q}d
Proof. After Theorem 3,
FrobSn(MHarn) = (q; q)n FrobSn(Q〈Xn〉)
FrobSn(NCHarn) =
{q, q}d
FrobSn(Q〈Xn〉)
This implies
dimq(MHarn) = (q; q)n dimq(Q〈Xn〉)
dimq(NCHarn) =
{q, q}d
dimq(Q〈Xn〉)
since the Hilbert series of a graded Sn–module is obtained by coefficient
extraction from the graded Frobenius characteristic (of the coefficient of
p(1n)[X]/n! in the expansion in power sum symmetric functions). Last, the
Hilbert series of Q〈Xn〉 is
The graded dimensions of MHarn for 2 ≤ n ≤ 5 are listed in [14] as
sequences A122391 through A122394. The sequences of graded dimensions
of NCHarn for 3 ≤ n ≤ 8 are listed in [14] as sequences A122367 through
A122372.
6 EMMANUEL BRIAND, MERCEDES ROSAS, AND MIKE ZABROCKI
3. Non–commutative harmonics and the enveloping algebra of
the derived free Lie algebra
Let Ln be the canonical realization of the free Lie algebra inside the ring
of polynomials in noncommuting variables Q〈Xn〉. More precisely, Ln is
the linear span of the minimal set of polynomials in Q〈Xn〉 that includes
Q and the variables Xn, and is closed under the bracket operation [x, y] =
xy − yx. Let L′n = [Ln,Ln] be the derived free Lie algebra. Remark that
Ln = L
n ⊕ QXn, where QXn denotes the space of linear polynomials. The
enveloping algebra A′n of Ln can be realized as a subalgebra of Q〈Xn〉 as
follows (see [12] 1.6.5):
A′n =
ker ∂x.
More explicitly, A′n is the subalgebra of Q〈Xn〉 generated by all the brackets
under concatenation.
In [1] it was established that there is an isomorphism of vector spaces
between MHarn and A
n ⊗ Hn. In this section we will show the following
result.
Theorem 5. As Sn–modules,
MHarn ≃ A
n ⊗Hn.
The proposition will be established by comparing the Frobenius image of
MHarn (known from Theorem 3) to FrobSn(A
n ⊗ Hn), which is equal to
FrobSn(A
n)⊙FrobSn(Hn). We will determine FrobSn(A
n) in Theorem 8
below. An intermediate step will make use the following Theorem due to V.
Drensky.
Proposition 6 (Drensky, [5] Theorem 2.6). As GLn(Q)–modules (and con-
sequently as Sn–modules),
Q〈Xn〉 ≃ Q[Xn]⊗A
Drensky proved Proposition 6 by exhibiting an explicit isomorphism be-
tween these two representations. We will look at it in the next section. For
now, we will provide a non–constructive proof of the theorem. Before, we
need to introduce some notation.
It is known that Q〈Xn〉 is the universal enveloping algebra (u.e.a) of the
free Lie algebra, Ln. Using the Poincaré-Birkhoff-Witt theorem, a linear
basis for Q〈Xn〉 is given by decreasing products of elements of Ln. Since
we can choose an ordering of the elements of Ln so that the space of linear
polynomials is smallest and decreasing products of linear polynomials are
isomorphic to Q[Xn] (as a vector space), we note that as vector spaces
Q〈Xn〉 = u.e.a.(Ln) = u.e.a(QXn ⊕ L
n) ≃ Q[Xn]⊗A
To distinguish between the commutative elements of Q[Xn] and the non-
commutative words of Q〈Xn〉, we will place a dot over the variables (as in
ẋi) to indicate the commutative variables.
NONCOMMUTATIVE HARMONICS 7
Let [n] = {1, 2, . . . , n} and let [n]r denote the words of length r in the
alphabet of the numbers 1, 2, . . . , n. A word w ∈ [n]r is called a Lyndon word
if w < wkwk+1 · · ·wr for all 2 ≤ k ≤ r where< represents lexicographic order
on words.
Every word w ∈ [n]r is equal to a unique product w = ℓ1ℓ2 · · · ℓk such
that ℓ1 ≥ ℓ2 ≥ · · · ≥ ℓk and each ℓi is Lyndon (e.g. Corollary 4.4 of [12]).
Let ℓ be a Lyndon word of length greater than 1. We say that ℓ = uv
is the standard factorization of ℓ if v is the smallest nontrivial suffix in
lexicographic order. It follows that u and v are Lyndon words and u < v.
For a Lyndon word ℓ, if ℓ is a single letter a then define Pa = xa ∈ Q〈Xn〉.
If ℓ = uv is the standard factorization of ℓ, then Pℓ = [Pu, Pv ]. For any
w ∈ [n]r with Lyndon decomposition w = ℓ1ℓ2 · · · ℓk, define
Pw = Pℓ1Pℓ2 · · ·Pℓk .
The set {Pw}w∈[n]r forms a basis for the noncommutative polynomials of
degree r ([12], Theorem 5.1). The elements Pw with Lyndon decomposition
w = ℓ1ℓ2 · · · ℓk such that each Lyndon factor has degree at least 2 are a basis
of A′n.
Proof. To prove that Q〈Xn〉 and Q[Xn] ⊗ A
n are isomorphic as GLn(Q)–
modules, we use the fact that two polynomial GLn(Q)–modules with the
same character are isomorphic (see for instance the notes by Kraft and
Procesi, [7]). The character of a GLn(Q)–module is the trace of the action
of the diagonal matrix diag(a1, a2, . . . , an).
A basis for Q[Xn] ⊗A
n are the elements ẋ
α ⊗ Pℓ1 · · ·Pℓk with ℓ1 ≥ ℓ2 ≥
· · · ≥ ℓk and |ℓi| ≥ 2. The action of the diagonal matrix diag(a1, a2, . . . , an)
on this basis element is the same as the action on the noncommutative
polynomial xα11 x
2 · · · x
n Pℓ1Pℓ2 · · ·Pℓk (in both cases: multiplication by
α1+m1
α2+m2
2 · · · a
αn+mn
n where mi is the number of occurrences of i in the
word ℓ1ℓ2 · · · ℓk). By the Poincaré-Birkhoff-Witt theorem, these polynomials
form a basis for Q 〈Xn〉, hence the trace of the action of diag(a1, a2, . . . , an)
acting on Q 〈Xn〉 and Q[Xn]⊗A
n are equal. Since their characters are equal,
we conclude that they are isomorphic as GLn(Q) modules. �
The GLn(Q)–character of Q[Xn] is
, and the GLn(Q)–character
of Q〈Xn〉 is
1−(a1+a2+···+an)
. Therefore, the existence of a GLn(Q)-module
isomorphism between Q〈Xn〉 and Q[Xn]⊗A
n implies the following result.
Corollary 7 (The GLn(Q)–character of A
charGLn(Q)(A
n)(a1, a2, · · · , an) =
(1− a1) · · · (1− an)
1− (a1 + a2 + · · · + an)
(−1)ie(i,1k−i)(a1, a2, . . . , an).
8 EMMANUEL BRIAND, MERCEDES ROSAS, AND MIKE ZABROCKI
Moreover this last sum is equal to
sshape(T )(a1, a2, . . . , an)
where the sum is over all standard tableaux T such that the smallest integer
which does not appear in the first column of T is odd.
By Schur-Weyl duality, the above formula also describes the decompo-
sition of the subspace of multilinear polynomials (i.e. with distinct occur-
rences of the variables) of A′n. That is, if n is the number of variables, the the
multilinear polynomials of degree n will be an Sn-module with Frobenius
image equal to
i=2(−1)
ie(i,1n−i)[X]. This decomposition was considered
in the papers [4], [10], [11] where an expression was given degree by degree
up to n = 7. The expansion of this formula in the Schur basis provided in
the Theorem agrees with the computations in those papers.
We can derive a formula for the Frobenius characteristic of A′ by using a
similar technique.
Theorem 8 (The Frobenius characteristic of A′n).
FrobSn(A
{q; q}d
h(n−d,1d)[X(1− q)].
Proof. For any symmetric function f [X] of degree n, we have that
f [X]⊙ hn
In particular, since FrobSn(Q[Xn]) = hn
, we conclude that
FrobSn(Q〈Xn〉) = FrobSn(A
n ⊗Q[Xn])
= FrobSn(A
n)⊙ hn
= FrobSn(A
This implies that if we make the plethystic substitution X→X(1 − q) into
both sides of this equation and using Lemma 2 we arrive at the stated
formula. �
We can now prove Theorem 5.
Proof. From Theorem 3 we know the Frobenius image of MHarn, we com-
pare this to
FrobSn(A
n ⊗Hn) = FrobSn(A
n)⊙FrobSn(Hn),
{q; q}d
h(n−d,1d)[X(1 − q)]⊙ hn
(q; q)n
= (q; q)n
{q; q}d
h(n−d,1d)[X]
= FrobSn(MHarn).
NONCOMMUTATIVE HARMONICS 9
Since the two Sn–modules have the same Frobenius image, we conclude that
they must be isomorphic. �
4. An explicit isomorphism between Q〈Xn〉 and Q[Xn]⊗A
Let V be a finite–dimensional vector space over Q. Let S(V ) and T (V ) be
its symmetric algebra and tensor algebra respectively. There exists a unique
embedding ϕ of GL(V )–modules of S(V ) into T (V ) such that
ϕ(v1v2 · · · vr) =
vσ(1) ⊗ vσ(2) ⊗ · · · ⊗ vσ(r)
for all r ≥ 0, v1, v2, . . . , vr ∈ V.
Its image is the subspace of the symmetric tensors. In the case V =
i=1Qxi, we have S(V ) = Q[Xn] and T (V ) = Q〈Xn〉. Then the embed-
ding ϕ and the inclusion A′n ⊂ Q〈Xn〉 induce a map of GLn(Q)–modules
Φ : Q[Xn] ⊗ A
n −→ Q〈Xn〉 characterized by Φ(f ⊗ a) = ϕ(f)a for all
f ∈ Q[Xn] and all a ∈ A
n. Then,
Proposition 9 (Drensky, [5] Theorem 2.6). The map Φ is a GLn(Q) equi-
variant isomorphism from Q[Xn]⊗A
n to Q〈Xn〉.
Indeed, Drensky showed that given an arbitrary homogeneous basis of G
of A′n, the elements Φ(m⊗ g) for m monomial and g ∈ G, are a basis of A
([5] Lemma 2.4). We refine Drensky’s proof by considering for G the bracket
basis {Pw}w∈[n]r of A
n (introduced before the proof of Proposition 6) and
the shuffle basis (see below) to realize Q[Xn] in Q〈Xn〉. We show that the
elements Φ(m⊗g) form a basis Q〈Xn〉 (the hybrid basis) that is triangularly
related and expands positively in the bracket basis of Q〈Xn〉 (Theorem 10
below).
We follow the book of Reutenauer [12] for the classical definitions and
results used in this section. The bracket basis Pw has been introduced in
the previous section (before the proof of Proposition 6). Before presenting
the hybrid basis we introduce another classical basis of Q〈Xn〉: the shuffle
basis.
The shuffle basis of Q〈Xn〉. Consider two monomials, xi1xi2 · · · xir and
xj1xj2 · · · xjr′ in Q〈Xn〉. For a subset
S = {s1, s2, . . . , sr} ⊆ [r + r
and the complement subset T = {t1, t2, . . . , tr′} = [r + r
′]\S, we let
xi1xi2 · · · xir⊔⊔Sxj1xj2 · · · xjr′ := w
be the unique monomial in Q〈Xn〉 of length r+r
′ such that ws1ws2 · · ·wsr =
xi1xi2 · · · xir and wt1wt2 · · ·wtr′ = xj1xj2 · · · xjr′ .
10 EMMANUEL BRIAND, MERCEDES ROSAS, AND MIKE ZABROCKI
The shuffle of any two monomials is defined as
u⊔⊔v =
S⊆[|u|+|v|]
|S|=|u|
u⊔⊔Sv.
This shuffle of monomials is then extended to a bilinear operation on any
two elements of Q〈Xn〉 The shuffle product is a commutative and associative
operation on Q〈Xn〉.
Let w be a word in [n]r and let w = ℓ
2 · · · ℓ
be the factorization of w
into decreasing products of Lyndon words ℓ1 > ℓ2 > · · · > ℓk. For a Lyndon
word ℓ = i1i2 · · · ir, let Sℓ be the corresponding monomial in Q〈Xn〉, that is
Sℓ = xi1xi2 · · · xir . If w is not a single Lyndon word then define
i1!i2! · · · ik!
⊔⊔ · · · ⊔⊔S
The set {Sw}w∈[n]r forms a basis for the noncommutative polynomials of
degree r ([12], Corollary 5.5).
It is interesting to note that the bracket basis Pw and the shuffle basis
Sw are dual with respect to the scalar product where the noncommutative
monomials are self-dual.
The hybrid basis of Q〈Xn〉. We are now ready to introduce the hybrid
basis.
Given a word w ∈ [n]r with a factorization into decreasing products of
Lyndon words w = ℓ
2 · · · ℓ
, then let ℓj1 , ℓj2 , · · · , ℓjr be the Lyndon words
of length 1 in this decomposition and set
M(w) = x
⊔⊔ij1
⊔⊔ij2
⊔⊔ · · · ⊔⊔x
⊔⊔ijr
= ij1 !ij2 ! · · · ijr !S
Observe that M(w) is the image under the embedding ϕ of the monomial
X(w) = ẋ
· · · ẋ
. For all of the remaining Lyndon words ℓa1 , ℓa2 ,
. . . , ℓak−r with length greater than 1 we define the Lie portion of the word
to be L(w) = P
iak−r
. We will define the hybrid elements to be
Hw := M(w)L(w) = Φ(X(w) ⊗ L(w)).
The result of this section is:
Theorem 10. The noncommutative polynomials Hw are triangularly related
to and expand positively in the Pu basis. Precisely, for w of length r,
Hw = r!Pw + terms cuPu with u lexicographically smaller than w.
As a consequence, the set {Hw}w∈[n]r is a basis for the noncommutative
polynomials of Q〈Xn〉 of degree r.
We require a few facts about Lyndon words and the lexicographic ordering
which can be found in [12].
(1) If u and v are Lyndon words and u < v then uv is a Lyndon word.
([12], (5.1.2))
NONCOMMUTATIVE HARMONICS 11
(2) If u < v and u is not a prefix of v, then ux < vy for all words x, y.
([12], Lemma 5.2.(i))
(3) If w = ℓ1ℓ2 · · · ℓk with ℓ1 ≥ ℓ2 ≥ · · · ≥ ℓk then ℓk is the smallest
(with respect to the > order) nontrivial suffix of w. ([12], Lemma
7.14)
(4) If ℓ′ < ℓ, are both Lyndon words, then ℓ′ℓ < ℓℓ′ (follows from (1)). As
a consequence, for ℓ1 ≥ ℓ2 ≥ · · · ≥ ℓk, ℓ1ℓ2 · · · ℓk ≥ ℓσ(1)ℓσ(2) · · · ℓσ(k)
for any permutation σ ∈ Sk with equality if and only ℓi = ℓσ(i) for
all 1 ≤ i ≤ k.
Proof. To see that (4) holds consider a weakly decreasing product of Lyndon
words ℓ1ℓ2 · · · ℓk. If id → σ
(1) → σ(2) → · · · → σ is a chain in the weak right
order then we have just shown that
ℓσ(i)(1)ℓσ(i)(1) · · · ℓσ(i)(k) ≥ ℓσ(i+1)(1)ℓσ(i+1)(2) · · · ℓσ(i+1)(k)
with equality if and only if the two Lyndon factors which were transposed are
equal. Therefore there exists a chain of words one greater than or equal to
the next with ℓ1ℓ2 · · · ℓk on one end and ℓσ(1)ℓσ(2) · · · ℓσ(k) on the other. �
Theorem 10 will be established after the following lemma.
Lemma 11. Let w be a word and ℓ1ℓ2 · · · ℓr the decomposition of w into
a decreasing product of Lyndon words. Let ℓ be a Lyndon word such that
ℓ = af1f2 · · · fk with a one of the variables, each fi a Lyndon word and
fi ≥ fi+1 and fk ≥ ℓ1. Let u = ℓ1 · · · ℓdℓℓd+1 · · · ℓr where ℓd > ℓ ≥ ℓd+1 or
d = 0 and ℓ ≥ ℓ1. Then
PℓPw = Pu
+ terms cvPv where v is lexicographically smaller than u and cv ≥ 0.
Proof. Assume that r = 1, and we have that either ℓ ≥ ℓ1 and PℓPℓ1 = Pℓℓ1
and we are done, or ℓ < ℓ1 and
PℓPℓ1 = Pℓ1Pℓ + [Pℓ, Pℓ1 ].
In this case Pℓ1Pℓ = Pℓ1ℓ. By (1) we know that ℓℓ1 is Lyndon. Moreover,
ℓℓ1 is its standard factorization (this follows from (3), since the nontrivial
suffixes of ℓℓ1 are all suffixes of f1f2 · · · fkℓ1, which is a nonincreasing product
of Lyndon words). Therefore Pℓℓ1 = [Pℓ, Pℓ1 ] and PℓPℓ1 = Pℓ1ℓ + Pℓℓ1 . By
(4), ℓℓ1 < ℓ1ℓ so the triangularity relation holds.
Now for an arbitrary r > 1 we have the same two cases. Either ℓ ≥ ℓ1
and PℓPℓ1Pℓ2 · · ·Pℓr = Pℓw, or ℓ < ℓ1 and
PℓPℓ1Pℓ2 · · ·Pℓr = Pℓ1PℓPℓ2 · · ·Pℓr + [Pℓ, Pℓ1 ]Pℓ2 · · ·Pℓr .
Our induction hypothesis holds for PℓPℓ2 · · ·Pℓr since fk ≥ ℓ1 ≥ ℓ2, hence
PℓPℓ2 · · ·Pℓr = Pu′ +
v′<u′ c
Pv′ where u
′ = ℓ2 · · · ℓdℓℓd+1 · · · ℓr. Moreover,
Pℓ1Pu′ = Pℓ1u′ = Pu since ℓ1 ≥ ℓ2 and Pℓ1Pv′ = Pℓ1v′ since ℓ1 ≥ any Lyndon
prefix of v′.
12 EMMANUEL BRIAND, MERCEDES ROSAS, AND MIKE ZABROCKI
Since [Pℓ, Pℓ1 ] = Pℓℓ1 by (3), and ℓ1 ≥ ℓ2, we have by the induction
hypothesis that Pℓℓ1Pℓ2 · · ·Pℓr = Pu′′ +
v′′<u′′ c
Pv′′ where
u′′ = ℓ2 · · · ℓd′ℓℓ1ℓd′+1 · · · ℓr
with ℓd′ > ℓℓ1 ≥ ℓd′+1. In order to justify the induction step we also need
to have that u′′ < u. This follows from (4) since u′′ is a permutation of the
factors of u and ℓ1 > ℓ and ℓ lies to the left of ℓ1 in u
We are now in a position to prove Theorem 10.
Proof. Hw is defined as the product M(w)L(w) where M(w) is a a shuffle
of monomials. It expands as M(w) =
c̃bxb with
c̃b = r! and where
each monomial in M(w) has the same number of x1s, x2s, etc. We fix one
such monomial xb that as follows by indexing its letters backwards: xb =
xikxik−1 · · · xi1 . We define inductively words w[k], . . . , w[1], w[0] as follows:
w[k] := w and w[j − 1] is the word obtained from w[j] by removing one of
its Lyndon factors of length 1 equal to xij . Remark that L(w[j]) = L(w)
for all j. Then we establish by induction on j that
xijxij−1 · · · xi1L(w) = Pw[j]
+ terms cvPv with v lexicographically smaller than w[j]
by applying Lemma 11 with xij for ℓ and w[j] for w. �
References
[1] N. Bergeron, C. Reutenauer, M. Rosas, M. Zabrocki, Invariants and Coinvariants of
the Symmetric Group in Noncommuting Variables, to appear in Canad. J. Math.
[2] N. Bergeron and M. Zabrocki, The Hopf algebra of symmetric functions in non-
commutative variables is free and cofree. Preprint, arXiv: math.CO/0509265.
[3] C. Chevalley, Invariants of finite groups generated by reflections, Amer. J. Math. 77
(1955), 778–782.
[4] V. Drensky, Lattices of varieties of associative algebras. Serdica 8 (1982), 20–31.
[5] V. Drensky, Codimensions of T -ideals and Hilbert series of relatively free algebras,
J. Algebra 91:1 (1984), 1–17.
[6] W. Fulton, Young tableaux. London Mathematical Society Student Texts, 35. Cam-
bridge University Press, Cambridge, 1997.
[7] H. P. Kraft and C. Procesi, Classical Invariant Theory: A primer, lecture notes,
http://www.math.unibas.ch/~kraft/Papers/KP-Primer.pdf.
[8] C. Lenormand, Opérateurs sur les polynômes non–commutatifs: définitions et no-
tations, Séminaire Schützenberger–Lentin–Nivat (Problèmes mathématiques de la
théorie des automates), 1969–1970, exposé num. 3, 9 p.
[9] I. G. Macdonald, Symmetric functions and Hall polynomials, 2nd edition, The
Clarendon Press, Oxford University Press, 1995.
[10] A. P. Popov, Identities of the Tensor Square of the Grassmann Algebra, Algebra
and Logic, 21 (1982) 4, pp. 296-316.
[11] A. P. Popov, Module Structure of Space of Proper Polynomials of Degree Seven, C.
R. Acad. Bulgare, 38:3 (1985), 295–298.
[12] C. Reutenauer, Free Lie algebras. London Mathematical Society Monographs. New
Series, 7. Oxford Science Publications. The Clarendon Press, Oxford University
Press, New York, 1993.
http://arxiv.org/abs/math/0509265
http://www.math.unibas.ch/~kraft/Papers/KP-Primer.pdf
NONCOMMUTATIVE HARMONICS 13
[13] M. Rosas, B. Sagan, Symmetric Functions in Noncommuting Variables. Transactions
of the American Mathematical Society, 358:1 (2006), 215–232.
[14] N. J. A. Sloane, The Online Encyclopedia of Integer Sequences, published electron-
ically at http://www.research.att.com/~njas/sequences/.
[15] H. Wilf, Generatingfunctionology. Second edition. Academic Press, Inc., Boston,
MA, 1994.
[16] M. C. Wolf, Symmetric functions of noncommutative elements, Duke Math. J. 2
(1936), 626–637.
Emmanuel Briand and Mercedes Rosas, Universidad de Sevilla, Sevilla,
Spain
Mike Zabrocki, York University, Toronto, Canada
http://www.research.att.com/~njas/sequences/
	1. Introduction
	2.  The Frobenius characteristic of noncommutative harmonics
	3. Non–commutative harmonics and the enveloping algebra of the derived free Lie algebra
	4. An explicit isomorphism between Q"426830A Xn "526930B  and  Q[Xn] An'.
	The shuffle basis of Q"426830A Xn "526930B .
	The hybrid basis of Q"426830A Xn "526930B .
	References
