# Invariants in Non-Commutative Variables of the Symmetric and Hyperoctahedral Groups

Anouk Bergeron-Brlek

York University, Mathematics and Statistics, 4700 Keele Street, M3J 1P3, Toronto, Canada

**Abstract.** We consider the graded Hopf algebra $NCSym$ of symmetric functions with non-commutative variables, which is analogous to the algebra $Sym$ of the ordinary symmetric functions in commutative variables. We give formulae for the product and coproduct on some of the analogues of the $Sym$ bases and expressions for a shuffle product on $NCSym$. We also consider the invariants of the hyperoctahedral group in the non-commutative case and a state a few results.

**Résumé.** Nous considérons l'algèbre de Hopf graduée $NCSym$ des fonctions symétriques en variables non-commutatives, qui est analogue à l'algèbre $Sym$ des fonctions symétriques en variables commutatives. Nous donnons des formules pour le produit et coproduit sur certaines des bases analogues à celles de $Sym$, ainsi qu'une expression pour le produit shuffle sur $NCSym$. Nous considérons aussi les invariants du groupe hyperoctaédral dans le cas non-commutatif et énonçons quelques résultats.

**Keywords:** invariants, symmetric function, non-commutative variables, Hopf algebra

## 1 Introduction

Let $X_n = x_1, x_2, \dots, x_n$ be a list of variables and denote by $\mathbb{Q}\langle X_n \rangle$ the algebra of polynomials in non-commutative variables with rational coefficients. We consider the algebra $\mathbb{Q}\langle X_n \rangle^{S_n}$ of polynomials in $\mathbb{Q}\langle X_n \rangle$ which are invariant under the action of the symmetric group $S_n$. In Bergeron et al. (2), this algebra is extended to the graded Hopf algebra $NCSym$ of symmetric functions in non-commutative variables (not to be confused with the algebra of non-commutative symmetric functions presented in Gelfand et al. (5)). The Hopf algebra $NCSym$ is analogous to the algebra of the ordinary symmetric functions in commutative variables and appears in many recent works, see for instance (6; 7; 1; 3; 2). The analogues of the monomial, elementary, homogeneous and power sum bases are defined in Rosas and Sagan (10) and are indexed by set partitions.

In Section 2, we recalled some basic facts about combinatorics of set partitions. In Section 3, we consider the Hopf algebra structure of that algebra. Section 4 contains some formulae for the product and coproduct, and expressions for a shuffle product on $NCSym$. One surprising thing that we found with this algebra is that all the bases defined by Rosas and Sagan (10) that are analogues multiplicative bases in the commutative algebra are also multiplicative and freely generated in the non-commutative version. We also found that the non-commutative homogeneous basis with the shuffle product is dual to
the non-commutative monomial basis with the usual coproduct, and the non-commutative monomial basis with the shuffle product is dual to the non-commutative homogeneous basis with the usual coproduct. This is very unusual and says that the bases defined by Rosas and Sagan (10) also behave naturally under the shuffle product.

Although this work is preliminary, at the end we introduce and state a few results on the invariants of the hyperoctahedral group $B_n$ in non-commutative variables $X_n$. This algebra is indexed by the set partitions with at most $n$ parts whose size are even. This makes clear the connection with the work of Orellana (9) on the centralizer algebra $End_{B_n}(V^{\otimes k})$ and the invariants of $B_n$.

## 2 Definitions and notations

Let $[n] = \{1, 2, \dots, n\}$. A set partition of $n$, denoted by $A \vdash [n]$, is a family of disjoint nonempty subsets $A_1, A_2, \dots, A_k \subseteq [n]$ such that $A_1 \cup A_2 \cup \dots \cup A_k = [n]$. The subsets $A_i$ are called the parts of $A$ and the length $\ell(A)$ of $A$ is the number of its parts. The size of a set partition $A$ is denoted by $|A|$. To simplify the notation, we will write each part of $A = \{A_1, A_2, \dots, A_k\}$ as a word. Moreover, the parts of every set partition will be arranged by increasing value of the smallest element in the subset.

**Example.** The set partitions of 3 are

$$ \{1, 2, 3\} \quad \{12, 3\} \quad \{13, 2\} \quad \{1, 23\} \quad \{123\}. $$

Assume that the parts of a set partition $A$ are listed in decreasing order of size, then to $A$ can be associated a partition $\lambda(A) = (|A_1|, |A_2|, \dots, |A_k|)$ and $A! = \lambda(A)! = \lambda_1!\lambda_2!\cdots\lambda_k!$. The partition $\lambda(A, B)$ will denote the partition whose $i$th part is the number of parts $A_j$ such that $A_j \subseteq B_i$, for $1 \le i \le \ell(B)$.

**Example.** Consider $A = \{136, 25, 4, 7\}$ and $B = \{12356, 47\}$. Then

$$ \begin{aligned} \lambda(A) &= (3, 2, 1, 1), \\ \lambda(A)! &= 3!2!, \\ \lambda(A, B) &= (2, 2). \end{aligned} $$

The sign of a permutation $\sigma = \sigma(1)\sigma(2)\cdots\sigma(n)$ is defined by $\operatorname{sgn}(\sigma) = (-1)^{\operatorname{inv}(\sigma)}$, where $\operatorname{inv}(\sigma)$ is the number of inversions of $\sigma$, i.e. the number of pairs $(\sigma(i), \sigma(j))$ such that $i < j$ and $\sigma(i) > \sigma(j)$. The sign $(-1)^A$ of a set partition $A$ is the sign of any permutation obtained in the following way: the cycles of the permutation will be formed by taking the integers in each part of $A$. A cycle of length $l$ has sign $(-1)^{l-1}$, so if the permutation $\sigma = c_1 \dots c_k \in S_n$ is written in cycle notation, then $\operatorname{sgn}(\sigma) = (-1)^{l_1-1} \dots (-1)^{l_k-1} = (-1)^{n-k}$. Hence the sign of a set partition $A \vdash [n]$ is $(-1)^{n-\ell(A)}$.

