Supercharacters, symmetric functions in
noncommuting variables (extended abstract)

Marcelo Aguiar

Zhi Chen

I. Martin Isaacs

Aaron Lauve

Kay Magaard

Franco Saliola

Vidya Venkateswaran

Carlos André

Persi Diaconis

Andrea Jedwab

Tung Le

Eric Marberg

Lenny Tevlin

C. Ryan Vinroot

Carolina Benedetti

Anders Hendrickson

Kenneth Johnson

Stephen Lewis

Jean-Christophe Novelli

Jean-Yves Thibon

Ning Yan

Nantel Bergeron

Samuel Hsiao

Gizem Karaali

Huilan Li

Amy Pang

Nathaniel Thiem

Mike Zabrocki

**Abstract.** We identify two seemingly disparate structures: supercharacters, a useful way of doing Fourier analysis on the group of unipotent uppertriangular matrices with coefficients in a finite field, and the ring of symmetric functions in noncommuting variables. Each is a Hopf algebra and the two are isomorphic as such. This allows developments in each to be transferred. The identification suggests a rich class of examples for the emerging field of combinatorial Hopf algebras.

**Résumé.** Nous montrons que deux structures en apparence bien différentes peuvent être identifiées: les supercaractères, qui sont un outil commode pour faire de l'analyse de Fourier sur le groupe des matrices unipotentes triangulaires supérieures à coefficients dans un corps fini, et l'anneau des fonctions symétriques en variables noncommutatives. Ces deux structures sont des algèbres de Hopf isomorphes. Cette identification permet de traduire dans une structure les développements conçus pour l'autre, et suggère de nombreux exemples dans le domaine nouveau des algèbres de Hopf combinatoires.

**Keywords:** supercharacters, set partitions, symmetric functions in non-commuting variables, Hopf algebras

# 1 Introduction

Identifying structures in seemingly disparate fields is a basic task of mathematics. An example, with parallels to the present work, is the identification of the character theory of the symmetric group with symmetric function theory. This connection is wonderfully exposited in Macdonald's book [20]. Later, Geissinger and Zelevinsky independently realized that there was an underlying structure of Hopf algebras that forced and illuminated the identification [14, 27]. We present a similar program for a "supercharacter" theory associated to the uppertriangular group and the symmetric functions in noncommuting variables.

Let $UT_n(q)$ be the group of uppertriangular matrices with entries in the finite field $F_q$ and ones on the diagonal. This group is a Sylow $p$-subgroup of $GL_n(q)$. Describing the conjugacy classes or characters of $UT_n(q)$ is a provably "wild" problem. In a series of papers, André developed a cruder theory that
lumps together various conjugacy classes into “superclasses” and considers certain sums of irreducible characters as “supercharacters.” The two structures are compatible (so supercharacters are constant on superclasses). The resulting theory is very nicely behaved — there is a rich combinatorics describing induction and restriction along with an elegant formula for the values of supercharacters on superclasses. The combinatorics is described in terms of set partitions (the symmetric group theory involves integer partitions) and the combinatorics seems akin to tableau combinatorics. At the same time, supercharacter theory is rich enough to serve as a substitute for ordinary character theory in some problems [6].

In more detail, the group $UT_n(q)$ acts on both sides of the algebra of strictly upper-triangular matrices $n_n$ (which can be thought of as $n_n = UT_n(q) - 1$). The two sided orbits on $n_n$ can be mapped back to $UT_n(q)$ by adding the identity matrix. These orbits form the superclasses in $UT_n(q)$. A similar construction on the dual space $n_n^*$ gives a collection of class functions on $UT_n(q)$ that turn out to be constant on superclasses. These orbit sums (suitably normalized) are the supercharacters. Let

$$ \mathbf{SC} = \bigoplus_{n \ge 0} \mathbf{SC}_n, $$

where $\mathbf{SC}_n$ is the set of functions from $UT_n(q)$ to $\mathbb{C}$ that are constant on superclasses, and $\mathbf{SC}_0 = \mathbb{C}$-span$\{1\}$ is by convention the set of class functions of $UT_0(q) = \{\}$.

Let

$$ \mathbf{\Pi} = \bigoplus_{n \ge 0} \mathbf{\Pi}_n $$

be the ring of symmetric functions in non-commuting variables. Such functions were considered by Wolf [25] and Doubilet [12]. More recent work of Sagan brought them to the forefront. A lucid introduction is given by Rosas and Sagan [22] and combinatorial applications by Gebhard and Sagan [13]. The algebra $\mathbf{\Pi}$ is actively studied as part of the theory of combinatorial Hopf algebras [3, 7, 9, 10, 17, 21]. The $\mathfrak{m}_\lambda$ and thus $\mathbf{\Pi}$ are invariant under permutations of variables.

