
\documentclass[submission]{FPSAC2019}

\articlenumber{24}
\addbibresource{24.bib}

% PACKAGES
\usepackage{tikz}
\usepackage{stmaryrd}

%\usepackage[backend=bibtex]{biblatex}
%\addbibresource{bibfile.bib}



% THEOREMS AND STRUCTURES
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}


\theoremstyle{definition}
\newtheorem*{definition}{Definition}
\newtheorem*{remark}{Remark}
\newtheorem{example}[theorem]{Example}
\newtheorem{examples}[theorem]{Examples}

% LETTERS AND NOTATIONS
\newcommand{\cX}{\mathcal{X}}
\newcommand{\cK}{\mathcal{K}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\calP}{\mathcal{P}}
\newcommand{\calS}{\mathcal{S}}
\newcommand{\cR}{\mathcal{R}}
\newcommand{\calR}{\mathcal{R}}
\newcommand{\cS}{\mathcal{S}}
\newcommand{\cQ}{\mathcal{Q}}
\newcommand{\cT}{\mathcal{T}}
\newcommand{\cO}{\mathcal{O}}
\newcommand{\cW}{\mathcal{W}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\bH}{\mathbf{H}}
\newcommand{\Irr}{\mathrm{Irr}}
\newcommand{\one}{1\hspace{-.12cm}1}
\newcommand{\Sup}{\mathrm{Sup}}
\newcommand{\Norm}{\mathbf{Norm}}
\newcommand{\Ind}{\mathrm{Ind}}
\newcommand{\bC}{\mathbb{C}}