**Example.** Consider $A = \{1325, 4\}$. Then

$$ (-1)^A = (-1)^{5-2} = \operatorname{sgn}(35241) = (-1)^{\operatorname{inv}(35241)} = -1. $$

Given $S \subseteq [\ell(A)]$ with $S = \{s_1, s_2, \dots, s_k\}$, we define $A_S = \{A_{s_1}, A_{s_2}, \dots, A_{s_k}\}$. Then the standard-isation of $A_S$, $\mathrm{st}(A_S)$, is the set partition obtained by lowering the entries of $A_S$ and keeping the values in relative order. We will also denote by $A \downarrow_S$ the set partition $A$ restricted to the entries which are in $S$ and $A \uparrow_S$ will mean raising the entries in $A$ so that they remain in the same relative order, with the union of all parts equal to $S$. Let $S^c$ denotes the complement of $S$.
**Example.** For $S = \{1, 3, 4\}$ we get

$$
\begin{align*}
st(\{136, 25, 4, 7\}_S) &= \{124, 3, 5\}, \\
st(\{136, 25, 4, 7\} \downarrow_S) &= \{12, 3\}, \\
\{13, 2\} \uparrow_S &= \{14, 3\}.
\end{align*}
$$

For an arbitrary set $S = \{s_1, s_2, \dots, s_k\}$, $S+n$ is defined to be $\{s_1+n, s_2+n, \dots, s_k+n\}$. Given two set partitions $A \vdash [n]$ and $B$, we can build the set partitions

$$
A|B = \{A_1, A_2, \dots, A_{\ell(A)}, B_1 + n, B_2 + n, \dots, B_{\ell(B)} + n\}.
$$

A set partition $A \vdash [n]$ is called *splittable* if there exists non-empty set partitions $B \vdash [k]$ and $C \vdash [n-k]$ such that $A = B|C$, and is called *non-splittable* if it is non-empty and not splittable. If $A$ is splittable, then $A^! = (A^{(1)}, A^{(2)}, \dots, A^{(d)})$, where each $A^{(i)}$ is non-splittable, will denote the split of $A$. In that case, $A^! = A^{(1)}|A^{(2)}|\dots|A^{(d)}$.

**Example.** Consider $A = \{13, 25, 4\}$, $B = \{13, 2\}$ and $C = \{1\}$. Then

$$
A|B|C = \{13, 25, 4, 68, 7, 9\}.
$$

There is an ordering (by refinement) on the set partitions defined as follow: We say that $A \le B$ if and only if each part of $A$ is contained in some part of $B$. Under this ordering, the set partitions of $n$ form a lattice $\Pi_n$. The greatest lower bound and the least upper bound of $A$ and $B$ will be respectively denoted by $A \wedge B = \{A_i \cap B_j | 1 \le i \le \ell(A), 1 \le j \le \ell(B)\}$ and $A \vee B$. Each part in $A \vee B$ is both a union only of parts of $A$ and a union only of parts of $B$, with no proper subset having that property.

**Example.** We have

$$
\begin{align*}
\{136, 25, 4, 7\} \wedge \{167, 245, 3\} &= \{16, 3, 25, 4, 7\}, \\
\{136, 25, 4, 7\} \vee \{167, 245, 3\} &= \{1367, 245\}.
\end{align*}
$$

The set partition $\mathbf{0}_n = \{1, 2, \dots, n\}$ is the minimal set partition and $\mathbf{1}_n = \{12 \dots n\}$ is the maximal set partition. The Möbius function of $\Pi_n$ is given by

$$
\mu(A, B) = \begin{cases} 1 & \text{if } A = B, \\ -\sum_{A \le C < B} \mu(A, C) & \text{otherwise.} \end{cases}
$$

The Kronecker delta of two set partitions A and B is defined by

$$
\delta_{A,B} = \begin{cases} 1 & \text{if } A = B, \\ 0 & \text{otherwise.} \end{cases}
$$

3 Hopf algebra structure on NCSym

We will concentrate here on graded-connected Hopf algebras. These are defined as a graded algebra $(H, \mu)$ with unit, a graded coalgebra structure $(H, \Delta)$ with counit, such that the coproduct is a morphism with respect to the algebra structure, i.e. for $f, g \in H$, $\tau(f \otimes g) = g \otimes f$ and

$$
(\mu \otimes \mu) \circ (id \otimes \tau \otimes id) \circ (\Delta \otimes \Delta) = \Delta \circ \mu.
$$
The symmetric group $S_n$ acts naturally on $\mathbb{Q}\langle X_n \rangle$ by

$$ \sigma f(x_1, x_2, \dots, x_n) = f(x_{\sigma(1)}, x_{\sigma(2)}, \dots, x_{\sigma(n)}). $$

The algebra $\mathbb{Q}\langle X_n \rangle^{S_n}$ of polynomials in $\mathbb{Q}\langle X_n \rangle$ which are invariant under this action can be extended to the graded algebra

$$ NCSym = \bigoplus_{d \ge 0} NCSym_d $$

of symmetric functions in non-commutative variables, where $NCSym_d$ is the linear span of all invariants of homogeneous degree $d$ in the infinite $x_1, x_2, x_3, \dots$ non-commuting variables. This is done via an analogous technique to the one used in the commutative version (see (8) for technical references). The analogues of the bases of the symmetric functions in commutative variables are defined as follows. For $A \vdash [d]$, the monomial symmetric function in non-commutative variables is defined as

$$ \mathbf{m}_A = \sum_{(i_1, i_2, \dots, i_n)} x_{i_1} x_{i_2} \dots x_{i_d}, \qquad (1) $$

where the sum is over all sequences $(i_1, i_2, \dots, i_n)$ with $i_a = i_b$ if and only if $a$ and $b$ are in the same part in $A$. We refer the reader to (10) for the definition of the elementary symmetric function, the complete homogeneous symmetric function and the power sum function in non-commutative variables and changes of variables. In the last section, there is a table summarizing those ones. Written in terms of the monomial symmetric function in non-commuting variables, we have:

$$ \mathbf{e}_A = \sum_{B \wedge A = \emptyset} \mathbf{m}_B, \quad \mathbf{h}_A = \sum_B (B \wedge A)! \mathbf{m}_B, \quad \mathbf{p}_A = \sum_{B \ge A} \mathbf{m}_B. $$

**Example.**

$$ \mathbf{m}_{\{13,2\}} = x_1 x_2 x_1 + x_2 x_1 x_2 + x_1 x_3 x_1 + x_3 x_1 x_3 + x_2 x_3 x_2 + x_3 x_2 x_3 + \dots $$

$$ \mathbf{e}_{\{13,2\}} = \mathbf{m}_{\{1,2,3\}} + \mathbf{m}_{\{12,3\}} + \mathbf{m}_{\{1,23\}} $$

$$ \mathbf{h}_{\{13,2\}} = \mathbf{m}_{\{1,2,3\}} + \mathbf{m}_{\{12,3\}} + 2 \mathbf{m}_{\{13,2\}} + \mathbf{m}_{\{1,23\}} + 2 \mathbf{m}_{\{123\}} $$

$$ \mathbf{p}_{\{13,2\}} = \mathbf{m}_{\{13,2\}} + \mathbf{m}_{\{123\}}. $$

In (2), they consider $NCSym = \bigoplus_{d \ge 0} NCSym_d$, where $NCSym_d$ is the linear span of $\{\mathbf{m}_A\}_{A \vdash [d]}$, as a graded Hopf algebra with product and coproduct given respectively by

$$ \mu : NCSym_d \otimes NCSym_k \to NCSym_{d+k}, $$

$$ \mu(\mathbf{m}_A \otimes \mathbf{m}_B) := \sum_{\substack{C \in \Pi_{d+k} \\ C \wedge 1_d | \mathbf{1}_k = A|B}} \mathbf{m}_C $$

$$ \Delta : NCSym_d \to \bigoplus NCSym_k \otimes NCSym_{d-k}. $$

$$ \Delta(\mathbf{m}_A) = \sum_{S \subseteq [\ell(A)]} \mathbf{m}_{A_S} \otimes \mathbf{m}_{A_{S^c}} $$

# 4 Results on NCSym

The first proposition shows that the non-commutative elementary basis is multiplicative.

**Proposition 1** We have

$$ \mathbf{e}_A \mathbf{e}_B = \mathbf{e}_{A|B}. $$
**Proof:** We have $\mathbf{p}_A\mathbf{p}_B = \mathbf{p}_{A|B}$ (see (1)) and for $A \vdash [m]$, $\mathbf{e}_A = \sum_{C \le A} \mu(\mathbf{0}_m, C)\mathbf{p}_C$ (see Table 1). Thus, for a set partition $B \vdash [n]$,

$$ \begin{aligned} \mathbf{e}_A \mathbf{e}_B &= \sum_{C \le A} \mu(\mathbf{0}_m, C) \mathbf{p}_C \sum_{D \le B} \mu(\mathbf{0}_n, D) \mathbf{p}_D \\ &= \sum_{C \le A} \sum_{D \le B} \mu(\mathbf{0}_m, C) \mu(\mathbf{0}_n, D) \mathbf{p}_{C|D}. \end{aligned} $$

Now since $\{G : G \le A|B\} = \{C|D : C|D \le A|B\} = \{C|D : C \le A|D \le B\}$ is isomorphic to the cartesian product $\{C : C \le A\} \times \{D : D \le B\}$ and the Möbius function $\mu$ is multiplicative in the sense that $\mu(A, C)\mu(B, D) = \mu(A|B, C|D)$, then

$$ \begin{aligned} \mathbf{e}_A \mathbf{e}_B &= \sum_{C \le A} \sum_{D \le B} \mu(\mathbf{0}_{m+n}, C|D) \mathbf{p}_{C|D} \\ &= \sum_{G \le A|B} \mu(\mathbf{0}_{m+n}, G) \mathbf{p}_G = \mathbf{e}_{A|B}. \end{aligned} $$

□

From Proposition 1 we get the next corollary.

**Corollary 1** NCSym is freely generated by the elements $\mathbf{e}_A$, where A is non splittable.

**Proof:** Since the $\mathbf{e}_A$ are multiplicative, we have that for $A^! = (A^{(1)}, A^{(2)}, \dots, A^{(k)})$,

$$ \mathbf{e}_A = \mathbf{e}_{A^{(1)}|A^{(2)}|\dots|A^{(k)}} = \mathbf{e}_{A^{(1)}} \mathbf{e}_{A^{(2)}} \cdots \mathbf{e}_{A^{(k)}}. $$

Since the $\mathbf{e}_A$ are linearly independant, then $\{\mathbf{e}_A : A \text{ non-splittable}\}$ must be algebraically independant. □

The next corollary also follows from Proposition 1 and use the involution $\omega : NCSym \to NCSym$ defined in (10), that sends $\mathbf{e}_A$ to $\mathbf{h}_A$, for all set partitions A and linear extension.

**Corollary 2** We have

$$ \mathbf{h}_A \mathbf{h}_B = \mathbf{h}_{A|B}. $$

Moreover, NCSym is freely generated by the elements $\mathbf{h}_A$, where A is non-splittable.

**Proof:** This results from the sequence of equalities

$$ \mathbf{h}_A \mathbf{h}_B = \omega(\mathbf{e}_A)\omega(\mathbf{e}_B) = \omega(\mathbf{e}_A \cdot \mathbf{e}_B) = \omega(\mathbf{e}_{A|B}) = \mathbf{h}_{A|B}. $$

□

The coproduct on the non-commutative elementary basis and the non-commutative homogeneous basis is next given. See the Appendix for some examples.

**Proposition 2** For $A \vdash [n]$, we have

$$ \Delta(\mathbf{e}_A) = \sum_{S \subseteq [n]} \mathbf{e}_{st(A \downarrow_S)} \otimes \mathbf{e}_{st(A \downarrow_{Sc})}. $$
**Proof:** For $A \vdash [n]$, $e_A = \sum_{B \wedge A = \mathbf{0}_n} \mathbf{m}_B$ (see Table 1). Therefore