Our main result is to show that when $q = 2$, $\mathbf{SC}$ has a Hopf structure isomorphic to that of $\mathbf{\Pi}$. This construction of a Hopf algebra from the representation theory of a sequence of groups is the main contribution of this paper. It differs from previous work in that supercharacters are used. Previous work was confined to ordinary characters (e.g. [19]) and the results of [8] indicate that this is a restrictive setting. This work opens the possibility for a vast new source of Hopf algebras.

## Acknowledgements

This paper developed during a focused research week at the American Institute of Mathematics in May 2010. The main results presented here were proved as a group during that meeting.

# 2 Background

## 2.1 Supercharacter theory

Supercharacters were first studied by André (e.g. [4]) and Yan [26] in relation to $UT_n(q)$ in order to find a more tractable way to understand the representation theory of $UT_n(q)$. Diaconis and Isaacs [11] then generalized the concept to arbitrary finite groups, and we reproduce a version of this more general definition below.

A supercharacter theory of a finite group $G$ is a pair $(\mathcal{K}, \mathcal{X})$ where $\mathcal{K}$ is a partition of $G$ and $\mathcal{X}$ is a partition of the irreducible characters of $G$ such that
(a) Each $K \in \mathcal{K}$ is a union of conjugacy classes,

(b) $\{1\} \in \mathcal{K}$, where 1 is the identity element of $G$, and $\{1\} \in \mathcal{X}$, where 1 is the trivial character of $G$.

(c) For $X \in \mathcal{X}$, the character

$$ \sum_{\psi \in X} \psi(1)\psi $$

is constant on the parts of $\mathcal{K}$,

(d) $|\mathcal{K}| = |\mathcal{X}|$.

We will refer to the parts of $\mathcal{K}$ as *superclasses*, and for some fixed choice of scalars $c_X \in \mathbb{Q}$ (which are not uniquely determined), we will refer to the characters

$$ \chi^X = c_X \sum_{\psi \in X} \psi(1)\psi, \quad \text{for } X \in \mathcal{X} $$

as *supercharacters* (the scalars $c_X$ should be picked such that the supercharacters are indeed characters). For more information on the implications of these axioms, including some redundancies in the definition, see [11].

There are a number of different known ways to construct supercharacter theories for groups, including

* Gluing together group elements and irreducible characters using outer automorphisms [11],

* Finding normal subgroups $N \triangleleft G$ and grafting together supercharacter theories for the normal subgroup $N$ and for the factor group $G/N$ to get a supercharacter theory for the whole group [16].

This paper will however focus on a technique first introduced for algebra groups [11], and then generalized to some other types of groups by André and Neto (e.g. [5]).

The group $\text{UT}_n(q)$ has a natural two-sided action on the $\mathbb{F}_q$-spaces

$$ \mathbf{n} = \text{UT}_n(q) - 1 \quad \text{and} \quad \mathbf{n}^* = \text{Hom}(\mathbf{n}, \mathbb{F}_q) $$

given by left and right multiplication on $\mathbf{n}$ and for $\lambda \in \mathbf{n}^*$,

$$ (u\lambda v)(x-1) = \lambda(u^{-1}(x-1)v^{-1}), \quad \text{for } u, v, x \in \text{UT}_n(q). $$

It can be shown that the orbits of these actions parametrize the superclasses and supercharacters, respectively, for a supercharacter theory. In particular, two elements $u, v \in \text{UT}_n(q)$ are in the same superclass if and only if $u-1$ and $v-1$ are in the same two-sided orbit in $\text{UT}_n(q) \backslash \mathbf{n}/\text{UT}_n(q)$. Since the action of $\text{UT}_n(q)$ on $\mathbf{n}$ can be viewed as applying row and column operations, we obtain a parameterization of superclasses given by

$$ \left\{ \text{Superclasses of } \text{UT}_n(q) \right\} \longleftrightarrow \left\{ \begin{array}{l} u-1 \in \mathbf{n} \text{ with at most} \\ \text{one nonzero entry in} \\ \text{each row and column} \end{array} \right\}. $$
This indexing set is central to the combinatorics of this paper, so we give several interpretations for it. Let

$$S_n(q) = \left\{ \begin{array}{l} \text{Sets } \lambda \text{ of triples } i \stackrel{a}{\rightleftharpoons} j = (i, j, a) \in [n] \times [n] \times \mathbb{F}_q^\times, \\ \text{with } i < j, \text{ and } i \stackrel{a}{\rightleftharpoons} j, k \stackrel{b}{\rightleftharpoons} l \in \lambda \text{ implies } i \neq k, j \neq l \end{array} \right\},$$

where we will refer to the elements of $S_n(q)$ as $\mathbb{F}_q^\times$-set partitions. In particular,

$$S_n(q) \quad \longleftrightarrow \quad \left\{ \begin{array}{l} u-1 \in \mathbf{n} \text{ with at most} \\ \text{one nonzero entry in} \\ \text{each row and column} \end{array} \right\} \qquad (2.1) \\ \\ \lambda = \{i \stackrel{\phi(i,j)}{\rightleftharpoons} j \mid (i,j) \in D\} \quad \mapsto \quad \sum_{i \stackrel{a}{\rightleftharpoons} j \in \lambda} ae_{ij},$$