%%%%%%%%%%%%%%%%%%  ARROWS AND EQUAL SIGNS %%%%%%%%%%%%%%%
\newcommand{\impliesby}[1]{
	{\stackrel{{\textstyle #1}}{\ \Rightarrow\ } }}
\newcommand{\iffby}[1]{
	{\stackrel{{\textstyle #1}}{\iff} }}

\newcommand{\subby}[1]{
	{\stackrel{{\textstyle #1}}{\ \subseteq\ } }}
\newcommand{\lact}{\rightharpoonup}
\newcommand{\ract}{\leftharpoonup}

\newcommand{\equal}[1]{
	{\stackrel{{\textstyle #1}}{\ {\textstyle =}\ } }}
\newcommand{\onto}{\twoheadrightarrow}
\newcommand{\map}[1]{\xrightarrow{#1}}
\newcommand{\leftmap}[1]{\xleftarrow{#1}}
\newcommand{\leftmapsto}{\leftarrow\!\!{\scriptscriptstyle\mid}}
\newcommand{\mapsby}[1]{ \overset{#1}{\mapsto} }
\newcommand{\leftmapsby}[1]{ \overset{#1}{\leftmapsto} }
\newcommand{\twomaps}[2]{ \overset{\xrightarrow{#1}}{\xrightarrow[#2]{}} }
\newcommand{\inc}{\hookrightarrow}
\newcommand{\dd}{\displaystyle}
\newcommand{\scscs}{\scriptscriptstyle} 
\newcommand{\scs}{\scriptstyle}
\newcommand{\ts}{\textstyle}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%% MATH OPERATORS  %%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\abs}[1]{\lvert#1\rvert}    % for absolute value
\newcommand{\st}{\mathrm{st}}          % for standardization
\newcommand{\ch}{\mathrm{char}}          % for characteristic
\newcommand{\id}{\mathit{id}}          % for identity
\newcommand{\Inv}{\mathrm{Inv}}
\newcommand{\Des}{\mathrm{Des}}
\newcommand{\GDes}{\mathrm{GDes}}      %for (proper) global descents
\newcommand{\comp}{\vDash}              %for compositions (of n)
\newcommand{\parti}{\vdash}              %for partitions (of n)
\newcommand{\rank}{\textrm{rk}}
\newcommand{\sumsub}[1]{\sum_{\substack{#1}}} % sums with multline subscripts
\newcommand{\Min}{\textsf{Min}}
\newcommand{\op}{\mathit{op}}
\newcommand{\cop}{\mathit{cop}}
\newcommand{\odd}{\mathrm{odd}}
\newcommand{\im}{\mathrm{Im}}
\newcommand{\End}{\mathrm{End}}


%%%STUFF NAT ADDED

\newcommand{\UT}{\mathrm{UT}}
\newcommand{\fkut}{\mathfrak{ut}}
\newcommand{\fku}{\mathfrak{u}}
\newcommand{\fki}{\mathfrak{i}}
\newcommand{\fkj}{\mathfrak{j}}
\newcommand{\norm}{\mathrm{norm}}
\newcommand{\cN}{\mathcal{N}}
\newcommand{\cI}{\mathcal{I}}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\fkb}{\mathfrak{b}}
\newcommand{\fkgl}{\mathfrak{gl}}
\newcommand{\fkt}{\mathfrak{t}}
\newcommand{\sml}{\mathrm{sml}}
\newcommand{\lrg}{\mathrm{lrg}}
\newcommand{\nn}{\mathrm{nn}}
\newcommand{\ag}{\mathrm{ag}}
\newcommand{\f}{\mathrm{f}}
\newcommand{\Cl}{\mathtt{Cl}}
\newcommand{\Ch}{\mathtt{Ch}}
\newcommand{\tS}{\mathsf{S}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\Aut}{\mathrm{Aut}}
\newcommand{\GL}{\mathrm{GL}}
\newcommand{\opart}{\mathrm{pp}}
\newcommand{\nnopart}{\mathrm{pp}_\nn}
\newcommand{\cL}{\mathcal{L}}
\newcommand{\scf}{\mathbf{f}_\ag^T}
\newcommand{\tpatt}{\mathrm{ptt}}
\newcommand{\patt}{\mathrm{ptt}}
\newcommand{\Res}{\mathrm{Res}}
\newcommand{\reg}{\mathrm{reg}}
\newcommand{\mountain}{\mathrm{mtn}}
\newcommand{\sky}{\mathrm{sky}}
\newcommand{\pivot}{\mathrm{pvt}}
\newcommand{\nst}{\mathrm{nst}}
\newcommand{\spanning}{\text{-span}}
\newcommand{\Inf}{\mathrm{Inf}}
\newcommand{\bT}{\mathbf{T}}
\newcommand{\bq}{\mathbf{q}}
\newcommand{\bm}{\mathbf{m}}
\newcommand{\cover}{\mathrm{cvr}}
\newcommand{\Int}{\mathrm{Int}}
\newcommand{\gen}{\mathrm{gn}}
\newcommand{\cogen}{\mathrm{ud}}
\newcommand{\Dec}{\mathrm{Dec}}
\newcommand{\One}{1\hspace{-.13cm}1}
\newcommand{\cA}{\mathcal{A}}
\newcommand{\cB}{\mathcal{B}}
\newcommand{\cC}{\mathcal{C}}
\newcommand{\cM}{\mathcal{M}}
\newcommand{\gco}{\mathrm{gco}}
\newcommand{\pp}{\mathrm{lbl}}
\newcommand{\lcm}{\mathrm{lcm}}
\newcommand{\poset}{\mathrm{PO}}
\newcommand{\pattern}{\mathbf{ptt}}
\newcommand{\cG}{\mathcal{G}}
\newcommand{\cJ}{\mathcal{J}}
\newcommand{\anti}{\mathrm{Anti}}
\newcommand{\poposet}{\mathbf{ppst}}
\newcommand{\fpoposet}{\mathbf{Tppst}}
\newcommand{\cvx}{\mathrm{cvx}}
\newcommand{\Fac}{\mathrm{Fac}}
\newcommand{\select}{\mathrm{slt}}
\newcommand{\SC}{\mathrm{SC}}
\newcommand{\NPL}{\mathrm{NPtt}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\width}{\mathrm{wdth}}


\newcommand{\eproof}{\hfill\framebox[8pt]{\rule{0pt}{2pt}}}

% TITLE, AUTHOR'S NAME AND ADDRESS
\title{Pattern groups and a poset based Hopf monoid }

\date{}
\author{Farid Aliniaeifard \and Nathaniel Thiem}

\address{Department of Mathematics,  University of Colorado Boulder,
Boulder, Colorado 80309 \\}

\received{\today}

\abstract{The supercharacter theory of algebra groups gave us a representation theoretic realization of the Hopf algebra of symmetric functions in noncommuting variables.  The underlying representation theoretic framework comes equipped with two canonical bases, one of which was completely new in terms of symmetric functions.  This paper simultaneously generalizes this Hopf structure by considering a larger class of groups while also restricting the representation theory to a more combinatorially tractable one.  Using the normal lattice supercharacter theory of pattern groups, we not only gain a third canonical basis, but also are able to compute numerous structure constants in the corresponding Hopf monoid, including coproducts and antipodes for the new bases.
}	

\begin{document}
	
	\maketitle
	


	
\section{Introduction} \label{Introduction}

A supercharacter theory of the unipotent upper-triangular matrices of the finite general linear groups gave a representation theoretic interpretation to the Hopf algebra of symmetric functions in non-commuting variables \cite{MR2880223}.  In fact, these supercharacter theories glue together most naturally as a Hopf monoid as described in \cite{MR3117506}, where we obtain the Hopf algebra as a quotient structure.   They give a rich combinatorics on set partitions explored  in \cite{MR3273396,MR3078055,MR3454411}.   However, the overall Hopf structure remains mysterious, especially with regard to the coproduct on the character basis.  This paper explores a supercharacter theory that is simultaneously computable for a larger swath of groups (including in our case all pattern groups), and yet is more amenable to explicit computation of structure constants.

Formally introduced by Diaconis--Isaacs \cite{MR2373317}, a supercharacter theory can be thought of as an approximation to the usual character theory of a group.  Given any set partition $\cK$ of a group $G$, one can study the subspace of the space of functions $\f(G)=\{\psi:G\rightarrow\CC\}$ that are constant on the parts of $\cK$.  If this subspace additionally has a basis of orthogonal characters, then we say that the parts of $\cK$ are the superclasses of a supercharacter theory.  The interplay between the parts of $\cK$ and the basis of characters (called supercharacters) mimic the interplay between conjugacy classes and irreducible characters.    This point of view then gives a framework for studying the representation theory of coarser (and often more combinatorial) partitions of groups.

This paper uses a specific supercharacter theory introduced by Aliniaeifard \cite{MR3563023} in his Ph.D. thesis work.  It gives a general construction for arbitrary groups (though it prefers groups with non-trivial normal subgroups) that has many combinatorial properties baked in.   The paper \cite{1810.01353} explores some more combinatorial implications of such theories in general, giving lattice-based formulas for the supercharacter values and for the restriction of supercharacters.  This paper applies these techniques to the case of pattern groups (which is in fact the original motivation for that work).

Pattern groups are a family of unipotent groups that are built out of finite posets, roughly a group version of an incidence algebra.  While they were a fundamental example in \cite{MR2373317}, the supercharacter theory they give in that paper for pattern groups is not generally well understood.  Andrews introduced a different supercharacter theory called a non-nesting supercharacter theory that has nice combinatorial properties \cite{MR3365596}; in fact, \cite{MR3656278} used this theory to study generalize Gelfand--Graev characters for the finite general linear groups.  While his theory differs from ours, it is morally equivalent.   This paper explores a Hopf monoid first defined (up to moral equivalence) by Andrews; however, the Aliniaeifard supercharacter theory gives us some additional tools, including a third canonical basis and a restriction formula from \cite{1810.01353}.  These tools allow us to give more explicit structural results, including a coproduct on supercharacters and antipode formulas.
  
After reviewing some of the background material in \cref{Preliminaries}, we apply the results of \cite{1810.01353} to the pattern group case in \cref{PatternGroupCombinatorics}. \cref{Monoid} reviews the monoid constructed in \cite{MR3365596} and examines the structure constants of various bases.  Here we have a new third basis coming from the normal lattice supercharacter theory and \cref{StructureConstantsSupercharacters} gives a formula for the coproduct on supercharacters.  We then explore some of the structure of this monoid, establish an algebraically independent set of free generators (as a monoid), and construct the primitive elements in the style of \cite{MR3273396}.  Along the way, we also compute the antipode on several bases.




\section{Preliminaries}\label{Preliminaries}

This section reviews the necessary background on pattern groups and supercharacter theories.  Throughout we will make use of different posets on an underlying set, so given a set $A$, let
$$\poset(A)=\{\text{partial orders on $A$}\}.$$

\subsection{Pattern groups}

Fix a finite field $\FF_q$, a set $A$, and a poset $\cR\in \poset(A)$.  Let 
$$\Int(\cR)=\{[i,j]\mid i,j\in \cR, i\preceq_\cR j\}$$
be the interval poset of $\cR$ (ordered by inclusion).  The corresponding \textbf{\emph{pattern group}} is given by
$$\UT_\cR=\{u:\Int(\cR)\rightarrow \FF_q\mid u([i,i])=1, i\in A\},$$
where for $u,v\in \UT_\cR$,
$$(uv)([i,k])=\sum_{i\preceq_\cR j\preceq_\cR k} u([i,j])v([j,k]).$$
In the case where $\cR$ is a linear order, we obtain the maximal group of upper triangular matrices in the finite general linear group with rows and columns indexed by $\cR$.

For each subposet $\cO\in\poset(A)$ of $\cR$, we have that $\UT_\cO\subseteq \UT_\cR$.  Let
$$\Int^\circ(\cR)=\{[i,j]\mid i,j\in \cR, i\prec_\cR j\}$$
be the set of proper intervals.  Since this paper is concerned with normal subgroups, we would like an easy characterization of when these subgroups $\UT_\cO$ is in fact normal. Recall, that a \textbf{\emph{co-ideal}} $I$ in a poset $\cR$ is a subset that satisfies $K\in I$ implies $L\in I$ for all $L\succeq_\cR K$.

\begin{proposition}
For subposet $\cO$ of $\cR$, $\UT_\cO\triangleleft\UT_\cR$ if and only if $\Int^\circ(\cO)$ is a co-ideal of $\Int^\circ(\cR)$.
\end{proposition}



 Given a poset $\cR$, the pattern group $\UT_\cR$  has many normal subgroups, and in general it is not clear that it is possible to find them all.  Instead, we consider the subset of normal subgroups
\begin{equation}\label{NormalPatternSubgroups}
\NPL(\cR)=\{\UT_\cQ\triangleleft \UT_\cR\mid \cQ\in \poset(A)\text{ a subposet of }\cR\}.
\end{equation}
This set forms a distributive lattice under containment with
$$\UT_\cO\cap \UT_\cP=\UT_{\cO\cap \cP} \quad \text{where}\quad i\preceq_{\cO\cap \cP}j \text{ if and only if  $i\preceq_\cO j$ and $i\preceq_\cP j$},$$
and 
$$ \UT_\cO \UT_\cP =\UT_{\cO\cup\cP} \quad \text{where}\quad i\preceq_{\cO\cup \cP}j \text{ if and only if  $i\preceq_\cO j$ or $i\preceq_\cP j$}.$$
The join irreducible elements given by
\begin{equation}
\UT_{\cR_{[i,j]}^\vee}\quad \text{with}\quad k\preceq_{\cR_{[i,j]}^\vee} l \quad \text{if and only if $[i,j]\preceq_{\cR} [k,l]$},
\end{equation}
and meet irreducible elements given by
\begin{equation}
\UT_{\cR_{[i,j]}}\quad \text{with}\quad k\preceq_{\cR_{[i,j]}} l \quad \text{if and only if $[k,l]\npreceq_{\cR} [i,j]$}.
\end{equation}


\subsection{Normal lattice supercharacter theories}\label{NormalLatticeSupercharacter}

Given a set partition $\cK$ of $G$, let
$$\f(G;\cK)=\{\psi:G\rightarrow \CC\mid \{g,h\}\subseteq K\in \cK\text{ implies } \psi(g)=\psi(h)\}$$
be the set of functions constant on the blocks of $\cK$.

A \textbf{\emph{supercharacter theory}} $\tS$ of a finite group $G$ is a pair $(\Cl(\tS),\Ch(\tS))$ where $\Cl(\tS)$ is a set partition of $G$ whose blocks are called \textbf{\emph{superclasses}} and $\Ch(\tS)$ is a set partition  of the irreducible characters $\Irr(G)$ of $G$, such that
\begin{enumerate}
\item[(SC1)] $\{1\}\in \Cl(\tS)$,
\item[(SC2)] $|\Cl(\tS)|=|\Ch(\tS)|$,
\item[(SC3)] For each $X\in \Ch(\tS)$, the \textbf{\emph{supercharacter}}
$$\sum_{\psi\in X}\psi(1)\psi\in \f(G;\Cl(\tS)).$$
\end{enumerate}  
  In fact, the supercharacters of $\tS$ form an orthogonal basis for $\f(G;\Cl(\tS))$; thus, the superclasses are unions of conjugacy classes.   
 
There are several standard supercharacter theories that get applied to pattern groups.  Since a pattern group $\UT_\cR$ is in fact an algebra group, \cite{MR2373317} defines a supercharacter theory whose superclasses are the equivalence classes of the set partition
\begin{equation}\label{AlgebraGroup}
u\sim v\quad \text{if and only if} \quad \text{there exist $a,b\in \UT_\cR$ such that $u=1+a(v-1)b$.}
\end{equation}
However, it is not even known whether this theory is in general wild, and they certainly are not generally understood.  Andrews \cite{MR3365596} defines a more suitable theory which he calls a non-nesting supercharacter theory for $\UT_\cR$.  This theory is very close to the following supercharacter theory that is the focus of this paper. 

\begin{theorem}[Normal Lattice Supercharacter Theory \cite{MR3563023}]\label{NormalLatticeSupercharacterTheory}
 Let $\cN$ be a set of normal subgroups such that $\{1\},G\in \cN$, and for all $M,N\in \cN$, we have $MN,M\cap N\in \cN$. 
 Then the partitions $\Cl=\{N_\circ\neq \emptyset\mid N\in \cN\}$, where $$
 N_\circ=\{g\in N\mid g\notin M\in \cN, \text{ if $N$ covers $M$ in $\cN$}\},$$
and $\Ch=\{X^{N^\bullet}\neq \emptyset \mid N\in \cN\}$, where 
$$X^{N^\bullet}=\{\psi\in \Irr(G)\mid N\subseteq \ker(\psi)\nsupseteq O,\text{ if $O$ covers $N$  in $\cN$}\}$$
define a supercharacter theory $\tS_\cN$ of $G$.
\end{theorem} 
This paper considers 
\begin{equation}\label{PatternNormalLattice}
\tS_\cR=\tS_{\NPL(\cR)}=(\Cl(\cR),\Ch(\cR)).
\end{equation}
which is a coarsening of Andrews' nonnesting theory (his is indexed by labeled set partitions, and we combine all possible labelings).
 





\section{Poset partitions and non-nesting supercharacter theories}\label{PatternGroupCombinatorics}

This section applies \cite{1810.01353} to the particular case of the normal lattice theory built on normal pattern subgroups.  We first review the poset combinatorics introduced in \cite{MR3365596} and connect it to the normal pattern subgroup lattice $\NPL(\cR)$.    We review the character formula of this theory from the point of view introduced in \cite{1810.01353}, and conclude with a combinatorial description of restriction between pattern groups.


Fix a set $A$, and let $\cR\in \poset(A)$.  An $\cR$-\textbf{\emph{partition}} is a subset
$$\lambda\subseteq \Int^\circ(\cR)$$
such that the interval between two elements $[i,j],[k,l]\in \lambda$ is a total order if and only if $[i,j]=[k,l]$.
Let
\begin{equation}
\opart(\cR)=\{\cR\text{-partitions}\}.
\end{equation}

We may visualize these partitions by placing the Hasse diagram of $\cR$ as the base, and then place an arc from $i$ to $j$ if $[i,j]\in \lambda$.  For example, 
$$\lambda=\{[1,4],[4,5],[3,5]\}\in \opart\left(
\begin{tikzpicture}[scale=.3,baseline=.5cm]
\foreach \x/\y/\z in {0/0/1,0/1/2,-1/2/3,1/2/4,0/3/5,0/4/6}
	\node (\z) at (\x,\y) [inner sep = 0] {$\scriptscriptstyle{\z}$};
\foreach \x/\y in {1/2,2/3,2/4,3/5,4/5,5/6}
	\draw[gray] (\x)--(\y);
\end{tikzpicture}\right)\quad \text{is}\quad 
\begin{tikzpicture}[scale=.7,baseline=0cm]
\foreach \x/\y/\z in {0/0/1,1/.1/2,1.9/.6/3,2.1/-.4/4,3/.3/5,4/.4/6}
	\node (\z) at (\x,\y) [inner sep = 0] {$\scriptscriptstyle{\z}$};
\foreach \x/\y in {1/2,2/3,2/4,3/5,4/5,5/6}
	\draw[gray] (\x)--(\y);
\foreach \x/\y in {1/4,4/5,3/5}
	\draw (\x) to [out=70, in=110] (\y);
\end{tikzpicture}\ .
$$
Note that if $\cL$ is a linear order, then the transitive closure of the relation $i\sim_\lambda j$ if $[i,j]\in \lambda$ gives a set partition of the underlying set.

Given a poset $\cP$, let
$$\anti(\cP)=\{\lambda\subseteq \cP\mid \lambda\text{ is an antichain}\}.$$
An $\cR$-partition $\lambda$ is \textbf{\emph{non-nesting}} if $\lambda$ is an anti-chain in $\Int^\circ(\cR)$.   Let
$$\nnopart(\cR)=\{\lambda\in\opart(\cR)\mid \lambda\in \anti\Big(\Int^\circ(\cR)\Big)\}.$$
For example,
$$\begin{tikzpicture}[scale=.7,baseline=0cm]
\foreach \x/\y/\z in {0/0/1,1/.1/2,1.9/.6/3,2.1/-.4/4,3/.3/5,4/.4/6}
	\node (\z) at (\x,\y) [inner sep = 0] {$\scriptscriptstyle{\z}$};
\foreach \x/\y in {1/2,2/3,2/4,3/5,4/5,5/6}
	\draw[gray] (\x)--(\y);
\foreach \x/\y in {3/6,4/5}
	\draw (\x) to [out=70, in=110] (\y);
\end{tikzpicture}\in \nnopart\left(
\begin{tikzpicture}[scale=.3,baseline=.5cm]
\foreach \x/\y/\z in {0/0/1,0/1/2,-1/2/3,1/2/4,0/3/5,0/4/6}
	\node (\z) at (\x,\y) [inner sep = 0] {$\scriptscriptstyle{\z}$};
\foreach \x/\y in {1/2,2/3,2/4,3/5,4/5,5/6}
	\draw[gray] (\x)--(\y);
\end{tikzpicture}\right)\qquad \text{but}\qquad \begin{tikzpicture}[scale=.7,baseline=0cm]
\foreach \x/\y/\z in {0/0/1,1/.1/2,2/.2/3,3/.3/4,4/.4/5,5/.5/6}
	\node (\z) at (\x,\y) [inner sep = 0] {$\scriptscriptstyle{\z}$};
\foreach \x/\y in {1/2,2/3,2/4,3/5,4/5,5/6}
	\draw[gray] (\x)--(\y);
\foreach \x/\y in {3/6,4/5}
	\draw (\x) to [out=70, in=110] (\y);
\end{tikzpicture}\notin \nnopart\left(
\begin{tikzpicture}[scale=.3,baseline=.6cm]
\foreach \x/\y/\z in {0/0/1,0/1/2,0/2/3,0/3/4,0/4/5,0/5/6}
	\node (\z) at (\x,\y) [inner sep = 0] {$\scriptscriptstyle{\z}$};
\foreach \x/\y in {1/2,2/3,3/4,4/5,5/6}
	\draw[gray] (\x)--(\y);
\end{tikzpicture}\right).$$

For $\lambda\in \nnopart(\cR)$, let
\begin{equation}\label{PartitionToSubgroup}
\UT^\lambda =\prod_{[i,j]\in \lambda} \UT_{\cR^{\vee}_{[i,j]}}\quad\text{and}\quad 
\UT_\lambda=  \bigcap_{[i,j]\in \lambda}  \UT_{\cR_{[i,j]}} .
\end{equation}
In other words,  in the first case, $\lambda$ specifies the minimal elements in co-ideal of $\Int^\circ(\cR)$, and in the second $\lambda$ specifies the maximal elements not in the co-ideal of $\Int^\circ(\cR)$  (thus recovering every element of $\NPL(\cR)$ in both ways).

\begin{example}
When $\cR\in \poset(B)$ is a total order, then $|\nnopart(\cR)|$ is the $|B|$th Catalan number.  In fact, if we view $\UT_\cR$ as upper-triangular matrices, then there is a natural Dyck path for each normal subgroup.  If we let $\ast$ indicate entries that may be nonzero, one such subgroup might be
$$\UT_\lambda=\left[
\begin{tikzpicture}[scale=.5,baseline=2.15cm]
\foreach \x in {1,...,8}
	\node (\x\x) at (\x,9-\x) {$1$};
\foreach \x in {1,...,7}
	{\foreach \y in {\x,...,7}
		\node (\x\y) at (\x,8-\y) {$0$};}
\draw[gray,thick] (.5,8.5) -- (1.5,8.5) -- (1.5,7.5) -- (4.5,7.5) -- (4.5,5.5) -- (5.5,5.5) -- (7.5,5.5) -- (7.5,2.5) -- (8.5,2.5) -- (8.5,.5);
\foreach \x/\y in {3/7,4/7,4/6,5/5,6/5,7/5,6/4,7/4,7/3,8/2}
	\node at (\x,\y) {$0$};
\foreach \x in {2,...,8}
	\node at (\x,8) {$\ast$};
\foreach \y in {6,7}
	{\foreach \x in {5,...,8}
		\node at (\x,\y) {$\ast$};}
\foreach \y in {3,4,5}
	\node at (8,\y) {$\ast$};
\end{tikzpicture}\right]=\UT^\mu.$$
The set partitions $\lambda$ and $\mu$ capture aspects of the Dyck path.  That is, $\lambda$ gives the coordinates of the peaks, so in the example
$\lambda=\{[2,4],[4,7],[7,8]\}$ (where we omit peaks with trivial coordinates), and $\mu$ gives the coordinates of the valleys, so $\mu=\{[1,2],[3,5],[6,8]\}$.
\end{example}

As a consequence of \cite{1810.01353}, we obtain a character formula for the supercharacters 
\begin{equation}\label{PatternSupercharacterDefinition}
\chi^\lambda=\sum_{\psi\in X^{\UT_\lambda^\bullet}}\psi(1)\psi.
\end{equation}
\begin{proposition}\label{PatternCharacterFormula}Let $\lambda,\mu\in \nnopart(\cR)$.  For $g\in \UT^\mu_\circ$,
$$\chi^{\lambda}(g)=\left\{\begin{array}{ll}\frac{|\UT_\cR|}{|\UT_\lambda|}\Big(1-\frac{1}{q}\Big)^{|\lambda|} \Big(\frac{1}{1-q}\Big)^{|\lambda\cap \mu|} & \text{if $g\in\cC_\lambda$,}\\ 0 & \text{otherwise,}
\end{array}\right.\quad\text{where}\quad \cC_\lambda=\prod_{N\text{ covers } \UT_\lambda} N.$$
\end{proposition}





\section{A Hopf monoid}\label{Monoid}

The goal of this section is to revisit a Hopf monoid defined in \cite{MR3365596} built out of the representation theory of pattern groups.  For a more detailed background on Hopf monoids, we recommend \cite{MR2724388}.  While there has been more literature on Hopf algebras, it appears that Hopf monoids seem to be especially well-suited to the representation theory of unipotent groups \cite{MR3117506}.  As it happens, we can easily recover a corresponding Hopf algebra as a quotient, but the monoid structure allows easier computations than in the Hopf algebra.  


\subsection{The pattern group Hopf monoid}
Define a vector species $\pattern:\{\text{sets}\}\rightarrow \{\FF_q\text{-modules}\}$ by
$$\pattern[A]=\bigoplus_{\cR\in \poset(A)} \f(\UT_\cR).$$

Let $\cP\in \poset(A)$ and $\cQ\in \poset(B)$ with $A\cap B=\emptyset$.  The \textbf{\emph{concatenation}}  $\cP.\cQ\in \poset(A\cup B)$ of $\cP$ with $\cQ$ is given by
\begin{equation*}
i\preceq_{\cP.\cQ}j \quad\text{if $i\preceq_\cP j$, $i\preceq_\cQ j$ or $i\in A$ and $j\in B$.}  
\end{equation*}
There is a corresponding projection $\pi_{A,B}: \UT_{\cP.\cQ}\rightarrow \UT_\cP\times \UT_\cQ$ given by
$$\pi_{A,B} (u) ([i,j])=\left\{\begin{array}{ll} 
u([i,j]) & \text{if $i,j\in A$ or $i,j\in B$,}\\
0 & \text{otherwise.}
\end{array}\right.$$ 

Given $\cP\in \poset(C)$ and $A\subseteq C$, the  \textbf{\emph{restriction}} $\cP|_A\in \poset(A)$ of $\cP$ to $A$ is given by
$$i\preceq_{\cP|_A} j\quad \text{if $i\preceq_\cP j$}.$$
There is a corresponding injective function $\iota_{A, B}:\UT_{\cP|_A}\times \UT_{\cP|_B}\rightarrow \UT_\cP$ given by
$$\iota_{A, B}(u,v)([i,j])=\left\{\begin{array}{ll} u([i,j]) & \text{if $i,j\in A$}\\ v([i,j]) & \text{if $i,j\in B$} \\ 0 & \text{otherwise.}\end{array}\right.$$
These constructions give us a product and coproduct on $\pattern$ via
$$
m_{A,B}(\chi\otimes \psi )=(\chi,\psi)\circ \pi_{A,B}
\qquad\text{and}\qquad
\Delta_{A,B}(\psi)=\psi\circ \iota_{A,B}$$
where these again give us the functors of inflation and restriction, respectively.  As shown in \cite{MR3365596}, these functions are compatible and give us a Hopf monoid.   Furthermore, every supercharacter theory on pattern groups that are compatible with inflation and restriction give us a sub Hopf monoid.    Our focus for the rest of the paper will be on the sub Hopf monoid
$\pattern_\NPL:\{\text{sets}\}\rightarrow \{\FF_q\text{-spaces}\}$ given by
$$\pattern_\NPL[A]=\bigoplus_{\cR\in \poset(A)} \f(\UT_\cR;\Cl(\cR)),$$
where $\Cl(\cR)$ is the superclass partition given in (\ref{PatternNormalLattice}).

As a supercharacter theory, $\tS_\cR$ equips $\f(\UT_\cR;\Cl(\cR))$ with two natural bases
\begin{align*}
\f(\UT_\cR;\Cl(\cR))&=\CC\spanning\{\delta_\mu\mid \mu\in \nnopart(\cR)\}\\
&=\CC\spanning\{\chi^\lambda \mid \lambda\in \nnopart(\cR)\},
\end{align*}
where
$$\delta_\mu(g)=\left\{\begin{array}{ll} 1 & \text{if $g\in \UT^\mu_\circ$},\\ 0 & \text{otherwise,}\end{array}\right.$$
is the superclass indicator function, and $\chi^\lambda$ is the supercharacter as in (\ref{PatternSupercharacterDefinition}).

As a normal lattice supercharacter theory, we obtain a third canonical basis
$$\f(\UT_\cR;\Cl(\cR))=\CC\spanning\{\chi^{\UT_\lambda}\mid \lambda\in \nnopart(\cR)\},
\quad \text{where}\quad  
\chi^{\UT_\lambda}=\sum_{\UT_\nu\supseteq \UT_\lambda} \chi^{\nu}.$$
Note that if
\begin{equation*}
\delta_{\UT^\mu}(g)=\left\{\begin{array}{ll} 1 & \text{if $g\in \UT^\mu$},\\ 0 & \text{otherwise.}\end{array}\right.
\end{equation*}  
give the normal subgroup indicator functions, then as the character of the permutation module $\Ind_{\UT_\lambda}^{\UT_\cR}(\One)$,
\begin{align*}
\chi^{\UT_\lambda}(g)&=\left\{\begin{array}{ll} \frac{|\UT_\cR|}{|\UT_\lambda|} & \text{if $g\in \UT_\lambda$},\\ 0 & \text{otherwise,}\end{array}\right.\\
&=\frac{|\UT_\cR|}{|\UT_\lambda|} \delta_{\UT_\lambda}(g).
\end{align*} 

For these three bases we can compute the structure constants as follows.  First the superclass indicators give

\begin{lemma}[\cite{MR3365596}]
Let $A,B$ be sets with $A\cap B=\emptyset$. 
\begin{enumerate}
\item[(a)] For $\cR\in \poset(A)$, $\cQ\in \poset(B)$, $\mu\in \nnopart(\cR)$ and $\nu\in\nnopart(\cQ)$,
$$\Inf_{A,B}(\delta_\mu\otimes\delta_\nu)=\sum_{\lambda\in \nnopart(\cP.\cQ)\atop \lambda|_A=\mu,\lambda|_B=\nu}\delta_\lambda.$$
\item[(b)] For $\cP\in \poset(A\cup B)$, $\lambda\in \nnopart(\cP)$,
$$\Res_{A,B}(\delta_\lambda)=\left\{\begin{array}{@{}l@{\ }l} \delta_{\lambda_A}\otimes \delta_{\lambda_B} & \text{if $\lambda_A\cup \lambda_B=\lambda$,}\\ 0 &\text{otherwise.}\end{array}\right.$$
\end{enumerate}
\end{lemma}

The normal subgroup basis has the following constants.

\begin{lemma}\label{StructureSubgroupPartition}
Let $A,B$ be sets with $A\cap B=\emptyset$. 
\begin{enumerate}
\item[(a)] For $\cR\in \poset(A)$, $\cQ\in \poset(B)$, $\lambda\in \nnopart(\cR)$ and $\nu\in\nnopart(\cQ)$,
$$\Inf_{A,B}(\chi^{\UT_\lambda}\otimes\chi^{\UT_\nu})=\chi^{\UT_{\lambda\cup\nu}}.$$
\item[(b)] For $\cR\in \poset(A\cup B)$, $\mu\in \nnopart(\cR)$,
$$\Res_{A,B}(\delta_{\UT^\mu})=\delta_{\UT^\mu\cap\UT_{\cR|_A}} \otimes \delta_{\UT^\mu\cap\UT_{\cR|_B}}.$$
\end{enumerate}
\end{lemma}


Somewhat surprisingly, we can also compute the structure constants for the supercharacter basis.  For $\lambda\in \nnopart(\cR)$ and $\mu\in \nnopart(\cQ)$, consider the subposet of $\Int(\cQ)$ given by
$$\Int^{\lambda}_\mu=\Big\{[i,j]\in \Int^\circ(\cQ)\mid [i,j]\in \bigcap_{[k,l]\in \mu} \cQ_{[k,l]}, [i,j]\notin\bigcap_{[k,l]\in \lambda} \cR_{[k,l]}\Big\}.$$

\begin{theorem}\label{StructureConstantsSupercharacters}
Let $A,B$ be sets with $A\cap B=\emptyset$. 
\begin{enumerate}
\item[(a)] For $\cR\in \poset(A)$, $\cQ\in \poset(B)$, $\lambda\in \nnopart(\cR)$ and $\nu\in\nnopart(\cQ)$,
$$\Inf_{A,B}(\chi^{\lambda}\otimes\chi^{\nu})=\chi^{\lambda\cup\nu}.$$
\item[(b)] For $\cR\in \poset(A\cup B)$, $\lambda\in \nnopart(\cR)$,

$$\Res_{A,B}(\chi^{\lambda})=\frac{|\UT_\lambda\cap(\UT_{\cR|_A}\times\UT_{\cR|_B})|}{|\UT_{\lambda_A}\times \UT_{\lambda_B}|}\frac{\chi^{\lambda}(1)}{\chi^{\lambda_{A}\cup\lambda_{B}}(1)}\sum_{ \nu\in \anti(\Int^\lambda_{\lambda_A})\atop \eta\in \anti(\Int^\lambda_{\lambda_B})} \chi^{\lambda_A\cup\nu}\otimes \chi^{\lambda_B\cup\eta}.$$
\end{enumerate}
\end{theorem}








\subsection{Antipodes}

For a set $B$, $\cP,\cQ\in \poset(B)$, a set composition $(I_1,\ldots, I_\ell)\vDash B$ is a $\cQ$\textbf{\emph{-factorization}} of $\cP$ if 
\begin{enumerate}
\item[(a)] $\cP|_{I_j}$ is a convex subposet of $\cQ$,
\item[(b)]  all minimal elements of $\cP|_{I_j}$ are greater than the maximal elements of $\cP|_{I_{j-1}}$.
\end{enumerate}
The number $\ell_\cQ(I_1,\ldots, I_\ell)=\ell$ is the  \textbf{\emph{length}} of the factorization.
Let
$$\Fac_\cQ(\cP)=\{\text{$\cQ$-factorizations of $\cP$}\}.$$
For example, if 
$$\cQ=\begin{tikzpicture} [scale=.3,baseline=1]
\foreach \x/\y/\z/\w in {0/0/\heartsuit/1,-.5/1/\diamondsuit/2,.5/1/\clubsuit/3,0/2/\spadesuit/4}
	\node (\w) at (\x,\y)[inner sep=0pt] {$\scriptscriptstyle\z$};
\foreach \x/\y in {1/2,1/3,2/4,3/4}
	\draw (\x) -- (\y);
\end{tikzpicture},\cP= \begin{tikzpicture} [scale=.3,baseline=1.5]
\foreach \x/\y/\z/\w in {0/0/\heartsuit/1,0/1/\diamondsuit/2,0/2/\clubsuit/3,0/3/\spadesuit/4}
	\node (\w) at (\x,\y)[inner sep=0pt] {$\scriptscriptstyle\z$};
\foreach \x/\y in {1/2,2/3,3/4}
	\draw (\x) -- (\y);
\end{tikzpicture}, \qquad\text{then}\qquad
\Fac_\cQ(\cP)=\bigg\{\Big( \heartsuit,\diamondsuit,\clubsuit,\spadesuit\Big),\Big( \begin{tikzpicture} [scale=.4,baseline=1.5]
\foreach \x/\y/\z/\w in {0/0/\heartsuit/1,0/1/\diamondsuit/2}
	\node (\w) at (\x,\y)[inner sep=0pt] {$\scriptstyle\z$};
\foreach \x/\y in {1/2}
	\draw (\x) -- (\y);
\end{tikzpicture},\clubsuit,\spadesuit\Big),\Big( \heartsuit,\diamondsuit, \begin{tikzpicture} [scale=.4,baseline=1.5]
\foreach \x/\y/\z/\w in {0/0/\clubsuit/1,0/1/\spadesuit/2}
	\node (\w) at (\x,\y)[inner sep=0pt] {$\scriptstyle\z$};
\foreach \x/\y in {1/2}
	\draw (\x) -- (\y);
\end{tikzpicture}\Big),\Big( \begin{tikzpicture} [scale=.4,baseline=1.5]
\foreach \x/\y/\z/\w in {0/0/\heartsuit/1,0/1/\diamondsuit/2}
	\node (\w) at (\x,\y)[inner sep=0pt] {$\scriptstyle\z$};
\foreach \x/\y in {1/2}
	\draw (\x) -- (\y);
\end{tikzpicture},\begin{tikzpicture} [scale=.4,baseline=1.5]
\foreach \x/\y/\z/\w in {0/0/\clubsuit/1,0/1/\spadesuit/2}
	\node (\w) at (\x,\y)[inner sep=0pt] {$\scriptstyle\z$};
\foreach \x/\y in {1/2}
	\draw (\x) -- (\y);
\end{tikzpicture}\Big)\bigg\}.$$

The following result is similar to the power-sum result in \cite{MR3273396}.

\begin{proposition} For $\cQ\in \poset(A)$,
$$S(\delta_{\UT_\cQ})=\sum_{\cP\in \poset(A)\atop \Fac_\cQ(\cP)=\{\vec{I}\}}  (-1)^{\ell_\cQ(\vec{I})-1}  \delta_{\UT_\cP}.$$
\end{proposition}


We also obtain a formula for the supercharacter basis.  For $\cR\in \poset(B)$, $\lambda\in \nnopart(\cR)$ and a set composition $\vec{A}=(A_1,\ldots, A_\ell)\vDash B$, let
\begin{align*}
\cR|_{\vec{A}} &= \cR|_{A_1}\cup \cR|_{A_2}\cup \cdots \cup  \cR|_{A_\ell}\\
\UT_{\cR|_{\vec{A}}} & = \UT_{\cR|_{A_1}}\times \cdots \times \UT_{\cR|_{A_\ell}}\\
\lambda_{\vec{A}} &=\lambda_{A_1}\cup\cdots\cup \lambda_{A_\ell}\in \nnopart(\cR|_{\vec{A}})\\
\cR_\lambda&\subseteq \cR \quad \text{where $\UT_{\cR_\lambda}=\UT_\lambda$}.
\end{align*}

 Let
\begin{equation*}
\Res^\lambda 
=\{\nu\in \nnopart(\cR)\mid (\nu-\lambda)\cap\bigcap_{[i,l]\in \lambda -\nu} \cR_{[i,l]}=\emptyset\}.
\end{equation*}
For $\lambda\in \nnopart(\cR)$, a $\cR$-factorization $(I_1,\ldots, I_\ell)\in \Fac_\cR(\cP)$ has a \textbf{\emph{$\lambda$-neutral cut}} if there exists $1\leq j\leq \ell-1$ such that 
$$\{[a,b]\mid a\in \max\{I_j\},b\in \min\{I_{j+1}\}\}\subseteq \Int^\circ(\cR_\lambda).$$
We say $\Fac_\cR(\cP)$ is \textbf{\emph{$\lambda$-atomic}} if it is nonempty and the longest element has no $\lambda$-neutral cuts.

\begin{theorem}
For $\cR\in \poset(B)$, and $\lambda\in \nnopart(\cR)$,
$$S(\chi^\lambda)=\sum_{\cP\in \poset(B)\atop \Fac_\cR(\cP)\text{ $\lambda$-atomic}} \sum_{\nu\in \nnopart(\cP)\cap \Res^\lambda} \frac{\chi^\lambda(1)}{(q-1)^{|\lambda\cap \nu|}}\Big(\sum_{{\vec{I}\in \Fac_\cR(\cP)\atop \nu_{\vec{I}} =\nu}\atop \lambda_{\vec{I}}=\lambda\cap \nu}(-1)^{\ell(\vec{I})-1}\frac{|\UT_\lambda\cap\UT_{\cR|_{\vec{I}}}|}{|\UT_{\cR|_{\vec{I}}}|}\Big) \chi^\nu.  $$
Furthermore, as polynomials in $q$, the coefficients are nonzero (though they may have integral roots).
\end{theorem}

\begin{remark}
An example that shows the coefficients can be zero is as follows.  The coefficient of $\emptyset\in \nnopart(1<2<3)$ in $S(\chi^{\{[1,3]\}})$ is 
$(q-1)(q-2)$, which is generically nonzero, but zero if $q=2$.  However, if $q$ is sufficiently large the coefficients are always nonzero.
\end{remark} 


We can apply the theorem to the specific case of trivial characters to get a pleasing result.   For $\cP\in \poset(B)$ let $\emptyset_\cP=\emptyset\in \nnopart(\cP)$.


\begin{corollary}  For $\cR\in \poset(B)$,    
$$S(\chi^{\emptyset_\cR})=\sum_{\cP\in \poset(B)\atop \Fac_\cR(\cP)=\{\vec{L}\}} (-1)^{\ell(\vec{L})-1}\chi^{\emptyset_{\cP}}.$$
\end{corollary}


\subsection{Primitives}

In \cite{MR3340544}, the authors indicate how to find the dimension of  the lie algebra of primitive elements of a (co)free Hopf monoid in each degree. For $\pattern_{\NPL}$ we go one step forward and give a full system of algebraic independent primitive elements.

For a set $B$, $\cP,\cQ\in \poset(B)$ with $\UT_\cQ\triangleleft \UT_\cP$, we say the pair $(\cP,\cQ)$  \textbf{\emph{factors}} if  there exists a nonempty, proper subset $A\subseteq B$ such that 
$$\cP|_{A}.\cP|_{B-A}=\cP\quad \text{and}\quad \cQ|_A.\cQ|_{B-A}=\cQ.
$$
If no such subset exists, we say the pair $(\cP,\cQ)$  is \textbf{\emph{atomic}}.   

Fix $a\in A$.  For $(\cR,\cQ)$ atomic, define
$$S^{(a)}_{\UT_\cQ}=\sum_{\Fac_\cQ(\cP)=\{\vec{I}\}\atop a\in I_1} (-1)^{\ell_\cQ(\vec{I})-1}\delta_{\UT_\cP}.$$ 

\begin{theorem}
Fix a functor $\select:\{\text{sets}\}\rightarrow \{\text{sets of size 1}\}$ such that $\select(A)\subseteq A$. 
Then 
$$\{S^{(\select(A))}_{\UT_\cQ}\mid \UT_\cQ\triangleleft \UT_\cR, \cR\in \poset(A), (\cR,\cQ)\text{ atomic}\}$$
is a full system of algebraically independent primitive generators of $\pattern_{\NPL}$.
\end{theorem}



In \cite{MR2289770}, Novelli--Thibon define a graded Hopf algebra 
$$\mathsf{CQSym}=\bigoplus_{n\geq 0}\mathsf{CQSym}_n $$
with $\dim(\mathsf{CQSym}_n)$ equal to the $n$th Catalan number $C_n$.  

\begin{corollary}
The Hopf algebra $\mathsf{CQSym}$ is isomorphic to canonical Hopf algebra quotient of $\pattern_{\NPL}$.  
\end{corollary}

\acknowledgements{Work of the second author is supported by a Simons collaboration grant 426594.}


\printbibliography






\end{document}