$$ \Delta(e_A) = \Delta\left(\sum_{B \wedge A = \mathbf{0}_n} \mathbf{m}_B\right) = \sum_{B \wedge A = \mathbf{0}_n} \Delta(\mathbf{m}_B) = \sum_{B \wedge A = \mathbf{0}_n} \sum_{T \subseteq [\ell(B)]} \mathbf{m}_{st(B_T)} \otimes \mathbf{m}_{st(B_{T^c})}. $$

Note that the parts of every set partition are arranged by increasing value of the smallest element in the subset. Let

$$ \begin{aligned} S_1 &= \{(B, T) \mid B \wedge A = \mathbf{0}_n \text{ and } T \subseteq [\ell(B)]\}, \\ S_2 &= \{(C, D, S) \mid C \wedge st(A \downarrow_S) = \mathbf{0}_{|S|}, D \wedge st(A \downarrow_{S^c}) = \mathbf{0}_{|S^c|} \text{ and } S \subseteq [n]\}. \end{aligned} $$

There is a bijection $\varphi : S_1 \to S_2$ defined by $\varphi((B, T)) = (st(B_T), st(B_{T^c}), B_{T_1} \cup B_{T_2} \cup \cdots \cup B_{T_{|T|}})$ with inverse $\varphi^{-1}((C, D, S)) = (C \uparrow_S \cup D \uparrow_{S^c}, \{i \mid (C \uparrow_S \cup D \uparrow_{S^c})_i \subseteq S\})$. Hence

$$ \begin{aligned} \Delta(e_A) &= \sum_{S \subseteq [n]} \sum_{C \wedge st(A \downarrow_S) = \mathbf{0}_{|S|}} \sum_{D \wedge st(A \downarrow_{S^c}) = \mathbf{0}_{|S^c|}} \mathbf{m}_C \otimes \mathbf{m}_D \\ &= \sum_{S \subseteq [n]} \left( \sum_{C \wedge st(A \downarrow_S) = \mathbf{0}_{|S|}} \mathbf{m}_C \right) \otimes \left( \sum_{D \wedge st(A \downarrow_{S^c}) = \mathbf{0}_{|S^c|}} \mathbf{m}_D \right) = \sum_{S \subseteq [n]} \mathbf{e}_{st(A \downarrow_S)} \otimes \mathbf{e}_{st(A \downarrow_{S^c})}. \end{aligned} $$

□

The next lemma will be used in order to prove a formula for the coproduct on the h basis.

**Lemma 1** $(\omega \otimes \omega) \circ \Delta = \Delta \circ \omega$.

**Proof:** By applying $\Delta$ and since $\omega(\mathbf{p}_A) = (-1^A)\mathbf{p}_A$ (see Table 6), we get

$$ \begin{aligned} (\omega \otimes \omega) \circ \Delta(\mathbf{p}_A) &= (\omega \otimes \omega) \left( \sum_{S \subseteq [\ell(A)]} \mathbf{p}_{st(A_S)} \otimes \mathbf{p}_{st(A_{S^c})} \right) \\ &= \sum_{S \subseteq [\ell(A)]} \omega(\mathbf{p}_{st(A_S)}) \otimes \omega(\mathbf{p}_{st(A_{S^c})}) \\ &= \sum_{S \subseteq [\ell(A)]} (-1)^{st(A_S)} \mathbf{p}_{st(A_S)} \otimes (-1)^{st(A_{S^c})} \mathbf{p}_{st(A_{S^c})}. \end{aligned} $$

Now observe that for any $S \subseteq [\ell(A)]$, $(-1)^{st(A_S)}(-1)^{st(A_{S^c})} = (-1)^A$. Hence

$$ \begin{aligned} (\omega \otimes \omega) \circ \Delta(\mathbf{p}_A) &= \sum_{S \subseteq [\ell(A)]} (-1)^A \mathbf{p}_{st(A_S)} \otimes \mathbf{p}_{st(A_{S^c})} \\ &= (-1)^A \Delta(\mathbf{p}_A) = \Delta((-1)^A \mathbf{p}_A) = \Delta \circ \omega(\mathbf{p}_A). \end{aligned} $$

□
**Corollary 3** For $A \vdash [n]$, one has

$$ \Delta(\mathbf{h}_A) = \sum_{S \subseteq [n]} \mathbf{h}_{st(A \downarrow_S)} \otimes \mathbf{h}_{st(A \downarrow_{S^c})}. $$

**Proof:** Let $\Delta(\mathbf{e}_A) = \sum_{B,C} d_A^{B,C} \mathbf{e}_B \otimes \mathbf{e}_C$. Then

$$ \begin{aligned} \Delta(\mathbf{h}_A) &= \Delta \circ \omega(\mathbf{e}_A) = (\omega \otimes \omega) \circ \Delta(\mathbf{e}_A) \quad \text{(by Lemma 1)} \\ &= (\omega \otimes \omega)(\sum_{B,C} d_A^{B,C} \mathbf{e}_B \otimes \mathbf{e}_C) = \sum_{B,C} d_A^{B,C} \omega(\mathbf{e}_B) \otimes \omega(\mathbf{e}_C) = \sum_{B,C} d_A^{B,C} \mathbf{h}_B \otimes \mathbf{h}_C. \end{aligned} \quad \square $$

Let $u$ and $v$ be monomials in $\mathbb{Q}\langle X_n \rangle$ and $\binom{([|u|+|v|]_u)}{u}$ be the set of subsets of $[|u| + |v|]$ with $|u|$ elements. Let $s = \{s_1, s_2, \dots, s_{|u|}\}$ be an element of that set and let $t = \{t_1, t_2, \dots, t_{|v|}\}$ be its complement in $[|u| + |v|]$. Then $u \sqcup s v$ is the monomial $w$ such that $u = w_{s_1} w_{s_2} \cdots w_{s_{|u|}}$ and $v = w_{t_1} w_{t_2} \cdots w_{t_{|v|}}$. The shuffle of the monomial $u$ with $v$ is then defined to be