where $e_{ij}$ is the matrix with 1 in the $(i, j)$ position and zeroes elsewhere.

**Remark 1** Consider the map

$$\pi: S_n(q) \to S_n(2) \qquad (2.2) \\ \lambda \mapsto \{i \stackrel{1}{\rightleftharpoons} j \mid i \stackrel{a}{\rightleftharpoons} j \in \lambda\},$$

which ignores the part of the data that involves field scalars. Note that $S_n(2)$ is in bijection with the set partitions of the set $\{1, 2, \dots, n\}$. Indeed, the connected components of an element $\lambda \in S_n(2)$ may be viewed as the blocks of a partition of $\{1, 2, \dots, n\}$. Composing the map $\pi$ with this bijection associates a set partition to an element of $M_n(q)$ or $S_n(q)$, which we call the underlying set partition.

Fix a nontrivial homomorphism $\vartheta: \mathbb{F}_q^+ \to \mathbb{C}^\times$. For each $\lambda \in \mathbf{n}^*$, construct a $\text{UT}_n(q)$-module

$$V^\lambda = \mathbb{C}\text{-span}\{v_\mu \mid \mu \in -\text{UT}_n(q) \cdot \lambda\}$$

with left action given by

$$uv_\mu = \vartheta(\mu(u^{-1} - 1))v_{u\mu}, \quad \text{for } u \in \text{UT}_n(q), \mu \in -\text{UT}_n(q)\lambda.$$

Up to isomorphism, these modules depend only on the two-sided orbit in $\text{UT}_n(q)\backslash \mathbf{n}^* / \text{UT}_n(q)$ of $\lambda$. Furthermore, there is an injective function $\iota: S_n(q) \to \mathbf{n}^*$ given by

$$\iota(\lambda): \begin{array}{ccc} \mathbf{n} & \to & \mathbb{F}_q \\ X & \mapsto & \displaystyle\sum_{i \stackrel{a}{\rightleftharpoons} j \in \lambda} aX_{ij} \end{array}$$

that maps $S_n(q)$ onto a natural set of orbit representatives in $\mathbf{n}^*$. We will identify $\lambda \in S_n(q)$ with $\iota(\lambda) \in \mathbf{n}^*$.

The traces of the modules $V^\lambda$ for $\lambda \in S_n(q)$ are the supercharacters of $\text{UT}_n(q)$, and they have a nice supercharacter formula given by