$$ u \sqcup v = \sum_{s \in \binom{([|u|+|v|]_u)}{u}} u \sqcup s v. $$

**Example.**

$$ \begin{aligned} x_1 x_1 \sqcup \mathbf{x}_1 \mathbf{x}_2 &= x_1 x_1 \sqcup \{1,2\} \mathbf{x}_1 \mathbf{x}_2 + x_1 x_1 \sqcup \{1,3\} \mathbf{x}_1 \mathbf{x}_2 + x_1 x_1 \sqcup \{1,4\} \mathbf{x}_1 \mathbf{x}_2 \\ &\quad + x_1 x_1 \sqcup \{2,3\} \mathbf{x}_1 \mathbf{x}_2 + x_1 x_1 \sqcup \{2,4\} \mathbf{x}_1 \mathbf{x}_2 + x_1 x_1 \sqcup \{3,4\} \mathbf{x}_1 \mathbf{x}_2 \\ &= x_1 x_1 \mathbf{x}_1 \mathbf{x}_2 + x_1 \mathbf{x}_1 x_1 \mathbf{x}_2 + x_1 \mathbf{x}_1 \mathbf{x}_2 x_1 + \mathbf{x}_1 x_1 \mathbf{x}_1 \mathbf{x}_2 + \mathbf{x}_1 x_1 \mathbf{x}_2 x_1 + \mathbf{x}_1 \mathbf{x}_2 x_1 x_1. \end{aligned} $$

If the monomial basis of $NCSym$ is expressed as a sum of words of non-commutative monomials as in equation (1), we can define

$$ \mathbf{m}_A \sqcup \mathbf{m}_B = \sum_C \alpha_{A,B}^C \mathbf{m}_C, \quad (2) $$

where

$$ \alpha_{A,B}^{C} = \# \left\{ S \in \binom{([|A| + |B|]_u)}{|A|} \middle| \text{st}(C \downarrow_S) = A \text{ and } \text{st}(C \downarrow_{S^c}) = B \right\}. $$

This shuffle product is commutative and associative and corresponds exactly to what happens when one consider the shuffle of monomials. Considering the pairing defined on the bases of $NCSym$ by $\langle \mathbf{h}_A, \mathbf{m}_B \rangle = \delta_{A,B}$, we have the following theorem.

**Theorem 1** Let $f, g, h \in NCSym$. Then $\langle \Delta(f), g \otimes h \rangle = \langle f, g \sqcup h \rangle$.

**Proof:** Since $\langle \mathbf{h}_A \otimes \mathbf{h}_B, \mathbf{m}_C \otimes \mathbf{m}_D \rangle = \langle \mathbf{h}_A, \mathbf{m}_C \rangle \langle \mathbf{h}_B, \mathbf{m}_D \rangle$, then

$$ \begin{aligned} \langle \Delta(\mathbf{h}_A), \mathbf{m}_B \otimes \mathbf{m}_C \rangle &= \langle \sum_{S \subseteq [|A|]} \mathbf{h}_{st(A \downarrow_S)} \otimes \mathbf{h}_{st(A \downarrow_{S^c})}, \mathbf{m}_B \otimes \mathbf{m}_C \rangle = \langle \sum_{D,E} \alpha_{D,E}^A \mathbf{h}_D \otimes \mathbf{h}_E, \mathbf{m}_B \otimes \mathbf{m}_C \rangle \\ &= \sum_{D,E} \alpha_{D,E}^A \langle \mathbf{h}_D \otimes \mathbf{h}_E, \mathbf{m}_B \otimes \mathbf{m}_C \rangle = \alpha_{B,C}^A. \end{aligned} $$
On the other hand, $\langle h_A, m_B \sqcup m_C \rangle = \langle h_A, \sum_D \alpha_{B,C}^D m_D \rangle = \sum_D \alpha_{B,C}^D \langle h_A, m_D \rangle = \alpha_{B,C}^A$. so the theorem follows. $\square$

**Corollary 4** Let $\beta_{A,B}^C = \#\{S \in (\ell(A)+\ell(B)) | st(C_S) = A \text{ and } st(C_{S^c}) = B\}$. Then

$$h_A \sqcup h_B = \sum_C \beta_{A,B}^C h_C.$$

**Proof:** Follows from Theorem 1 and the fact that

$$\Delta(\mathbf{m}_C) = \sum_{S \subseteq [\ell(C)]} \mathbf{m}_{st(C_S)} \otimes \mathbf{m}_{st(C_{S^c})} = \sum_{A,B} \beta_{A,B}^C \mathbf{m}_A \otimes \mathbf{m}_B.$$

$\square$

**Conjecture 1** Let $\beta_{A,B}^C$ be the coefficients defined in Corollary 4. Then

$$\mathbf{p}_A \sqcup \mathbf{p}_B = \sum_C \beta_{A,B}^C \mathbf{p}_C.$$

Given the previous conjecture, the following proposition follows from a simple calculation.

**Proposition 3** Let $f, g \in \mathcal{NCSym}$. Then $\omega(f \sqcup g) = \omega(f) \sqcup \omega(g)$.

**Proof:** Since $\omega(\mathbf{p}_C) = (-1)^C \mathbf{p}_C$ (see Table 6), then

$$\omega(\mathbf{p}_A \sqcup \mathbf{p}_B) = \omega\left(\sum_C \beta_{A,B}^C \mathbf{p}_C\right) = \sum_C \beta_{A,B}^C \omega(\mathbf{p}_C) = \sum_C \beta_{A,B}^C (-1)^C \mathbf{p}_C.$$

Note that when $\ell(A) + \ell(B) = \ell(C)$ then $(-1)^A(-1)^B = (-1)^C$. In the definition of the shuffle product on the $\mathbf{p}$ basis, we certainly have $\ell(A) + \ell(B) = \ell(C)$, so

$$\omega(\mathbf{p}_A \sqcup \mathbf{p}_B) = \sum_C \beta_{A,B}^C (-1)^A (-1)^B \mathbf{p}_C = (-1)^A (-1)^B \mathbf{p}_A \sqcup \mathbf{p}_B = \omega(\mathbf{p}_A) \sqcup \omega(\mathbf{p}_B)$$

and the proposition follows.

$\square$

The next corollary follows naturally from this proposition.

**Corollary 5** Let $\beta_{A,B}^C$ be the coefficients defined in Corollary 4. Then

$$\mathbf{e}_A \sqcup \mathbf{e}_B = \sum_C \beta_{A,B}^C \mathbf{e}_C.$$

**Proof:** $\mathbf{e}_A \sqcup \mathbf{e}_B = \omega(h_A) \sqcup \omega(h_B) = \omega(h_A \sqcup h_B) = \omega(\sum_C \beta_{A,B}^C h_C) = \sum_C \beta_{A,B}^C \mathbf{e}_C$. $\square$

$\square$
# 5 Results on the invariants of the hyperoctahedral group

In some preliminary work, we also consider the analogue of type $B_n$ for $\mathbb{Q}\langle X_n \rangle^{S_n}$. We consider the algebra $\mathbb{Q}\langle X_n \rangle^{B_n} = \bigoplus_{d \ge 0} \mathbb{Q}\langle X_n \rangle_d^{B_n}$ of polynomials in $\mathbb{Q}\langle X_n \rangle$ which are invariant under the action of the hyperoctahedral group $B_n$ of signed permutations of $[n]$. The action of a signed permutation $\sigma \in B_n$ on $\mathbb{Q}\langle X_n \rangle$ is characterized by sending a variable $x_i$ to $\pm x_{|\sigma(i)|}$, where $|\sigma(i)|$ is the absolute value of $\sigma(i)$. One can show that a monomial basis of $\mathbb{Q}\langle X_n \rangle^{B_n}$ is given by

$$ \{ \mathbf{m}_A[X_n] \}_{\substack{\ell(A) \le n \\ |A_i| \text{ even}}} $$

where $A = \{A_1, A_2, \dots, A_{\ell(A)}\}$ is a set partition and $\mathbf{m}_A[X_n]$ is defined as in equation (1) with a finite number of variables. In other words, a monomial basis is indexed by the set partitions with at most $n$ parts of even cardinality. In (9), it has been proved that a basis for the centralizer algebra $End_{B_n}(V^{\otimes d})$ of $B_n$ is also indexed by the set partitions of $2k$ with at most $n$ parts of even cardinality. We have a correspondence between the centralizer algebra and the invariants of $B_n$ since

$$ \mathrm{End}_{B_n}(V^{\otimes k}) \simeq (V^{\otimes 2k})^{B_n} \simeq \mathbb{Q}\langle X_n \rangle_{2k}^{B_n}. $$

**Lemma 2** Let $\alpha_{d,k}$ be the number of set partitions of $d$ of length $k$ with even parts. Then

$$ F_k(q) = \sum_{d \ge 0} \alpha_{d,k} q^d = \frac{1 \cdot 3 \cdots (2k-1)q^{2k}}{(1-q^2)(1-4q^2)\cdots(1-k^2q^2)}. $$

**Proof:** We have $F_k(q) = F_{k-1}(q)^{\frac{(2k-1)q^2}{1-k^2q^2}}$, so

$$ F_k(q) = k^2 q^2 F_k(q) + q^2 F_{k-1}(q) + 2(k-1)q^2 F_{k-1}(q). $$

Taking the coefficient of $q^n$ on both sides yields the following recurrence:

$$ \alpha_{d,k} = k^2 \alpha_{d-2,k} + \alpha_{d-2,k-1} + 2(k-1)\alpha_{d-2,k-1}. $$

We would like to show that the number of set partitions of $d$ of length $k$ with even parts satisfies this same recurrence. Let us first denote by $C_{d,k}$ the set of set partitions of $d$ of length $k$ with even parts. For a set partition $A = \{A_1, A_2, \dots, A_k\}$, denote by $m_i$ and $m_i \setminus \{d\}$ the greatest value of respectively $A_i$ and $A_i \setminus \{d\}$. Order the parts of $A$ with the rule $A_i < A_j$ if and only if $m_i < m_j$. For $A \in C_{d,k}$, suppose that $d-1 \in A_i$ and $d \in A_j$. Let

$$ E_1 = \{A \in C_{d,k} | i = j, |A_i| = |A_j| > 2\}, \quad E_2 = \{A \in C_{d,k} | i < j, |A_i| \ge 2, |A_j| > 2\}, $$

$$ E_3 = \{A \in C_{d,k} | i > j, |A_i| > 2, |A_j| \ge 2\}, \quad E_4 = \{A \in C_{d,k} | i = j, |A_i| = |A_j| = 2\}, $$

$$ E_5 = \{A \in C_{d,k} | i < j, |A_i| \ge 2, |A_j| = 2\}, \quad E_6 = \{A \in C_{d,k} | i > j, |A_i| = 2, |A_j| \ge 2\}. $$

These sets are clearly mutually disjoint, and $C_{d,k} = \bigcup_{i=1}^6 E_i$.
Define an injection $f : C_{d,k} \to k^2 C_{d-2,k} \cup C_{d-2,k-1} \cup 2(k-1)C_{d-2,k-1}$ by

$$f(A) = \begin{cases} \{A_1, A_2, \dots, A_i \setminus \{d-1, d\}, \dots, A_k\} & \text{if } A \in E_1, \\ \{A_1, A_2, \dots, A_i \setminus \{d-1\} \cup \{m_j \setminus \{d\}\}, \dots, A_j \setminus \{d, m_j \setminus \{d\}\}, \dots, A_k\} & \text{if } A \in E_2 \cup E_5, \\ \{A_1, A_2, \dots, A_j \setminus \{d\} \cup \{m_i \setminus \{d-1\}\}, \dots, A_i \setminus \{d-1, m_i \setminus \{d-1\}\}, \dots, A_k\} & \text{if } A \in E_3 \cup E_6, \\ A \setminus \{\{d-1, d\}\} & \text{if } A \in E_4. \end{cases}$$