$$\chi^\lambda(u_\mu) = \left\{ \begin{array}{ll} \frac{q^{\#\{(i,j,k)|i<j<k,i \stackrel{a}{\rightleftharpoons} k \in \lambda\}}}{q^{\#\{(i \stackrel{a}{\rightleftharpoons} l,j \stackrel{b}{\rightleftharpoons} k) \in \lambda \times \mu | i<j<k<l\}}} & \text{if } i \stackrel{a}{\rightleftharpoons} k \in \lambda \text{ and } i < j < k \\ \displaystyle\prod_{\substack{i \stackrel{a}{\rightleftharpoons} l \in \lambda \\ i \stackrel{b}{\rightleftharpoons} l \in \mu}} \vartheta(ab), & \text{implies } i \stackrel{b}{\rightleftharpoons} j, j \stackrel{b}{\rightleftharpoons} k \notin \mu, \\ 0, & \text{otherwise.} \end{array} \right. \qquad (2.3)$$
where $u_\mu$ has superclass type $\mu$ [6]. Note that the degree of the supercharacter is

$$ \chi^{\lambda}(1) = \prod_{i \stackrel{a}{\sim} k \in \lambda} q^{k-i-1}. \qquad (2.4) $$

Define

$$ \mathbf{SC} = \bigoplus_{n \ge 0} \mathbf{SC}_n, \quad \text{where} \quad \mathbf{SC}_n = \mathbb{C}\text{-span}\{\chi^{\lambda} | \lambda \in \mathcal{S}_n(q)\}, $$

and let $\mathbf{SC}_0 = \mathbb{C}\text{-span}\{\chi^{\emptyset}\}$. By convention, we write $1 = \chi^{\emptyset}$, since this element will be the identity of our Hopf algebra. Note that since $\mathbf{SC}_n$ is in fact the space of superclass functions of $\text{UT}_n(q)$, it also has another distinguished basis, the superclass characteristic functions,

$$ \mathbf{SC}_n = \mathbb{C}\text{-span}\{\kappa_\mu | \mu \in \mathcal{S}_n(q)\}, \quad \text{where} \quad \kappa_\mu(u) = \begin{cases} 1, & \text{if } u \text{ has superclass type } \mu, \\ 0, & \text{otherwise,} \end{cases} $$

and $\kappa_{\emptyset} = \chi^{\emptyset}$. Section 3 will explore a Hopf structure for this space.

## 2.2 Representation theoretic functors on SC

We will focus on two representation theoretic operations on the space $\mathbf{SC}$. For $J = (J_1|J_2|\cdots|J_\ell)$ any set composition of $\{1, 2, \dots, n\}$, let

$$ \text{UT}_J(q) = \{u \in \text{UT}_n(q) \mid u_{ij} \neq 0 \text{ with } i < j \text{ implies } i, j \text{ are in the same part of } J\}. $$

In the remainder of the paper we will need variants of a straightening map on set compositions. For each set composition $J = (J_1|J_2|\cdots|J_\ell)$, let

$$ \text{st}_J([n]) = \text{st}_{J_1}(J_1) \times \text{st}_{J_2}(J_2) \times \cdots \times \text{st}_{J_\ell}(J_\ell), \qquad (2.5) $$

where for $K \subseteq [n]$, $\text{st}_K : K \to [[K]]$ is the unique order preserving map. For example, $\text{st}_{(14|3|256)}([6]) = \{1, 2\} \times \{1\} \times \{1, 2, 3\}$.

We can extend this straightening map to a canonical isomorphism

$$ \text{st}_J : \text{UT}_J(q) \to \text{UT}_{|J_1|}(q) \times \text{UT}_{|J_2|}(q) \times \cdots \times \text{UT}_{|J_\ell|}(q) \qquad (2.6) $$

by reordering the rows and columns according to (2.5). For example, if $J = (14|3|256)$, then

$$ \text{UT}_J(q) \ni \begin{pmatrix} 1 & 0 & 0 & a & 0 & 0 \\ 0 & 1 & 0 & 0 & b & c \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & d \\ 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix} \stackrel{\text{st}_J}{\mapsto} \left( \begin{pmatrix} 1 & a \\ 0 & 1 \end{pmatrix}, (1), \begin{pmatrix} 1 & b & c \\ 0 & 1 & d \\ 0 & 0 & 1 \end{pmatrix} \right) \in \text{UT}_2(q) \times \text{UT}_1(q) \times \text{UT}_3(q). $$

Combinatorially, if $J = (J_1|J_2|\cdots|J_\ell)$ we let

$$ \mathcal{S}_J(q) = \{\lambda \in \mathcal{S}_n(q) \mid i \stackrel{a}{\sim} j \in \lambda \text{ implies } i, j \text{ are in the same part in } J\}. $$
Then we obtain the bijection

$$ \mathrm{st}_J : \mathcal{S}_J(q) \to \mathcal{S}_{|J_1|}(q) \times \mathcal{S}_{|J_2|}(q) \times \cdots \times \mathcal{S}_{|J_\ell|}(q) \quad (2.7) $$

that relabels the indices using the straightening map (2.5). For example, if $J = 14|3|256$, then

$$ \mathrm{st}_J \left( \begin{array}{ccccccc} \bullet & & & & & & \\ & \bullet & & & & & \\ & & \bullet & & & & \\ & & & \bullet & & & \\ & & & & \bullet & & \\ & & & & & \bullet & \\ & & & & & & \bullet \end{array} \right) = \begin{array}{ccccccc} \bullet & & & & & & \\ & \bullet & & & & & \\ & & \bullet & & & & \\ & & & \bullet & & & \\ & & & & \bullet & & \\ & & & & & \bullet & \\ & & & & & & \bullet \end{array} \times \begin{array}{ccccccc} \bullet & & & & & & \\ & \bullet & & & & & \\ & & \bullet & & & & \\ & & & \bullet & & & \\ & & & & \bullet & & \\ & & & & & \bullet & \\ & & & & & & \bullet \end{array} \times \begin{array}{ccccccc} \bullet & & & & & & \\ & \bullet & & & & & \\ & & \bullet & & & & \\ & & & \bullet & & & \\ & & & & \bullet & & \\ & & & & & \bullet & \\ & & & & & & \bullet \end{array} $$

Note that $\mathrm{UT}_m(q) \times \mathrm{UT}_n(q)$ is an algebra group, so it has a supercharacter theory with the standard construction [11] such that

$$ \mathbf{SC}(\mathrm{UT}_m(q) \times \mathrm{UT}_n(q)) \cong \mathbf{SC}_m \otimes \mathbf{SC}_n. $$

The combinatorial map (2.7) preserves supercharacters across this isomorphism.

The first operation of interest is restriction

$$ \begin{array}{rcl} J \mathrm{Res}_{\mathrm{st}_J(\mathrm{UT}_J(q))}^{\mathrm{UT}_n(q)} : & \mathbf{SC}_n & \to \mathbf{SC}_{|J_1|} \otimes \mathbf{SC}_{|J_2|} \otimes \cdots \otimes \mathbf{SC}_{|J_\ell|} \\ & \chi & \mapsto \mathrm{Res}_{\mathrm{UT}_J(q)}^{\mathrm{UT}_n(q)}(\chi) \circ \mathrm{st}_J^{-1}, \end{array} $$

or

$$ J \mathrm{Res}_{\mathrm{st}_J(\mathrm{UT}_J(q))}^{\mathrm{UT}_n(q)}(\chi)(u) = \chi(\mathrm{st}_J^{-1}(u)), \quad \text{for } u \in \mathrm{UT}_{|J_1|}(q) \times \cdots \times \mathrm{UT}_{|J_\ell|}(q). $$

**Remark 2** There is an algorithmic method for computing restrictions of supercharacters (and also tensor products of characters) [23, 24]. This has been implemented in Sage.

For an integer composition $(m_1, m_2, \dots, m_\ell)$ of $n$, let

$$ \mathrm{UT}_{(m_1, m_2, \dots, m_\ell)}(q) = \mathrm{UT}_{(1, \dots, m_1|m_1+1, \dots, m_1+m_2|\dots|n-m_\ell+1, \dots, n)}(q) \subseteq \mathrm{UT}_{m_1+\dots+m_\ell}(q). $$

There is a surjective homomorphism $\tau : \mathrm{UT}_n(q) \to \mathrm{UT}_{(m_1, m_2, \dots, m_\ell)}(q)$ such that $\tau^2 = \tau$ ($\tau$ fixes the subgroup $\mathrm{UT}_{(m_1, m_2, \dots, m_\ell)}(q)$ and sends the normal complement to 1). We now obtain the inflation map

$$ \mathrm{Inf}_{\mathrm{UT}_{(m_1, m_2, \dots, m_\ell)}(q)}^{\mathrm{UT}_n(q)} : \mathbf{SC}_{m_1} \otimes \mathbf{SC}_{m_2} \otimes \cdots \otimes \mathbf{SC}_{m_\ell} \to \mathbf{SC}_n, $$

where

$$ \mathrm{Inf}_{\mathrm{UT}_{(m_1, m_2, \dots, m_\ell)}(q)}^{\mathrm{UT}_n(q)}(\chi)(u) = \chi(\tau(u)), \quad \text{for } u \in \mathrm{UT}_n(q). $$

## 2.3 The Hopf algebra Π

Symmetric polynomials in a set of commuting variables $X$ are the invariants of the action of the symmetric group $\mathfrak{S}_X$ of $X$ by automorphisms of the polynomial algebra $\mathbb{K}[X]$ over a field $\mathbb{K}$.

When $X = \{x_1, x_2, \dots\}$ is infinite, we let $\mathfrak{S}_X$ be the set of bijections on $X$ with finitely many nonfixed points. Then the subspace of $\mathbb{K}[[X]]^{\mathfrak{S}_X}$ of formal power series with bounded degree is the algebra of symmetric functions $\mathrm{Sym}(X)$ over $\mathbb{K}$. It has a natural bialgebra structure defined by

$$ \Delta(f) = \sum_k f_k' \otimes f_k'', \quad (2.8) $$
where the $f'_k, f''_k$ are defined by the identity

$$f(X' + X'') = \sum_k f'_k(X') f''_k(X''), \qquad (2.9)$$

and $X' + X''$ denotes the disjoint union of two copies of $X$. The advantage of defining the coproduct in this way is that $\Delta$ is clearly coassociative and that it is obviously a morphism for the product. For each integer partition $\lambda = (\lambda_1, \lambda_2, \dots, \lambda_\ell)$, the monomial symmetric function corresponding to $\lambda$ is the sum

$$m_{\lambda}(X) = \sum_{x^{\alpha} \in O(x^{\lambda})} x^{\alpha} \qquad (2.10)$$

over elements of the orbit $O(x^{\lambda})$ of $x^{\lambda} = x_1^{\lambda_1} x_2^{\lambda_2} \cdots x_{\ell}^{\lambda_{\ell}}$ under $\mathfrak{S}_X$, and the monomial symmetric functions form a basis of $\text{Sym}(X)$. The coproduct of a monomial function is

$$\Delta(m_{\lambda}) = \sum_{\mu \cup \nu = \lambda} m_{\mu} \otimes m_{\nu}. \qquad (2.11)$$

The dual basis $m_{\lambda}^*$ of $m_{\lambda}$ is a multiplicative basis of the graded dual $\text{Sym}^*$, which turns out to be isomorphic to $\text{Sym}$ via the identification $m_n^* = h_n$ (the complete homogeneous function, the sum of all monomials of degree $n$).

The case of noncommuting variables is very similar. Let $A$ be an alphabet, and consider the invariants of $\mathfrak{S}_A$ acting by automorphisms on the free algebra $\mathbb{K}\langle A\rangle$. Two words $a = a_1 a_2 \cdots a_n$ and $b = b_1 b_2 \cdots b_n$ are in the same orbit whenever $a_i = a_j$ if and only if $b_i = b_j$. Thus, orbits are parametrized by set partitions in at most $|A|$ blocks. Assuming as above that $A$ is infinite, we obtain an algebra based on all set partitions, defining the monomial basis by

$$\mathbf{m}_{\lambda}(A) = \sum_{w \in O_{\lambda}} w, \qquad (2.12)$$

where $O_{\lambda}$ is the set of words such that $w_i = w_j$ if and only if $i$ and $j$ are in the same block of $\lambda$. One can introduce a bialgebra structure by means of the coproduct

$$\Delta(f) = \sum_k f'_k \otimes f''_k \quad \text{where} \quad f(A' + A'') = \sum_k f'_k(A') f''_k(A''), \qquad (2.13)$$

and $A' + A''$ denotes the disjoint union of two mutually commuting copies of $A$. The coproduct of a monomial function is

$$\Delta(\mathbf{m}_{\lambda}) = \sum_{J \subseteq [\ell(\lambda)]} \mathbf{m}_{\text{st}(\lambda_J)} \otimes \mathbf{m}_{\text{st}(\lambda_{Jc})}. \qquad (2.14)$$

This coproduct is cocommutative. With the unit that sends 1 to $m_0$ and the counit $\varepsilon(f(A)) = f(0, 0, \dots)$, we have that $\Pi$ is a connected graded bialgebra and therefore a graded Hopf algebra.

**Remark 3** We note that $\Pi$ is often denoted in the literature as NCSym or WSym.
### 3 A Hopf algebra realization of SC

In this section we describe a Hopf structure for the space

$$ 
\begin{aligned}
\mathbf{SC} &= \bigoplus_{n \ge 0} \mathbf{SC}_n \\
&= \mathbb{C}\text{-span}\{\kappa_\mu \mid \mu \in \mathcal{S}_n(q), n \in \mathbb{Z}_{\ge 0}\} \\
&= \mathbb{C}\text{-span}\{\chi^\lambda \mid \lambda \in \mathcal{S}_n(q), n \in \mathbb{Z}_{\ge 0}\}.
\end{aligned}
$$

The product and coproduct are defined representation theoretically by the inflation and restriction operations of Section 2.2,

$$ \chi \cdot \psi = \mathrm{Inf}_{\mathrm{UT}_{(a,b)}(q)}^{\mathrm{UT}_{a+b}(q)} (\chi \times \psi), \quad \text{where } \chi \in \mathbf{SC}_a, \psi \in \mathbf{SC}_b, \qquad (3.1) $$

and

$$ \Delta(\chi) = \sum_{\substack{J=(A|A^c) \\ A \subset [n]}} J \mathrm{Res}_{\mathrm{UT}_{|A|}(q) \times \mathrm{UT}_{|A^c|}(q)}^{\mathrm{UT}_n(q)} (\chi), \quad \text{for } \chi \in \mathbf{SC}_n. \qquad (3.2) $$

For a combinatorial description of the Hopf structure of SC it is most convenient to work with the super-class characteristic functions.

**Proposition 3.1**

$$ (a) \text{ For } \mu \in \mathcal{S}_k(q), \nu \in \mathcal{S}_{n-k}(q), $$

$$ \kappa_{\mu} \cdot \kappa_{\nu} = \sum_{\substack{\lambda = \mu \sqcup \gamma \sqcup (k+\nu) \in \mathcal{S}_n(q) \\ i \neq j \text{ implies } i \le k < j \le \lambda}} \kappa_{\lambda}, $$

where $(k + \nu) = \{(k + i) \stackrel{a}{\rightleftharpoons} (k + j) \mid i \stackrel{a}{\rightleftharpoons} j \in \nu\}$ and $\sqcup$ denotes disjoint union.

$$ (b) \text{ For } \lambda \in \mathcal{S}_n(q), $$

$$ \Delta(\kappa_{\lambda}) = \sum_{\substack{\lambda = \mu \sqcup \nu \\ \mu \in \mathcal{S}_A(q), \nu \in \mathcal{S}_{A^c}(q) \\ A \subset \{1, 2, \dots, n\}}} \kappa_{\mathrm{st}_A(\mu)} \otimes \kappa_{\mathrm{st}_{A^c}(\nu)}. $$

**Example 1** We have

$$ \begin{aligned} \kappa_{\bullet \bullet \bullet} \cdot \kappa_{\bullet \bullet \bullet} = \kappa_{\bullet \bullet \bullet} &+ \sum_{d \in \mathbb{F}_q^\times} \left( \kappa_{\bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet} + \kappa_{\bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet} + \kappa_{\bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet} \right. \\ & \left. + \sum_{d,e \in \mathbb{F}_q^\times} \left( \kappa_{\bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet} + \kappa_{\bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet} \right) \right). \end{aligned} $$
and

$$
\Delta\left(\begin{smallmatrix} \kappa & \bullet & \bullet & \bullet \\ 1 & 2 & 3 & 4 \end{smallmatrix}\right) = \kappa\begin{smallmatrix} \bullet & \bullet & \bullet & \bullet \\ 1 & 2 & 3 & 4 \end{smallmatrix} \otimes \kappa_{\emptyset} + 2\kappa\begin{smallmatrix} \bullet & \bullet & \bullet & \bullet \\ 1 & 2 & 3 & 4 \end{smallmatrix} \otimes \kappa_{\bullet} + \kappa_{\bullet}\begin{smallmatrix} \bullet & \bullet & \bullet & \bullet \\ 1 & 2 & 3 & 4 \end{smallmatrix} \otimes \kappa_{\bullet \bullet} \\
+ \kappa_{\bullet \bullet}\begin{smallmatrix} \bullet & \bullet & \bullet & \bullet \\ 1 & 2 & 3 & 4 \end{smallmatrix} \otimes \kappa_{\bullet \bullet} + 2\kappa_{\bullet}\begin{smallmatrix} \bullet & \bullet & \bullet & \bullet \\ 1 & 2 & 3 & 4 \end{smallmatrix} \otimes \kappa_{\bullet \bullet} + \kappa_{\emptyset} \otimes \kappa_{\bullet \bullet \bullet \bullet}.
$$

By comparing Proposition 3.1 to (2.14) and the product on monomials, we obtain the following theorem.

**Theorem 3.2** For $q = 2$, the map

$$
\begin{array}{rcl}
\text{ch :} & \mathbf{SC} & \to \mathbf{\Pi} \\
& \kappa_{\mu} & \mapsto \mathbf{m}_{\mu}
\end{array}
$$

is a Hopf algebra isomorphism.

Note that although we did not assume for the theorem that SC is a Hopf algebra, the fact that ch preserves the Hopf operations implies that SC for $q = 2$ is indeed a Hopf algebra.

**Corollary 3.3** *The algebra SC with product given by (3.1) and coproduct given by (3.2) is a Hopf algebra.*

**Remark 4**

(a) Note that the isomorphism of Theorem 3.2 is not in any way canonical. In fact, the automorphism group of $\Pi$ is rather large, so there are many possible isomorphisms. For our chosen isomorphism, there is no nice interpretation for the image of the supercharacters under the isomorphism of Theorem 3.2. Even less pleasant, when one composes it with the map

$$
\Pi \to \mathrm{Sym}
$$

that allows variables to commute (see [12, 22]), one in fact obtains that the supercharacters are
not Schur positive. But, exploration with Sage suggests that it may be possible to choose an isomor-
phism such that the image of the supercharacters are Schur positive.

(b) Although the antipode is determined by the bialgebra structure of Π, explicit expressions are not well understood. However, there are a number of forthcoming papers (e.g. [2, 18]) addressing this situation.

The Hopf algebra **SC** has a number of natural Hopf subalgebras. One of particular interest is the subspace spanned by linear characters (characters with degree 1). In fact, for this supercharacter theory every linear character of $U_n$ is a supercharacter and by (2.4) these are exactly indexed by the set

$$
\mathcal{L}_n = \{ \lambda \in S_n(q) \mid i \stackrel{a}{\rightsquigarrow} j \in \lambda \text{ implies } j = i + 1 \}.
$$

**Corollary 3.4** For $q = 2$, the Hopf subalgebra

$$
\mathbf{LSC} = \mathbb{C}\text{-span}\{\chi^{\lambda} \mid i \stackrel{1}{\rightleftharpoons} j \in \lambda \text{ implies } j = i + 1\},
$$

is isomorphic to the Hopf algebra of noncommutative symmetric functions Sym studied in [15].
**Remark 5** In fact, for each $k \in \mathbb{Z}_{\ge 0}$ the space

$$ \mathbf{SC}^{(k)} = \mathbb{C}\text{-span}\{\chi^{\lambda} \mid i \prec j \in \lambda \text{ implies } j - i \le k\} $$

is a Hopf subalgebra. This gives an unexplored filtration of Hopf algebras which interpolate between LSC and SC.

## References

[1] M. Aguiar, N. Bergeron and F. Sottile, *Combinatorial Hopf Algebras and generalized Dehn-Sommerville relations*, Compositio Math. **142** (2006), 1-30.

[2] M. Aguiar, N. Bergeron and N. Thiem, *A Hopf monoid from the representation theory of the finite group of unitriangular matrices*, in preparation.

[3] M. Aguiar and S. Mahajan, *Coxeter groups and Hopf algebras*, Amer. Math. Soc. Fields Inst. Monogr. **23** (2006).

[4] C. André, *Basic characters of the unitriangular group*, J. Algebra **175** (1995), 287-319.

[5] C. André and A Neto, *Super-characters of finite unipotent groups of types $B_n$, $C_n$ and $D_n$*, J. Algebra **305** (2006), 394-429.

[6] E. Arias-Castro, P. Diaconis and R. Stanley, *A super-class walk on upper-triangular matrices*, J. Algebra **278** (2004), 739-765.

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

[8] N. Bergeron, T. Lam and H. Li, *Combinatorial Hopf algebras and Towers of Algebras - Dimension, Quantization and Functorality*, Preprint arXiv:0710.3744v1.

[9] N. Bergeron, C. Reutenauer, M. Rosas and M. Zabrocki, *Invariants and coinvariants of the symmetric groups in noncommuting variables*, Canad. J. Math. **60** (2008), no. 2, 266-296.

[10] N. Bergeron and M. Zabrocki, *The Hopf algebras of symmetric functions and quasi-symmetric functions in non-commutative variables are free and co-free*, J. Algebra Appl. **8** (2009), no. 4, 581-600. Commun. Math. Phys. **199** (1998) 203-242.

[11] P. Diaconis and M Isaacs, *Supercharacters and superclasses for algebra groups*, Trans. Amer. Math. Soc. **360** (2008), 2359-2392.

[12] P. Doubilet, *On the foundations of combinatorial theory. VII: Symmetric functions through the theory of distribution and occupancy*, Studies in Applied Math. **51** (1972), 377-396.

[13] D.D. Gebhard and B.E. Sagan, *A chromatic symmetric function in noncommuting variables*, J. Algebraic Combin. **13** (2001), no. 3, 227-255.
[14] L. Geissinger, *Hopf algebras of symmetric functions and class functions*, Lecture Notes in Math. **579** (1977) 168–181.

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

[16] A. Hendrickson, *Supercharacter theories of finite cyclic groups*. Unpublished Ph.D. Thesis, Department of Mathematics, University of Wisconsin, 2008.

[17] F. Hivert, J.-C. Novelli and J.-Y. Thibon, *Commutative combinatorial Hopf algebras*, J. Algebraic Combin. **28** (2008), no. 1, 65–95.

[18] A. Lauve and M. Mastnak, *The primitives and antipode in the Hopf algebra of symmetric functions in noncommuting variables*, Preprint arXiv:1006.0367.

[19] H. Li, *Algebraic Structures of Grothendieck Groups of a Tower of Algebras*, Ph.D. Thesis, York University, 2007.

[20] I.G. Macdonald, *Symmetric functions and Hall polynomials*, 2nd ed., Oxford University Press, 1995.

[21] J.-C. Novelli and J.-Y. Thibon, *Polynomial realizations of some trialgebras*, FPSAC'06. Also preprint ArXiv:math.CO/0605061.

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

[23] N. Thiem, *Branching rules in the ring of superclass functions of unipotent upper-triangular matrices*, J. Algebraic Combin. **31** (2010), no. 2, 267–298.

[24] N. Thiem and V. Venkateswaran, *Restricting supercharacters of the finite group of unipotent upper-triangular matrices*, Electron. J. Combin. **16**(1) Research Paper 23 (2009), 32 pages.

[25] M.C. Wolf, *Symmetric functions of non-commuting elements*, Duke Math. J. **2** (1936) 626–637.

[26] N. Yan, *Representation theory of the finite unipotent linear groups*, Unpublished Ph.D. Thesis, Department of Mathematics, University of Pennsylvania, 2001.

[27] A. Zelevinsky. *Representations of Finite Classical Groups*, Springer Verlag, 1981.
M. Aguiar, University of Texas A&M,

C. André, University of Lisbon,

C. Benedetti, York University,

N. Bergeron, York University, supported by CRC and NSERC,

Z. Chen, York University,

P. Diaconis, Stanford University, supported by NSF DMS-0804324,

A. Hendrickson, Concordia College,

S. Hsiao, Bard College,

I.M. Isaacs, University of Wisconsin-Madison,

A. Jedwab, University of Southern California, supported by NSF DMS 07-01291,

K. Johnson, Penn State Abington,

G. Karaali, Pomona College,

A. Lauve, Loyola University,

T. Le, University of Aberdeen,

S. Lewis, University of Washington, supported by NSF DMS-0854893,

H. Li, Drexel University, supported by NSF DMS-0652641,

K. Magaard, University of Birmingham,

E. Marberg, MIT, supported by NDSEG Fellowship,

J.-C. Novelli, Université Paris-Est Marne-la-Vallée,

A. Pang, Stanford University,

F. Saliola, Université du Québec á Montréal, supported by CRC,

L. Tevlin, New York University,

J.-Y. Thibon, Université Paris-Est Marne-la-Vallée,

N. Thiem, University of Colorado at Boulder, supported by NSF DMS-0854893,

V. Venkateswaran, Caltech University,

C.R. Vinroot, College of William and Mary, supported by NSF DMS-0854849,

N. Yan,

M. Zabrocki, York University.