We have that $f$ sends $E_1 \cup E_2 \cup E_3$ to $k^2$ copies of $C_{d-2,k}$, $E_4$ to one copy of $C_{d-2,k-1}$ and $E_5 \cup E_6$ to $2(k-1)$ copies of $C_{d-2,k-1}$. Denote by $C_{d-2,k}^{(i,j)}$ the $(i,j)$-th copy of $C_{d-2,k}$ and by $C_{d-2,k-1}^{(i)}$ the $i$-th copy of $C_{d-2,k-1}$. The inverse of $f$ is defined as follows.

$$f^{-1}(A) = \begin{cases} \{A_1, A_2, \dots, A_i \cup \{d-1, d\}, \dots, A_k\} & \text{if } A \in C_{d-2,k}^{(i,i)}, \\ \{A_1, A_2, \dots, A_i \cup \{d-1\} \setminus \{m_i\}, \dots, A_j \cup \{d, m_i\}, \dots, A_k\} & \text{if } A \in C_{d-2,k}^{(i,j)}, \\ \{A_1, A_2, \dots, A_j \cup \{d\} \setminus \{m_j\}, \dots, A_i \cup \{d-1, m_j\}, \dots, A_k\} & \text{if } A \in C_{d-2,k}^{(j,i)}, \\ \{A_1, A_2, \dots, A_{k-1}\} \cup \{\{d-1, d\}\} & \text{if } A \in C_{d-2,k-1}^{(1)}, \\ \{A_1, A_2, \dots, A_i \cup \{d-1\} \setminus \{m_i\}, \dots, A_{k-1}, \{d, m_i\}\} & \text{if } A \in C_{d-2,k-1}^{(i)}, \\ \{A_1, A_2, \dots, A_j \cup \{d\} \setminus \{m_j\}, \dots, A_{k-1}, \{d-1, m_j\}\} & \text{if } A \in C_{d-2,k-1}^{(j)}. \end{cases}$$

So $|C_{d,k}| = \alpha_{d,k}$ because they satisfy the same recurrence. $\square$

<figure><img src="image_1.png" /></figure>

From the previous lemma, and the fact that a basis of $\mathbb{Q}\langle X_n \rangle^{B_n}$ is indexed by the set partitions with at most $n$ parts of even length, we get the following corollary.

**Corollary 6** *The Poincare series for the algebra $\mathbb{Q}\langle X_n \rangle^{B_n}$ is*

$$\sum_{d \ge 0} \dim(\mathbb{Q}\langle X_n \rangle_d^{B_n}) q^d = \frac{1}{|B_n|} \sum_{\sigma \in B_n} \frac{1}{1 - \mathrm{Tr}(\sigma) q} = 1 + \sum_{k=1}^{n} \frac{1 \cdot 3 \cdots (2k-1) q^{2k}}{(1-q^2)(1-4q^2)\cdots(1-k^2 q^2)}.$$

**Proof:** The first equality is a non-commutative analogue of Molien's Theorem, that has been proved by Dicks and Formanek (4). $\square$

<figure><img src="image_2.png" /></figure>

# 6 Appendix

The next two tables summarize the changes of bases and operations on NCSym bases. They are followed by some examples of the coproduct and shuffle product.
<table><caption>**Tab. 1:** Changes of bases (see (10)). For $e_A$, $h_A$, $p_A$ in terms of $m$, see section 3.</caption><thead><tr><th></th><th>e</th><th>h</th><th>p</th></tr></thead><tbody><tr><th>e<sub>A</sub></th><td></td><td>&sum;<sub>B&le;A</sub>(-1)<sup>B</sup>&lambda;(B, A)!h<sub>B</sub></td><td>&sum;<sub>B&le;A</sub>&mu;(0, B)p<sub>B</sub></td></tr><tr><th>h<sub>A</sub></th><td>&sum;<sub>B&le;A</sub>(-1)<sup>B</sup>&lambda;(B, A)!e<sub>B</sub></td><td></td><td>&sum;<sub>B&le;A</sub>|&mu;(0, B)|p<sub>B</sub></td></tr><tr><th>m<sub>A</sub></th><td>&sum;<sub>B&ge;A</sub>&mu;(A, B)/&mu;(0, B)&sum;<sub>C&le;B</sub>&mu;(C, B)e<sub>C</sub></td><td>&sum;<sub>B&ge;A</sub>&mu;(A, B)/|&mu;(0, B)|&sum;<sub>C&le;B</sub>&mu;(C, B)h<sub>C</sub></td><td>&sum;<sub>B&ge;A</sub>&mu;(A, B)p<sub>B</sub></td></tr><tr><th>p<sub>A</sub></th><td>1/&mu;(0, A)&sum;<sub>B&le;A</sub>&mu;(B, A)e<sub>B</sub></td><td>1/|&mu;(0, A)|&sum;<sub>B&le;A</sub>&mu;(B, A)h<sub>B</sub></td><td></td></tr></tbody></table>

<table><caption>**Tab. 2:** Operations on NCSym bases, where $A \vdash [n]$ and $B \vdash [k]$.</caption><thead><tr><th>f</th><th>f<sub>A</sub> &sdot; f<sub>B</sub></th><th>&Delta;(f<sub>A</sub>)</th><th>&omega;(f<sub>A</sub>)</th><th>f<sub>A</sub> &sqcup; f<sub>B</sub></th></tr></thead><tbody><tr><td>e</td><td>e<sub>A|B</sub><br>Proposition 1</td><td>&sum;<sub>S&sube;[n]</sub>e<sub>st(A&sube;S)</sub> &otimes; e<sub>st(A&sube;S<sub>c</sub>)</sub></td><td>h<sub>A</sub><br>(10)</td><td>&sum;<sub>C</sub>&beta;<sup>C</sup><sub>A,B</sub>e<sub>C</sub><br>Corollary 5</td></tr><tr><td>h</td><td>h<sub>A|B</sub><br>Corollary 2</td><td>&sum;<sub>S&sube;[n]</sub>h<sub>st(A&sube;S)</sub> &otimes; h<sub>st(A&sube;S<sub>c</sub>)</sub></td><td>e<sub>A</sub><br>(10)</td><td>&sum;<sub>C</sub>&beta;<sup>C</sup><sub>A,B</sub>h<sub>C</sub><br>Corollary 4</td></tr><tr><td>m</td><td>&sum;<sub>C&w;([n]||[k])=A|B</sub>m<sub>C</sub><br>(2) Proposition 3.2</td><td>&sum;<sub>S&sube;[l(A)]</sub>m<sub>st(A<sub>S</sub>)</sub> &otimes; m<sub>st(A<sub>S<sub>c</sub></sub>)</sub></td><td>?</td><td>&sum;<sub>C</sub>&alpha;<sup>C</sup><sub>A,B</sub>m<sub>C</sub><br>Equation 2</td></tr><tr><td>p</td><td>p<sub>A|B</sub><br>(1) Lemma 4.1</td><td>&sum;<sub>S&sube;[l(A)]</sub>p<sub>st(A<sub>S</sub>)</sub> &otimes; p<sub>st(A<sub>S<sub>c</sub></sub>)</sub><br>(1) Remark 4.4</td><td>(-1)<sup>A</sup>p<sub>A</sub><br>(10) Theorem 3.5</td><td>&sum;<sub>C</sub>&beta;<sup>C</sup><sub>A,B</sub>p<sub>C</sub><br>Conjecture 1</td></tr></tbody></table>

<table><caption>**Tab. 3:** Examples of coproduct and shuffle product.</caption><tbody><tr><td>f</td><td colspan="2">&Delta;(f<sub>{124,3}</sub>)</td></tr><tr><td>h</td><td colspan="2">1 &otimes; h<sub>{124,3}</sub> + h<sub>{1}</sub> &otimes; h<sub>{12,3}</sub> + 2 h<sub>{1}</sub> &otimes; h<sub>{13,2}</sub> + h<sub>{1}</sub> &otimes; h<sub>{123}</sub> + 3 h<sub>{12}</sub> &otimes; h<sub>{1,2}</sub> + 3 h<sub>{1,2}</sub> &otimes; h<sub>{12}</sub> + h<sub>{123}</sub> &otimes; h<sub>{1}</sub> + 2 h<sub>{13,2}</sub> &otimes; h<sub>{1}</sub> + h<sub>{12,3}</sub> &otimes; h<sub>{1}</sub> + h<sub>{124,3}</sub> &otimes; 1</td></tr><tr><td>m</td><td colspan="2">1 &otimes; m<sub>{124,3}</sub> + m<sub>{1}</sub> &otimes; m<sub>{123}</sub> + m<sub>{123}</sub> &otimes; m<sub>{1}</sub> + m<sub>{124,3}</sub> &otimes; 1</td></tr><tr><td>f</td><td colspan="2">f<sub>{12}</sub> &sqcup; f<sub>{1,2}</sub></td></tr><tr><td>h</td><td colspan="2">h<sub>{1,2,34}</sub> + h<sub>{13,2,4}</sub> + h<sub>{1,23,4}</sub> + h<sub>{14,2,3}</sub> + h<sub>{1,24,3}</sub> + h<sub>{12,3,4}</sub></td></tr><tr><td>m</td><td colspan="2">m<sub>{12,3,4}</sub> + m<sub>{13,2,4}</sub> + m<sub>{14,2,3}</sub> + m<sub>{1,23,4}</sub> + m<sub>{1,24,3}</sub> + m<sub>{1,2,34}</sub> + 3 m<sub>{134,2}</sub> + 3 m<sub>{123,4}</sub> + 3 m<sub>{1,234}</sub> + 3 m<sub>{124,3}</sub></td></tr></tbody></table>
# Acknowledgements

The author is grateful to the anonymous referees for the useful and accurate comments provided.

## References

[1] N. Bergeron, C. Hohlweg, M. Rosas, and M. Zabrocki. Grothendieck bialgebras, partition lattices, and symmetric functions in noncommutative variables. *Electron. J. Combin.*, 13(1):Research Paper 75, 19 pp. (electronic), 2006.

[2] N. Bergeron, C. Reutenauer, C. Rosas, and M. Zabrocki. Invariants and coinvariants of the symmetric group in noncommuting variables. *Canadian Math. Journal*. To appear.

[3] N. Bergeron and M. Zabrocki. The hopf algebras of symmetric functions and quasisymmetric functions in non-commutative variables are free and cofree. *J. of Alg. and Its Appl.*, 2005. Submitted.

[4] W. Dicks and E. Formanek. Poincaré series and a problem of S. Montgomery. *Linear and Multilinear Algebra*, 12(1):21–30, 1982/83.

[5] I. M. Gelfand, D. Krob, A. Lascoux, B. Leclerc, V. S. Retakh, and J. Y. Thibon. Noncommutative symmetric functions. *Adv. Math.*, 112(2):218–348, 1995.

[6] F. Hivert, J. C. Novelli, and J. Y. Thibon. Commutative combinatorial hopf algebras. *J. Alg. Combin*. To appear.

[7] F. Hivert, J. C. Novelli, and J. Y. Thibon. Commutative hopf algebras of permutations and trees. 2005. arXiv.org:math/0502456.

[8] I. G. Macdonald. *Symmetric functions and Hall polynomials*. The Clarendon Press Oxford University Press, New York, 1979. Oxford Mathematical Monographs.

[9] R. C. Orellana. On the algebraic decomposition of a centralizer algebra of the hyperoctahedral group. In *Algebraic structures and their representations*, volume 376 of *Contemp. Math.*, pages 345–357. Amer. Math. Soc., Providence, RI, 2005.

[10] M. H. Rosas and B. E. Sagan. Symmetric functions in noncommuting variables. *Trans. Amer. Math. Soc.*, 358(1):215–232 (electronic), 2006.