\documentclass[ALCO,published]{cedram} %\listfiles \usepackage{latexsym} \usepackage{amssymb} %\usepackage{amsthm} \usepackage{amscd} %\usepackage{amsmath} \usepackage{tikz} \usepackage{mathabx} \usepackage{stmaryrd} %\usepackage{mathtools} \usepgflibrary{arrows} % \equalenv{lemma}[theorem]{Lemma} % \equalenv{definition}[theorem]{Definition} % \equalenv{proposition}[theorem]{Proposition} % \equalenv{corollary}[theorem]{Corollary} % \equalenv{conjecture}[theorem]{Conjecture} % \theoremstyle{definition} \equalenv{example}{exam*} \equalenv{examples}{exams*} % \theoremstyle{remark} % \equalenv{remark}{Remark}[section] % \equalenv{remarks}{Remarks}[section] % \numberwithin{equation}{section} \newenvironment{Smallmatrix}[1] {\arraycolsep=2pt\def\arraystretch{1}\footnotesize% change to whatever you need \array{#1}} {\endarray} %Special Letters \newcommand{\CC}{\mathbb{C}} \newcommand{\FF}{\mathbb{F}} \newcommand{\KK}{\mathbb{K}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\RR}{\mathbb{R}} \newcommand{\cA}{\mathcal{A}} \newcommand{\cB}{\mathcal{B}} \newcommand{\cC}{\mathcal{C}} \newcommand{\cD}{\mathcal{D}} \newcommand{\cE}{\mathcal{E}} \newcommand{\cF}{\mathcal{F}} \newcommand{\cG}{\mathcal{G}} \newcommand{\cH}{\mathcal{H}} \newcommand{\cI}{\mathcal{I}} \newcommand{\cJ}{\mathcal{J}} \newcommand{\cK}{\mathcal{K}} \newcommand{\cL}{\mathcal{L}} \newcommand{\cM}{\mathcal{M}} \newcommand{\cN}{\mathcal{N}} \newcommand{\cO}{\mathcal{O}} \newcommand{\cP}{\mathcal{P}} \newcommand{\cQ}{\mathcal{Q}} \newcommand{\cR}{\mathcal{R}} \newcommand{\cS}{\mathcal{S}} \newcommand{\cT}{\mathcal{T}} \newcommand{\cU}{\mathcal{U}} \newcommand{\cV}{\mathcal{V}} \newcommand{\cW}{\mathcal{W}} \newcommand{\cX}{\mathcal{X}} \newcommand{\cY}{\mathcal{Y}} \newcommand{\cZ}{\mathcal{Z}} \newcommand{\fkg}{\mathfrak{g}} \newcommand{\fkh}{\mathfrak{h}} \newcommand{\fkn}{\mathfrak{n}} \newcommand{\fksl}{\mathfrak{sl}} \newcommand{\fku}{\mathfrak{u}} \newcommand{\fkS}{\mathfrak{S}} \newcommand{\fkX}{\mathfrak{X}} \newcommand{\fkut}{\mathfrak{ut}} \newcommand{\bg}{\mathbf{g}} \newcommand{\bk}{\mathbf{k}} \newcommand{\bm}{\mathbf{m}} \newcommand{\bM}{\mathbf{M}} \newcommand{\bN}{\mathbf{N}} \newcommand{\bp}{\mathbf{p}} %Math Roman \newcommand{\ad}{\mathrm{ad}} \newcommand{\tr}{\mathrm{tr}} \newcommand{\Hom}{\mathrm{Hom}} \newcommand{\End}{\mathrm{End}} \newcommand{\Aut}{\mathrm{Aut}} \newcommand{\Ind}{\mathrm{Ind}} \newcommand{\GL}{\mathrm{GL}} \newcommand{\ind}{\mathrm{ind}} \newcommand{\Res}{\mathrm{Res}} \newcommand{\Inf}{\mathrm{Inf}} \newcommand{\ch}{\mathrm{ch}} \newcommand{\Irr}{\mathrm{Irr}} \newcommand{\Resf}{\mathrm{Resf}} \newcommand{\wt}{\mathrm{wt}} \newcommand{\Indf}{\mathrm{Indf}} \newcommand{\sh}{\mathrm{sh}} \newcommand{\hgt}{\mathrm{ht}} \newcommand{\diag}{\mathrm{diag}} \newcommand{\Card}{\mathrm{Card}} \newcommand{\Tr}{\mathrm{Tr}} \newcommand{\btr}{\mathrm{btr}} \newcommand{\Id}{\mathrm{Id}} \newcommand{\im}{\mathrm{im}} \newcommand{\LL}{\mathrm{LL}} \newcommand{\RL}{\mathrm{RL}} \newcommand{\UT}{\mathrm{UT}} \newcommand{\SInd}{\mathrm{SInd}} \newcommand{\Def}{\mathrm{Def}} \newcommand{\pack}{\mathrm{pack}} \newcommand{\Sym}{\mathrm{Sym}} \newcommand{\mt}{\mathrm{mt}} \newcommand{\rst}{\mathrm{rst}} \newcommand{\io}{\mathrm{io}} \newcommand{\character}{\mathrm{char}} \newcommand{\st}{\mathrm{st}} \newcommand{\supp}{\mathrm{supp}} \newcommand{\Coeff}{\mathrm{Coeff}} %\newcommand{\nst}{\mathrm{nst}} \DeclareMathOperator{\nst}{nst} \newcommand{\cl}{\mathrm{cf}} \newcommand{\scl}{\mathrm{scf}} \newcommand{\scf}{\mathrm{scf}} \newcommand{\Stab}{\mathrm{Stab}} \newcommand{\Ext}{\mathrm{Ext}} %Size \newcommand{\dd}{\displaystyle} \newcommand{\scs}{\scriptstyle} \newcommand{\scscs}{\scriptscriptstyle} %Var Variables \newcommand{\vphi}{\varphi} \newcommand{\veps}{\varepsilon} %Miscellaneous \newcommand{\spanning}{\textnormal{-span}} \newcommand{\One}{{1\hspace{-.14cm} 1}} \newcommand{\one}{{1\hspace{-.11cm} 1}} \newcommand{\entryr}[1]{\sss{\overrightarrow{\underset{\circ}{#1}}}} \newcommand{\entryl}[1]{\sss{\underleftarrow{\overset{\circ}{#1}}}} \newcommand{\larc}[1]{\hspace{-.4ex}\overset{#1}{\frown}\hspace{-.4ex}} \newcommand{\slarc}[1]{\overset{#1}{\frown}} \def\adots{\mathinner{\mkern2mu\raise0pt\hbox{.} % antidiagonal dots \mkern2mu\raise4pt\hbox{.}\mkern1mu \raise7pt\vbox{\kern7pt\hbox{.}}\mkern1mu}} %New \newcommand{\bl}{\mathrm{bl}} \newcommand{\uncr}{\mathrm{uncr}} %\newcommand{\crs}{\mathrm{crs}} \DeclareMathOperator{\crs}{crs} \newcommand{\Pqbin}[3]{\genfrac{[}{]}{0pt}{}{#1}{#2}_{#3}} \newcommand{\ggamma}{\gamma\hspace{-1.1ex}\gamma} \newcommand{\sggamma}{\gamma\hspace{-.8ex}\gamma} \newcommand{\rte}{\overset{\curvearrowright}{\varepsilon}} \newcommand{\lte}{\overset{\curvearrowleft}{\varepsilon}} \newcommand{\rse}[2]{{#1}^{\curvearrowright}_{#2}} \newcommand{\lse}[2]{{#1}^{\curvearrowleft}_{#2}} \newcommand{\bte}{\mathrm{bte}} \newcommand{\lcP}{\mathcal{P}_{\curvearrowleft}} \newcommand{\rcP}{\mathcal{P}_{\curvearrowright}} \newcommand{\lbl}{\mathrm{bl}_{\curvearrowleft}} \newcommand{\rbl}{\mathrm{bl}_{\curvearrowright}} \newcommand{\el}{\mathrm{ep}_{\curvearrowleft}} \newcommand{\er}{\mathrm{ep}_{\curvearrowright}} \newcommand{\cflt}{\mathrm{cflt}} \newcommand{\snst}{\mathrm{snst}} \newcommand{\sdim}{\mathrm{sdim}} \newcommand{\bdry}{\mathrm{bdry}} \newcommand{\rank}{\mathrm{rank}} \newcommand{\row}{\mathrm{row}} \newcommand{\col}{\mathrm{col}} \newcommand{\sq}{\mathrm{sq}} \newcommand{\levi}{\mathrm{lc}} \newcommand{\fat}{\mathrm{fat}} \newcommand{\dyck}{\mathrm{dyck}} \newcommand{\parb}{\mathrm{pb}} \newcommand{\qbin}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_{q}} \newcommand{\fcrs}{\mathrm{fcrs}} \newcommand{\loc}{\mathrm{loc}} \newcommand{\rowsupp}{\mathrm{rsp}} \newcommand{\colsupp}{\mathrm{csp}} \newcommand{\sInt}{\mathrm{sInt}} % \makeatletter % \renewcommand{\@makefnmark}{\mbox{\textsuperscript{}}} % \makeatother \allowdisplaybreaks[1] \title[Unipotent polytopes]{Supercharacter theories of type $A$ unipotent\\ radicals and unipotent polytopes} \author{\firstname{Nathaniel} \lastname{Thiem}} \address{University of Colorado \textbf{Boulder}\\ Department of Mathematics\\ Campus Box 395\\ Boulder, Colorado 80309 (USA)} \email{thiemn@colorado.edu} \thanks{The work was partially supported by NSA H98230-13-0203.} \keywords{supercharacters, integral polytopes, finite unipotent groups, unipotent radicals} \subjclass{05E10, 20C33} \begin{document} \newtheorem{fact}[cdrthm]{Fact} %\newtheorem{claim}[cdrthm]{Claim} \begin{abstract} Even with the introduction of supercharacter theories, the representation theory of many unipotent groups remains mysterious. This paper constructs a family of supercharacter theories for normal pattern groups in a way that exhibit many of the combinatorial properties of the set partition combinatorics of the full uni-triangular groups, including combinatorial indexing sets, dimensions, and computable character formulas. Associated with these supercharacter theories is also a family of polytopes whose integer lattice points give the theories geometric underpinnings. \end{abstract} \maketitle \section{Introduction} Supercharacter theory has infused the representation theory of unipotent groups with the combinatorics of set partitions. Specifically, set partitions index the supercharacters of the maximal unipotent upper-triangular subgroup $\UT$ of the finite general linear group $\GL$ \cite{An,Ya}, and similar theories exist for the maximal unipotent subgroups of other finite reductive groups \cite{AFN,Aw}. However, while there are supercharacter theories for other unipotent groups, they do not generally exhibit this computable and combinatorial nature. This paper seeks to define a natural family of supercharacter theories for the normal pattern subgroups of $\UT$. As an added bonus, we not only obtain a combinatorial description for these theories, but also gain geometric underpinnings coming from a family of integral polytopes. Diaconis--Isaacs defined a supercharacter theory of a finite group $G$ as a direct analogue of its character theory, where they replacing conjugacy classes with superclasses and irreducible characters with supercharacters \cite{DI}. Their approach is based on Andr\'e's adaption of the Kirillov orbit method to study $\UT$, and the underlying axioms are calibrated to preserve as many properties of irreducible characters and conjugacy classes as possible. For example, the supercharacters are an orthogonal (but not generally orthonormal) basis for the space of functions that are constant on superclasses. This definition has given us new approaches to groups whose representation theories are known to be difficult (eg. unipotent groups). Not only can these new theories be combinatorially striking \cite{AIM}, but they can also be used in place of the usual character theory \cite{ADS} in applications, they give a starting point in studying difficult theories \cite{DG}, or give character theoretic foundations for number theoretic identities (eg. \cite{BBFGGKMTS,FoGK}). The supercharacter theories of this paper are fundamentally based on Andr\'e's original construction for $\UT$ \cite{An} and Diaconis--Isaacs' later generalization to algebra groups \cite{DI}. These constructions use two-sided orbits in the dual space $\fkut^*$ of the corresponding Lie algebra $\fkut$ to construct the supercharacters. In the algebra group case the group $\UT$ acts on $\fkut^*$ by left and right multiplication (technically pre-composition by left and right multiplication on $\fkut$). In this paper we modify this construction by instead acting by parabolic subgroups of $\GL$. The resulting theory is coarser but far more combinatorial in nature. In particular, we obtain statistics such as dimension, nestings and crossings that generalize the corresponding set partition statistics \cite{CPKR}, and in Theorem \ref{FullFormula} we give a character formulas with a ``factorization'' analogous to the well-known $\UT$-cases. For each supercharacter theory there is an associated polytope whose integer lattice points index the supercharacters of the theory. Thus, the supercharacter theories could in principle give a categorified version of the Ehrhart polynomials of these polytopes. These polytopes include all transportation polytopes \cite{DK}, and may be viewed as a family of subfaces of transportation polytopes. This point of view not only gives a geometric approach to these supercharacter theories, but it also re-interprets set partitions as vertices of a polytope. Since I am unaware of other contexts where these polytopes may have been studied, I will refer to them as \emph{unipotent polytopes}. At present we do not understand the significance of this geometry in the representation theory of unipotent groups, and this seems to be a promising direction for future work. Section \ref{SectionPreliminaries} reviews some of the background material on unipotent groups and supercharacter theories. Section \ref{SectionGroups} defines the particular unipotent groups we will focus on. Pattern groups arise naturally in context of groups of Lie type, since they are unipotent groups invariant under conjugation by a maximal split torus. The unipotent groups we consider are effectively a block-analogue to pattern groups where we define a notion of invariance under the action of a fixed Levi subgroup. Section \ref{SectionSupercharacterTheories} shows how to use this Levi subgroup to construct supercharacter theories for the group, and shows how the supercharacters (and superclasses) are indexed by the $\ZZ_{\geq 0}$-lattice points of a polytope. Section \ref{SectionSupercharacterFormulas} computes the supercharacter formulas for these theories, and discusses some consequences of these results. In addition to teasing out the geometric implications of the underlying polytopes, this paper also gives a framework for studying random walks on the integer lattice points of unipotent polytopes, and representation theoretic Hopf structures on them. However, both these directions are beyond the scope of this paper. \section{Preliminaries} \label{SectionPreliminaries} This paper is primarily concerned with unipotent subgroups of the finite general linear groups. It is standard to index the rows and columns of the corresponding matrices by the set $\{1,2,\ldots, N\}$ in the usual total order, but recent work \cite{ABT} has suggested that it is better to instead allow an arbitrary set of size $N$ to index the rows and columns and fix a total order $\cN$ on that set. However, the paper may be easily read with $\cN$ as the total order $1<2<\cdots < N$. This section reviews the relevant unipotent groups, a combinatorial interpretation of normality, and some of the standard supercharacter theories for these groups. The last section gives a quick refresher of $q$-binomial coefficients. \subsection{Subgroups of Lie type} Let $\cN$ be a fixed total order of a finite set with $N$ elements and fix a finite field $\FF_q$ with $q$ elements. Let $\GL_\cN$ denote the finite general linear group on matrices with rows and columns indexed by our finite set in the order dictated by $\cN$. If $\mathrm{char}(\FF_q)=p$, then a Sylow $p$-subgroup of $\GL_\cN$ is the subgroup of unipotent upper-triangular matrices $$\UT_\cN=\{g\in \GL_\cN\mid (g-\Id_N)_{ij}\neq 0 \text{ implies } i\prec_\cN j\}.$$ The normalizer in $\GL_\cN$ of $\UT_\cN$ is the Borel subgroup $$B_\cN=\{g\in \GL_\cN\mid g_{ij}\neq 0 \text{ implies } i\preceq_\cN j\}=N_{\GL_\cN}(\UT_\cN).$$ Let $$\fkut_\cN=\UT_\cN-\Id_N$$ denote the corresponding nilpotent $\FF_q$-algebra. If $\fkn\subseteq \fkut_\cN$ is any subalgebra, then we obtain a subgroup $\Id_N+\fkn\subseteq \UT_\cN$ called and \emph{algebra subgroup}. If $\cP$ is a subposet of $\cN$ on the same underlying set, then we call the algebra subgroup $$\UT_\cP=\Id_N+\fkut_\cP\subseteq \UT_\cN, \qquad \text{where} \qquad \fkut_\cP=\{x\in \fkut_\cN\mid x_{ij}\neq 0 \text{ implies } i\prec_{\cP} j\},$$ a \emph{pattern subgroup} of $\UT_\cN$. Note that transitivity in the poset $\cP$ exactly implies that this $\UT_\cP$ is closed under multiplication. \subsection{Normal posets}\label{SectionNormalPosets} In general, a subposet $\cP$ of a poset $\cQ$ does not give a normal subgroup $\UT_\cP$ of $\UT_\cQ$. However, there is a straight-forward condition on the poset that characterizes this group theoretic condition: a subposet $\cP\subseteq \cQ$ is \emph{normal} if $j\prec_\cP k$ implies $i\prec_\cP k$ and $j\prec_\cP l$ for all $i\prec_{\cQ}j$ and $k\prec_\cQ l$. In this case, we write $\cP\triangleleft \cQ$. Alternatively, if $\sInt(\cQ)$ is the strict interval poset on the set $\{(i,j)\mid i\prec_\cQ j\}$ given by $(j,k)\preceq_{\sInt(\cQ)} (i,l)$ if and only if $i\preceq_\cQ j\prec_\cQ k\preceq_{\cQ} l$, then $\cP$ is normal in $\cQ$ if and only if $\sInt(\cP)$ is a dual order ideal of $\sInt(\cQ)$. In fact, in this case, $\sInt(\cP)$ exactly gives the coordinates of the Ferrer's shape $F$ or the coordinates allowed to be nonzero in $\UT_{\cP}$. For example, $$ \begin{tikzpicture}[scale=1,baseline=1cm] \foreach \x/\y/\z in {0/0/1,1/1/2,0/1/3,0/2/4,1/2/5} \node (\z) at (\x,\y) [inner sep = 1pt] {$\scs\z$}; \foreach \a/\b in {1/3,2/4,2/5,3/4,3/5} \draw (\a) -- (\b); \end{tikzpicture} \subseteq \begin{tikzpicture}[scale=.7,baseline=1cm] \foreach \x/\y/\z in {0/0/1,0/1/2,0/2/3,0/3/4,0/4/5} \node (\z) at (\x,\y) [inner sep = 1pt] {$\scs\z$}; \foreach \a/\b in {1/2,2/3,3/4,4/5} \draw (\a) -- (\b); \end{tikzpicture} \quad \text{in interval posets is}\quad \begin{tikzpicture}[scale=1,baseline=2cm] \foreach \x/\y in {1/3,1/4,1/5,2/4,2/5,3/4,3/5} \fill[gray!20!white] (\x+\y,\y-\x)+(-.6,-.3) rectangle ++(.6,.3); \foreach \x/\y in {1/2,1/3,1/4,1/5,2/3,2/4,2/5,3/4,3/5,4/5} \node (\x\y) at (\x+\y,\y-\x) {$(\x,\y)$}; \draw (12) -- (13) -- (14) -- (15) -- (25) -- (35) -- (45); \draw (13) -- (23) -- (24) -- (25); \draw (35) -- (34) -- (24) -- (14); \end{tikzpicture} $$ where the boxed entries are correspond to the subposet. There are a number of combinatorial interpretations of normal posets of the total order $\cN$. For $N\in \ZZ_{\geq 0}$, let $D_N$ denote the Ferrer's shape $(N-1,N-2,\ldots, 1)$, where we right justify the rows. For example, $$D_5=\begin{tikzpicture}[scale=.3,baseline=-.5cm] \foreach \y in {0,...,3} {\foreach \x in {\y,...,3} \draw (\x,-\y)+(-.5,-.5) rectangle ++(.5,.5);} \end{tikzpicture}\ .$$ \begin{proposition}\label{NormalPosetInterpretations} There are bijections $$\begin{array}{c@{\ }c@{\ }c@{\ }c@{\ }c}\left\{\begin{array}{@{}c@{}} \text{Dyck paths from}\\ \text{ $(0,0)$ to $(2N,-2N)$} \end{array}\right\} & \longleftrightarrow & \left\{\begin{array}{@{}c@{}} \text{normal sub-}\\ \text{posets of $\cN$}\end{array}\right\} & \longleftrightarrow & \left\{\begin{array}{@{}c@{}} \text{sub-Ferrers}\\ \text{shapes of $D_N$}\end{array}\right\}\\ d_\cP & \mapsfrom & \cP & \mapsto & F_\cP.\end{array}$$ where $(2i-1,2j-1)$ is NorthEast of $d_\cP$ if and only if $i\prec_{\cP} j$ if and only if $(i,j)\in F_\cP$. \end{proposition} \begin{example} For example, if $2N=10$, then $$ \begin{tikzpicture}[scale=.3,baseline=-1.5cm] \fill[gray!20!white] (7,-1)+(-3,-1) rectangle ++(3,1); \fill[gray!20!white] (8,-4)+(-2,-2) rectangle ++(2,2); \foreach \x in {0,...,5} {\foreach \y in {0,...,\x} \node[gray] (\x\y) at (2*\x,-2*\y) [inner sep = -1pt] {$\scscs\bullet$}; } \foreach \x in {1,...,4} {\foreach \y in {1,...,\x} \node at (2*\x+1,-2*\y+1) {$\bullet$}; } \foreach \x in {1,...,5} \node[gray] at (2*\x-1,-2*\x+1) {$\scs\x$}; \foreach \a/\b/\c/\d in {0/0/2/0,2/0/2/1,2/1/3/1,3/1/3/3,3/3/5/3,5/3/5/5} \draw (\a\b)--(\c\d); \end{tikzpicture} \quad\longleftrightarrow\quad \begin{tikzpicture}[scale=1,baseline=1cm] \foreach \x/\y/\z in {0/0/1,1/1/2,0/1/3,0/2/4,1/2/5} \node (\z) at (\x,\y) [inner sep = 1pt] {$\scs\z$}; \foreach \a/\b in {1/3,2/4,2/5,3/4,3/5} \draw (\a) -- (\b); \end{tikzpicture} \quad\longleftrightarrow \quad \begin{tikzpicture}[scale=.5,baseline=-1cm] \foreach \y in {0,...,3} {\foreach \x in {\y,...,3} \draw[gray] (\x,-\y)+(-.5,-.5) rectangle ++(.5,.5);} \foreach \x/\y in {1/0,2/0,3/0,2/1,3/1,2/2,3/2} \draw[thick] (\x,-\y)+(-.5,-.5) rectangle ++(.5,.5); \end{tikzpicture}\ $$ where the shaded region accentuates the relevant points NorthEast of the Dyck path. \end{example} \subsection{Supercharacter theories of unipotent groups}\label{SectionSupercharacters} Supercharacter theories for finite groups were first defined in \cite{DI}, generalizing work by Andr\'e studying representations of $\UT_\cN$ (a series of papers starting with \cite{An}). There are numerous equivalent formulations of a supercharacter theory, but the following seems most suitable for the purposes of this paper. A \emph{supercharacter theory} $(\cK,\cX)$ of a finite group $G$ is a pair, where $\cK$ is a partition of $G$ and $\cX$ is a set of characters, such that \begin{itemize} \item[(SC0)] The number of blocks of $\cK$ is the same as the number of elements in $\cX$. \item [(SC1)] Each block $K\in \cK$ is a union of conjugacy classes. \item [(SC2)] The set $$\cX\subseteq \{\theta:G\rightarrow \CC\mid \theta(g)=\theta(h), g,h\in K, K\in \cK\}.$$ \item [(SC3)] Each irreducible character of $G$ is the constituent of exactly one element in~$\cX$. \end{itemize} We refer to the blocks of $\cK$ as \emph{superclasses} and the elements of $\cX$ as \emph{supercharacters}. While we have many ways of constructing supercharacter theories, general constructions are not well-understood. That is, given a finite groups, it is a hard problem to determine its supercharacter theories. Some groups have remarkably few supercharacter theories, such as the symplectic group $\mathrm{Sp}_6(\FF_2)$ with exactly 2 \cite{BLLW}, and some groups have surprisingly many, such as $C_3\times C_6$ with 297 distinct supercharacter theories. However, for this paper we follow the basic strategy laid out by \cite{DI} for algebra groups. Let $\Id_N+\fkn\subseteq \UT_\cN$ be an algebra subgroup. Then $\Id_N+\fkn$ acts on both $\fkn$ and its vector space dual $\fkn^*$ by left and right multiplication, where $$(a\cdot y\cdot b)(x)=y(a^{-1}xb^{-1}), \qquad \text{for $a,b\in \Id_N+\fkn$, $x\in \fkn$, $y\in \fkn^*$.}$$ Fix a nontrivial homomorphism $\vartheta:\FF_q^+\rightarrow \GL_1(\CC)\cong \CC^\times$. In this situation \cite{DI} define a supercharacter theory given by \begin{itemize} \item \textit{$AG$-superclasses of $\Id_N+\fkn$}: The set partition $\{\Id_N+(\Id_N+\fkn)x(\Id_N+\fkn)\mid x\in \fkn\}$ of $\Id_N+\fkn$. \item \textit{$AG$-supercharacters of $\Id_N+\fkn$}: The set of characters $$\Big\{\chi_{AG}^y=\frac{|(\Id_N+\fkn)y|}{|(\Id_N+\fkn)y(\Id_N+\fkn)|} \sum_{z\in (\Id_N+\fkn)y(\Id_N+\fkn)} \vartheta\circ z\mid y\in \fkn^*\Big\}.$$ \end{itemize} \begin{remark} In the case where $\fkn=\fkut_\cN$, this supercharacter theory gives a nice combinatorial theory developed algebraically by Andr\'e \cite{An} and more combinatorially by Yan \cite{Ya}. However, in general even this supercharacter theory may be wild for algebra subgroups. In fact, we do not even understand it for pattern subgroups. \end{remark} For the purposes of our generalization, there is a slight coarsening of the $AG$-supercharacter theory for $\UT_\cN$ called the $B_\cN$-supercharacter theory that exists because $\fkut_\cN$ and $\fkut_\cN^*$ are in fact permuted by left and right multiplication by $B_\cN$. \begin{itemize} \item \textit{$B_\cN$-superclasses of $\UT_\cN$}: The set partition $\{\Id_N+B_\cN x B_\cN\mid x\in \fkut_\cN\}$ of $\UT_\cN$. \item \textit{$B_\cN$-supercharacters of $\UT_\cN$}: The set of characters $$\Big\{\chi_{\cN}^y=\sum_{z\in B_\cN y B_\cN} \vartheta\circ z\mid y\in \fkut_\cN^*\Big\}.$$ \end{itemize} In this case, the supercharacters and superclasses are indexed by set partitions of the underlying set. In the following sections it is best to view set partitions as functions $\lambda:\sInt(\cN)\rightarrow \{0,1\}$ such that for $\lambda_{ik}=1=\lambda_{jl}$, we have $i=j$ if and only if $k=l$ (or placements of non-attacking rooks on a triangular chessboard). The primary purpose of this paper is to generalize this set-up to nice families of pattern groups. \begin{remark} This version of the supercharacters is scaled slightly from the conventional choice. That is, usually each character $\chi_{\cN}^y$ is multiplied by $$ \frac{|\UT_{\cN} y|}{|\UT_{\cN} y \UT_{\cN}|}.$$ This scaling removes some excessive multiplicities. However, in this paper the ``best" scaling factor for the supercharacters below is not clear, so the paper is written with them removed entirely. This choice implies that in fact $$\chi_{\cN}^y=\sum_{\psi\in X_y} \psi(1)\psi$$ for some set of irreducible characters $X_y$. \end{remark} \subsection{$q$-Binomials and weights} The symbol $q$ will generally be the size of a finite field, but for this section may treat $q$ as an indeterminate. For $n,k\in\ZZ_{\geq 0}$, let $$\qbin{n}{k}=\frac{[n]!}{[k]![n-k]!},\qquad \text{where}\qquad [n]!=[n][n-1]\cdots [2][1] \quad \text{and}\quad [n]=\frac{q^n-1}{q-1}.$$ In this subsection, we review some other interpretations and results associated with these $q$-binomial coefficients. Let $S_n$ be the symmetric group on $n$ letters. Then $$[n]!=\sum_{w\in S_n} q^{\mathrm{inv}(w)},\qquad \text{where}\qquad \mathrm{inv}(w)=\#\{1\leq iw(j)\}.$$ In particular, it will be useful to note that since $[n]!$ is palindromic of degree $\binom{n}{2}$, \begin{equation}\label{InvolutionSum} \sum_{w\in S_n} \frac{1}{q^{\mathrm{inv}(w)}}=\frac{1}{q^{\binom{n}{2}}} [n]!. \end{equation} Let $B\subseteq C$, where $C$ is a set with a total order $\cC$. Let $$\begin{array}{rccc} \wt^\uparrow_B:&\{A\subseteq C\} & \longrightarrow & \ZZ_{\geq 0}\\ & A & \mapsto & \#\{(a,b)\in A\times B\mid a\prec_\cC b\},\end{array}$$ and for $A,B\subseteq C$, let $$\wt^\downarrow_B(A)=\wt^\uparrow_A(B).$$ Then \begin{equation}\label{WeightqBinomial} \qbin{n}{k}=q^{\binom{k}{2}}\sum_{A\subseteq \{1,\ldots, n\}\atop |A|=k} q^{\wt_{\{1,\ldots,n\}}^\uparrow (A)}=q^{\binom{k}{2}}\sum_{A\subseteq \{1,\ldots, n\}\atop |A|=k} q^{\wt_{\{1,\ldots,n\}}^\downarrow (A)}. \end{equation} \section{A parabolic generalization of pattern subgroups} \label{SectionGroups} In this section, we build a family of pattern subgroups of $\UT_\cN$; they will all be normal, and each will have a family of supercharacter theories, defined in Section \ref{SectionSupercharacterTheories}. The choice of a subgroup with an associated supercharacter theory will determine a polytope, giving the theory a geometric foundation. \subsection{Parabolic posets and $\UT_\beta$} We begin by defining a family of unipotent groups that appear naturally in the theory of reductive groups, the unipotent radicals of parabolic subgroups. It turns out that for $\GL_\cN$, these unipotent groups are pattern groups and their associated posets are easy to characterize. In the Section \ref{SectionSupercharacterTheories}, each unipotent radical $\UT_\beta$ will determine a family of supercharacter theories. A subposet $\cQ$ is \emph{parabolic} in $\cN$ if there exists a set composition $(\cQ_1, \cQ_2, \ldots, \cQ_\ell)$ of the underlying set such that $a\prec_\cQ b$ if and only if $a\in \cQ_i$ and $b\in \cQ_j$ with $i,gray] (0,0,0) -- (6,0,0); \draw[->,gray] (0,0,0) -- (0,6,0); \draw[->,gray] (0,0,0) -- (0,0,6); \draw[gray] (0,0,1) -- (4,0,1) -- (0,4,1) -- (0,0,1); \draw[gray] (3,0,0) -- (3,0,2) -- (3,2,0) -- (3,0,0); \draw[gray] (0,2,0) -- (3,2,0) -- (0,2,3) -- (0,2,0); \draw (0,0,1) -- (3,0,1) -- (3,1,1) -- (2,2,1) -- (0,2,1) -- (0,0,1); \draw (3,0,1) -- (3,0,0) -- (3,2,0) -- (3,1,1); \draw (0,2,1) -- (0,2,0) -- (3,2,0) -- (2,2,1); \node at (.75,6,0) {$\scs x_{15}$}; \node at (6,-.5,0) {$\scs x_{25}$}; \node at (0,-.5,6) {$\scs x_{35}$}; \end{tikzpicture} $$ (E2)\enspace% In general, the unipotent polytopes $(\beta,\cP)$ where the corresponding Ferrer's shape $F$ is a rectangle have transportation polytopes as distinguished faces (points where row and column sums all equal their bound). They are a subfamily corresponding to abelian unipotent groups. In this case, the bounds on the row sums and and the bounds on the column sums are independent. \end{examples} \end{samepage} Unipotent polytopes match up with Levi compatible sub-posets in the following way. \begin{proposition} Let $\cN$ be a total order on a set with $N$ elements and let $\beta\vDash N$. Then the following are equivalent: \begin{enumerate}[\textup{(P\arabic*)}] \item $(\beta,\cP)$ is a unipotent polytope, \item $\fat_{\beta}(\cP)\triangleleft_\levi \bdry^{-1}(\beta)$, \item $P_\beta\subseteq N_{\GL_\cN(q)}(\UT_{(\beta,\cP)}).$ \end{enumerate} \end{proposition} \begin{proof} Let $\cQ=\bdry^{-1}(\beta)$, and let $\cL$ be the usual total order on $\{1,\ldots, \ell(\beta)\}$. If $(\beta,\cP)$ is a unipotent polytope, then by definition $\cP\triangleleft \cL$. But then by Proposition \ref{FatMap}, $\fat_\beta(\cP)\subseteq_\levi\fat_\beta(\cL)=\cQ$, and $\fat_\beta$ preserves normality. If $\fat_\beta(\cP)\triangleleft_\levi \cQ$, then $\UT_{(\beta,\cP)}\triangleleft \UT_\beta$ and $L_\beta\subseteq N_{\GL_\cN(q)}(\UT_{(\beta,\cP)})$. Thus, $$P_\beta=L_\beta\ltimes \UT_\beta\subseteq N_{\GL_\cN(q)}(\UT_{(\beta,\cP)}).$$ If $P_\beta\subseteq N_{\GL_\cN(q)}(\UT_{(\beta,\cP)}),$ then $\UT_{(\beta,\cP)}\triangleleft\UT_\beta$, so $\fat_\beta(\cP)\triangleleft \cQ=\fat_\beta(\cL)$ and since $\fat_\beta$ preserves normality, $\cP\triangleleft \cL$. \end{proof} \begin{remark} For a fixed total order $\cN$ with $N$ elements, the function $$\begin{array}{c@{\ }c@{\ }c} \left\{\begin{array}{@{}c@{}} \text{unipotent polytopes}\\ \text{$(\beta,\cP)$ with $|\beta|=N$}\end{array} \right\} & \longrightarrow & \left\{\begin{array}{@{}c@{}} \text{normal sub-}\\ \text{groups of $\UT_\cN$}\end{array} \right\} \\ (\beta,\cP) & \mapsto & \UT_{(\beta,\cP)}\end{array}$$ is not injective, since, for example, $$\UT_{((1^4), \begin{tikzpicture}[scale=.5,baseline=.2cm] \foreach \x/\y/\z in {0/0/1,1/0/2,0/1/3,1/1/4} \node (\x\y) at (\x,\y) [inner sep=1pt] {$\scscs\z$}; \draw (00) -- (01); \draw (00) -- (11); \draw (10) -- (01); \draw (10) -- (11); \end{tikzpicture})}=\left[\begin{array}{cccc} 1 & 0 & \ast & \ast\\ 0 & 1 & \ast & \ast\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\end{array}\right]=\UT_{((2,2), \begin{tikzpicture}[scale=.5,baseline=.2cm] \foreach \x/\y/\z in {0/0/1,0/1/2} \node (\x\y) at (\x,\y) [inner sep=1pt] {$\scscs\z$}; \draw (00) -- (01); \end{tikzpicture})}. $$ On the other hand, for a fixed $\beta\vDash N$ $$\begin{array}{c@{\ }c@{\ }c} \left\{\begin{array}{@{}c@{}} \text{unipotent poly-}\\ \text{topes $(\beta,\cP)$}\end{array} \right\} & \longrightarrow & \left\{\begin{array}{@{}c@{}} \text{normal sub-}\\ \text{groups of $\UT_\cN$}\end{array}\right\} \\ (\beta,\cP) & \mapsto & \UT_{(\beta,\cP)}\end{array}$$ is injective. Note that $\UT_\cN$ has many normal subgroups that are not pattern subgroups, so this function is not surjective; for example, any proper nontrivial subgroup of the center ($\cong \FF_q^+$) is not a pattern subgroup. \end{remark} \section{Families of parabolic supercharacter theories}\label{SectionSupercharacterTheories} The data in a unipotent polytope $(\beta,\cP)$ also gives a natural supercharacter theory to a corresponding unipotent group $\UT_{(\beta,\cP)}$. This section describes this theory, and shows that the supercharacters/superclasses are indexed by the integer lattice points contained in the polytope $(\beta,\cP)$. \subsection{Supercharacter theory definition} Let $(\beta,\cP)$ be a unipotent polytope with $\beta\vDash N$. Then $$\fkut_{(\beta,\cP)}=\UT_{(\beta,\cP)}-\Id_{N}$$ is an $\FF_q$-vector space with basis $$\{e_{ij}\mid i\prec_{\fat_\beta(\cP)} j\},\qquad \text{where}\qquad (e_{ij})_{kl}=\delta_{(i,j),(k,l)}.$$ The dual space $$\fkut_{(\beta,\cP)}^*=\Hom_{\FF_q}(\fkut_{(\beta,\cP)},\FF_q)$$ has dual basis $$\left\{\begin{array}{r@{\ }c@{\ }c@{\ }c}e_{ij}^*:&\fkut_{(\beta,\cP)} &\rightarrow &\FF_q\\ & x & \mapsto & x_{ij}\end{array}\ \bigg| i\prec_{\fat_\beta(\cP)} j\right\}.$$ The group $P_\beta$ acts on both $\fkut_{(\beta,\cP)}$ and $\fkut_{(\beta,\cP)}^*$ by left and right multiplication, where $$(a\cdot y \cdot b)(x)=y(a^{-1}xb^{-1}), \quad \text{for $x\in \fkut_{(\beta,\cP)}, y\in \fkut_{(\beta,\cP)}^*, a,b\in P_\beta$}.$$ These actions give a natural supercharacter theory for $\UT_{(\beta,\cP)}$. \begin{itemize} \item \textit{$P_\beta$-superclasses of $\UT_{(\beta,\cP)}$}: The set partition $\{P_\beta x P_\beta+\Id_{N}\mid x\in \fkut_{(\beta,\cP)}\}$ of $\UT_{(\beta,\cP)}$. \item \textit{$P_\beta$-supercharacters of $\UT_{(\beta,\cP)}$}: The characters \begin{equation} \label{SupercharacterDefinition} \{\chi_{\beta}^{y}\mid P_\beta y P_\beta\in P_\beta\backslash \fkut_{(\beta,\cP)}^*/P_\beta\}, \quad \text{where}\quad \chi_{\beta}^{y}=\sum_{z\in P_\beta y P_\beta}\vartheta\circ z.\end{equation} \end{itemize} \begin{proposition} If $(\beta,\cP)$ is a unipotent polytope, then the $P_\beta$-superclasses and the $P_\beta$-supercharacters form a supercharacter theory of $\UT_{(\beta,\cP)}$. \end{proposition} \begin{proof} The following conditions are straight-forward to check: \begin{itemize} \item[(SC0)] The fact that the number of $G$ orbits on a vectors space $V$ is the same as the number of $G$-orbits on $V^*$ shows that there are an equal number of superclasses and supercharacters (see \cite[Lemma 4.1]{DI} for an analogous argument). \item[(SC1)] The superclasses are unions of conjugacy classes. \item[(SC2)] The supercharacters are constant on superclasses. \end{itemize} It therefore suffices to show that $P_\beta$-supercharacters are in fact orthogonal characters (rather than just class functions) that collectively have the irreducibles of $\UT_{(\beta,\cP)}$ as constituents. By definition, \begin{align} \chi_{\beta}^y & = \sum_{z\in P_\beta y P_\beta} \vartheta\circ z \notag\\ &=\sum_{\UT_{(\beta,\cP)}z' \UT_{(\beta,\cP)}\in P_\beta (\UT_{(\beta,\cP)}y \UT_{(\beta,\cP)}) P_\beta}\bigg( \sum_{z\in \UT_{(\beta,\cP)}z' \UT_{(\beta,\cP)}}\vartheta\circ z\bigg)\notag\\ &= \sum_{\UT_{(\beta,\cP)}z' \UT_{(\beta,\cP)}\in P_\beta (\UT_{(\beta,\cP)}y \UT_{(\beta,\cP)}) P_\beta} \frac{|\UT_{(\beta,\cP)} z' \UT_{(\beta,\cP)}|}{|\UT_{(\beta,\cP)} z'|}\chi_{AG}^{z'}.\label{AGSupercharacterDecomposition} \end{align} Thus, $\chi_{\beta}^y$ is a $\ZZ_{\geq 0}$-linear combination of characters and so is also a character. Furthermore, since each $AG$-supercharacter appears in a unique $P_\beta$-supercharacter, the $P_\beta$-supercharacters are orthogonal and collectively have all the irreducibles as constituents. \end{proof} \begin{remarks}\hfill\break\indent (R1)\enspace The unipotent polytope $((1^N),\cN)$ recovers the $B_\cN$-supercharacter theory of $\UT_\cN$ from Section \ref{SectionSupercharacters} (also studied in \cite{BT}). (R2)\enspace Since $B_\cN=P_{(1^{N})}\subseteq P_\beta$, we can coarsen (\ref{AGSupercharacterDecomposition}) to get \begin{equation} \label{BSupercharacterDecomposition} \chi_{\beta}^y = \sum_{P_{(1^{N})}z' P_{(1^{N})}\subseteq P_\beta y P_\beta} \chi_{(1^{N})}^{z'}. \end{equation} This formula will be more useful below since the $\chi_{(1^{N})}^{z'}$ have nicer character formulas. (R3)\enspace In practice, one often scales the supercharacters by some factor that divides the multiplicities of the irreducible constituents. In this case, there does not seem to be an obvious choice, so we have omitted the scaling factor. However, (\ref{AGSupercharacterDecomposition}) implies that one may divide by $$\frac{|\UT_{(\beta,\cP)} y \UT_{(\beta,\cP)}|}{|\UT_{(\beta,\cP)} y|}$$ and still have characters. (R4)\enspace An advantage of our definition of the supercharacters (without any scaling) is that it is easy to construct the corresponding modules. For $y\in \fkut_{(\beta,\cP)}^*$, define the $\UT_{(\beta,\cP)}$-module $M^y$ by a $\CC$-basis $$\{\boxed{z}\mid z\in P_\beta y P_\beta\}$$ with an action $$u \cdot\boxed{z}= \vartheta\circ z(u^{-1}-\Id_{|\beta|}) \boxed{uz} \qquad \text{for $u\in \UT_{(\beta,\cP)}$, $z\in P_\beta y P_\beta$}.$$ (R5)\enspace The paper \cite{MT} observes that when a pattern subgroup $\UT_\cP$ is normal in $\UT_\cN$, then it is in fact a union of $AG$-superclasses (in some sense ``supernormal"). In this sense, the $P_\beta$-supercharacter theory makes $\UT_{(\beta,\cP)}$ a supernormal subgroup of $\UT_\beta$. %\end{enumerate} \end{remarks} \subsection{The combinatorics of the indexing sets} For a unipotent polytope $(\beta,\cP)$ with $F_\cP$ as in Proposition \ref{NormalPosetInterpretations}, let $$\cT_\cP^\beta= \Big\{\begin{array}{@{}r@{}c@{\ }c @{\ }c@{}}\lambda: & F_\cP &\rightarrow &\ZZ_{\geq 0}\\ & (i,j) & \mapsto & \lambda_{ij}\end{array}\ \Big|\ \sum_{k\atop (j,k)\in F_\cP} \lambda_{jk}, \sum_{i\atop (i,j)\in F_\cP} \lambda_{ij}\leq \beta_j,1\leq j\leq \ell\Big\}$$ be the set of $\ZZ_{\geq 0}$-lattice points contained in or on $(\beta,\cP)$. \begin{examples}\hfill\break\indent (E1)\enspace% The set $$\cT_{ \begin{tikzpicture}[scale=.3] \foreach \x/\y/\z in {0/0/1,2/0/2,1/1/3} \node (\z) at (\x,\y) [inner sep=1pt] {$\scscs \z$}; \foreach \a/\b in {1/3,2/3} \draw (\a) -- (\b); \end{tikzpicture} }^{(4,1,2)}=\left\{ \begin{tikzpicture}[scale=.4,baseline=0cm] \foreach \x/\y/\z in {-1/1/4,0/0/1,1/-1/2} {\fill[gray!20!white] (\x,\y) +(-.5,-.5) rectangle ++(.5,.5); \node at (\x,\y) {$\scs\z$};} \foreach \x/\y/\num in { 1/1/0, 1/0/0} { \draw (\x,\y) +(-0.5,-0.5) rectangle ++(0.5,0.5); \draw (\x,\y) node {$\scs\num$}; } \end{tikzpicture},\ \begin{tikzpicture}[scale=.4,baseline=0cm] \foreach \x/\y/\z in {-1/1/4,0/0/1,1/-1/2} {\fill[gray!20!white] (\x,\y) +(-.5,-.5) rectangle ++(.5,.5); \node at (\x,\y) {$\scs\z$};} \foreach \x/\y/\num in { 1/1/1, 1/0/0} { \draw (\x,\y) +(-0.5,-0.5) rectangle ++(0.5,0.5); \draw (\x,\y) node {$\scs\num$}; } \end{tikzpicture},\ \begin{tikzpicture}[scale=.4,baseline=0cm] \foreach \x/\y/\z in {-1/1/4,0/0/1,1/-1/2} {\fill[gray!20!white] (\x,\y) +(-.5,-.5) rectangle ++(.5,.5); \node at (\x,\y) {$\scs\z$};} \foreach \x/\y/\num in { 1/1/0, 1/0/1} { \draw (\x,\y) +(-0.5,-0.5) rectangle ++(0.5,0.5); \draw (\x,\y) node {$\scs\num$}; } \end{tikzpicture},\ \begin{tikzpicture}[scale=.4,baseline=0cm] \foreach \x/\y/\z in {-1/1/4,0/0/1,1/-1/2} {\fill[gray!20!white] (\x,\y) +(-.5,-.5) rectangle ++(.5,.5); \node at (\x,\y) {$\scs\z$};} \foreach \x/\y/\num in { 1/1/1, 1/0/1} { \draw (\x,\y) +(-0.5,-0.5) rectangle ++(0.5,0.5); \draw (\x,\y) node {$\scs\num$}; } \end{tikzpicture},\ \begin{tikzpicture}[scale=.4,baseline=0cm] \foreach \x/\y/\z in {-1/1/4,0/0/1,1/-1/2} {\fill[gray!20!white] (\x,\y) +(-.5,-.5) rectangle ++(.5,.5); \node at (\x,\y) {$\scs\z$};} \foreach \x/\y/\num in { 1/1/2, 1/0/0} { \draw (\x,\y) +(-0.5,-0.5) rectangle ++(0.5,0.5); \draw (\x,\y) node {$\scs\num$}; } \end{tikzpicture},\ \right\}$$ where the entries shaded in gray give the bounds for each row and column. (E2)\enspace If $\beta=(1^{m},n)$ with $m\leq n$ and $$\cP= \begin{tikzpicture}[scale=.5,baseline=.5cm] \foreach \x/\y/\z in {0/0/1,1/0/2,4/0/{m},2/2/{m+1}} \node (\x) at (\x,\y) [inner sep=1pt] {$\scs \z$}; \foreach \a/\b in {0/2,1/2,4/2} \draw (\a) -- (\b); \node at (2.5,0) {$\cdots$}; \end{tikzpicture} $$ then $\cT_\cP^{\beta}$ is the set of vertices of the $m$-dimensional hypercube. (E3)\enspace If $N=2m$, and $$\cP= \begin{tikzpicture}[scale=.5,baseline=.5cm] \foreach \x/\y/\z in {0/0/1,1/0/2,4/0/{m},0/2/{m+1},1/2/{m+2}, 4/2/N} \node (\x\y) at (2*\x,\y) [inner sep=1pt] {$\scs \z$}; \foreach \a/\b in {00/02,00/12,00/42,10/02,10/12,10/42,40/02,40/12,40/42} \draw (\a) -- (\b); \node at (5,0) {$\cdots$}; \node at (5,2) {$\cdots$}; \end{tikzpicture}$$ then $\cT_\cP^{(1^N)}$ is the usual basis for the rook monoid. (E4)\enspace If $\cN$ is a total order of a set $A$, then the set $\cT_\cN^{(1^N)}$ is in bijection with the set of set partitions of $A$. Specifically, $\lambda\in \cT_\cN^{(1^N)}$ we have $\lambda_{ab}\in \{0,1\}$ for all coordinates $a] (\x,6) -- (6,\x); \foreach \x in {2,3,4,5,6} \draw[gray] (6,\x) to [out=-60,in=120] (\x-1,6); \foreach \x/\y/\z in {0/6/1,1/5/2,2/4/3,3/3/{\ddots},4/2/{\ell-1},5/1/{\ell-1},6/0/{\ell}} \node at (\x,\y) {$\scscs\z$}; \end{tikzpicture}.$$ Then we obtain a sequence $$\{\tilde\nu^{(jl)}\in \cT_{\fat_\beta(\cP)}^{(1^N)}\mid j\prec_\cP l\}, \quad \text{where} \quad \tilde\nu^{(jl)}= \gamma_{jl}+ \sum_{(i,k)\prec (j,l) } \gamma_{ik}.$$ At each step there will be limits on what rows and columns $\gamma_{jl}$ can have nonzero entries to be compatible with the previous choices, but we will obtain all possible $\tilde\nu$ in this way. If we only choose $\tilde\nu$ such that $\chi^{\tilde\nu}(u_{\tilde\mu})\neq 0$, then the nonzero entries of $\gamma_{jl}$ can only be in rows and columns such that \begin{enumerate} \item[(a)] there are no nonzero entries in $\tilde\nu^{(jl)}-\gamma_{jl}$ in that column or row, \item[(b)] there is no nonzero entry of $\tilde\mu$ strictly below in that column or strictly to the left in that row. \end{enumerate} That is, we have $$\beta_j-\sum_{j\prec_\cP k< l} \mu_{jk}-\sum_{l\prec_\cP m} \lambda_{jm}\quad \text{rows and}\quad \beta_{l}-\sum_{j< k\prec_\cP l} \mu_{kl}-\sum_{i\prec_\cP j} \lambda_{il}\quad\text{columns}$$ to choose from for the nonzero entries of $\gamma_{jl}$. Let $\rowsupp(\gamma_{jl})\subseteq \cQ_j$ be the rows in $\gamma_{jl}$ with nonzero entries, and $\colsupp(\gamma_{jl})\subseteq \cQ_l$ be the columns with nonzero entries. Let $\delta_\lambda^{(jl)}\in \cT_\cP^\beta$ be given by $(\delta_\lambda^{(jl)})_{ik}=\delta_{(i,k),(j,l)}\lambda_{jl}$, and let $\lambda^{(jl)}\in \cT_\cP^{\beta}$ label the orbit containing $e^*_{\tilde\nu^{(jl)}}\in \fkut_\cP^*$. Then we have recursions, \begin{align*} \dim_L(\tilde\nu^{(jl)})+\dim_R(\tilde\nu^{(jl)})=&\dim_L(\tilde\nu^{(jl)}-\gamma_{jl})+\dim_R(\tilde\nu^{(jl)}-\gamma_{jl})+\dim_L(\delta_\lambda^{(jl)})\\ &+\dim_R(\delta_\lambda^{(jl)})+\wt_{\cQ_j}^\uparrow(\rowsupp(\gamma_{jl}))+\wt_{\cQ_l}^\downarrow(\colsupp(\gamma_{jl})) \end{align*} and \begin{align*} \nst_{\tilde\mu}^{\tilde\nu^{(jl)}}=&\nst_{\tilde\mu}^{\tilde\nu^{(jl)}-\gamma_{jl}}+\nst_\mu^{(\delta_\lambda^{(jl)})}+\#\{i'\prec j'\prec k'\prec l'\mid j'\in \cQ_j,(\gamma_{jl})_{i'l'}\tilde\mu_{j'k'}=1\}+\\ &+\#\{i'\prec j'\prec k'\prec l'\mid j'\notin \cQ_j,k'\in \cQ_l,(\gamma_{jl})_{i'l'}\tilde\mu_{j'k'}=1\}\\ \crs(\tilde\nu^{(jl)})=&\crs(\tilde\nu^{(jl)}-\gamma_{jl})+\crs(\lambda^{(jl)})-\crs(\lambda^{(jl)}-\delta_\lambda^{(jl)}) +\crs(\gamma_{jl})\\ &+\wt^\uparrow_{\rowsupp(\tilde\nu^{(jl)})\cap \cQ_j-\rowsupp(\gamma_{jl})}(\rowsupp(\gamma_{jl}))+\wt^\downarrow_{\colsupp(\tilde\nu^{(jl)})\cap \cQ_l-\colsupp(\gamma_{jl})}(\colsupp(\gamma_{jl})). \end{align*} Iterating these recursions gives \begin{align*} \dim_L(\tilde\nu)+\dim_R(\tilde\nu)&= \dim_L(\lambda)+\dim_R(\lambda)+\sum_{j\prec_\cP l} \wt_{\cQ_j}^\uparrow(\rowsupp(\gamma_{jl}))+\wt_{\cQ_l}^\downarrow(\colsupp(\gamma_{jl})) \end{align*} and \begin{align*} \nst_{\tilde\mu}^{\tilde\nu}=&\nst_\mu^\lambda+\sum_{j\prec_\cP l}\Big( \#\{i'\prec j'\prec k'\prec l'\mid j'\in \cQ_j,(\gamma_{jl})_{i'l'}\tilde\mu_{j'k'}=1\}\\ &+\#\{i'\prec j'\prec k'\prec l'\mid j'\notin \cQ_j,k'\in \cQ_l,(\gamma_{jl})_{i'l'}\tilde\mu_{j'k'}=1\}\Big)\\ \crs(\tilde\nu)&= \crs(\lambda)+ \sum_{j\prec_\cP l} \Big(\crs(\gamma_{jl}) +\wt^\uparrow_{\rowsupp(\tilde\nu^{(jl)})\cap \cQ_j-\rowsupp(\gamma_{jl})}(\rowsupp(\gamma_{jl}))\\ &+\wt^\downarrow_{\colsupp(\tilde\nu^{(jl)})\cap \cQ_l-\colsupp(\gamma_{jl})}(\colsupp(\gamma_{jl}))\Big). \end{align*} Let \begin{align*} \cR_{jl} &=\cQ_j-\{i'\in \cQ_j\mid (\tilde\mu)_{i'l'}\neq 0, \text{ for some $l'\in \cQ_k$, $k< l$}\}-(\rowsupp(\tilde\nu^{(jl)}-\gamma_{jl})\cap \cQ_j)\\ \cC_{jl} &= \cQ_l-\{k'\in \cQ_l\mid (\tilde\mu)_{j'k'}\neq 0, \text{ for some $j'\in \cQ_k$, $k> j$}\}-(\colsupp(\tilde\nu^{(jl)}-\gamma_{jl})\cap \cQ_l), \end{align*} denote the rows and columns in which $\gamma_{jl}$ may have nonzero entries. Let $\tilde\mu_{jl}=\Res_{\cQ_j\times\cQ_l}(\tilde\mu)$ and $\gamma_{jl}^\circ=\gamma_{jl}-\gamma_{jl}\cap \tilde\mu_{jl}$. Then since $\crs(\gamma_{jl})=\crs(\gamma_{jl}^\circ)$ for $\delta_{\mu_{jl}}^{\gamma_{jl}}\neq 0$, \begin{align*} \chi^\lambda_\beta(u_\mu)&=\frac{q^{\dim_L(\lambda)+\dim_R(\lambda)}}{q^{\crs(\lambda)+\nst_\mu^\lambda}}\prod_{j\prec_\cP l} \sum_{\gamma_{jl}, \tilde\nu^{(jl)}\in \cT_{\cP}^{(1^N)}\atop \chi^{\tilde\nu^{(jl)}}(u_{\tilde\mu})\neq 0} \frac{(q-1)^{\lambda_{jl}}q^{ \wt_{\cR_{jl}}^\uparrow(\rowsupp(\gamma_{jl}))+\wt_{\cC_{jl}}^\downarrow(\colsupp(\gamma_{jl}))}}{(1-q)^{|\gamma_{jl}\cap \tilde\mu_{jl}|}q^{\crs(\gamma_{jl}^\circ)+\nst_{\tilde\mu_{jl}}^{\gamma_{jl}\cap\tilde\mu_{jl}}+|\gamma_{jl}^\circ||\tilde\mu_{jl}|}}\\ &=\frac{q^{\dim_L(\lambda)+\dim_R(\lambda)}}{q^{\crs(\lambda)+\nst_\mu^\lambda}}\prod_{j\prec_\cP l}\chi^{(\lambda_{jl})}_{\loc^\lambda_{\mu}(j,l)}(u_{(\mu_{jl})}), \end{align*} where the second equality comes by letting $\nu_\cA=\gamma_{jl}\cap \tilde\mu_{jl}$ and $\nu_\cB=\gamma_{jl}^\circ$, and comparing with (\ref{KeyIdentity}). \end{proof} We also easily obtain a number of consequences (some of which no doubt have more direct proofs). \begin{corollary} For $\nu\in \cT_\cP^\beta$ with corresponding $e_{\tilde\nu}^*\in \fkut_\cP^*$, $$|P_\beta e_{\tilde\nu}^* P_\beta|=\frac{q^{\dim_L(\lambda)+\dim_R(\lambda)}}{q^{\crs(\lambda)}} \prod_{j\prec_\cP l} |\GL_{\lambda_{jl}}(\FF_q)| \qbin{\beta_j-\sum_{l\prec_\cP m}\lambda_{jm}}{\lambda_{jl}}\qbin{\beta_l-\sum_{i\prec_\cP j}\lambda_{il}}{\lambda_{jl}}.$$ \end{corollary} \begin{proof} By (\ref{SupercharacterDefinition}) and Theorem \ref{FullFormula}, \begin{align*} |P_\beta e_{\tilde\nu}^* P_\beta|=\chi_\beta^\nu(1)=&\frac{q^{\dim_L(\lambda)+\dim_R(\lambda)}}{q^{\crs(\lambda)}} \prod_{j\prec_\cP l} |\GL_{\lambda_{jl}}(\FF_q)| \\ &\times\qbin{\beta_j-\sum_{l\prec_\cP m}\lambda_{jm}}{\lambda_{jl}}\qbin{\beta_l-\sum_{i\prec_\cP j}\lambda_{il}}{\lambda_{jl}}, \end{align*} as desired. \end{proof} Recall that the $\CC$-vector space of functions $\mathrm{f}(G)=\{\psi:G\rightarrow \CC\}$ of a group $G$ has a canonical inner product given by $$\langle \psi, \theta\rangle=\frac{1}{|G|}\sum_{g\in G} \psi(g)\overline{\theta(g)};$$ with respect to this inner product, the irreducible characters are an orthonormal basis for the subspace of class functions. While supercharacters are still orthogonal, they are generally no longer orthonormal. In our case, using a similar argument to \cite{DI}, $$\langle \chi_\beta^\nu,\chi_\beta^\mu\rangle=\delta_{\nu\mu} \chi_\beta^\nu(1)\quad\text{for $\nu,\mu\in \cT_\cP^\beta$},$$ so we may deduce the following result. \begin{corollary} For $\nu,\mu\in \cT_\cP^\beta$, \begin{align*} \langle \chi_\beta^\nu,\chi_\beta^\mu\rangle=\delta_{\nu\mu}\frac{q^{\dim_L(\lambda)+\dim_R(\lambda)}}{q^{\crs(\lambda)}} &\prod_{j\prec_\cP l} |\GL_{\lambda_{jl}}(\FF_q)| \\ &\times\qbin{\beta_j-\sum_{l\prec_\cP m}\lambda_{jm}}{\lambda_{jl}}\qbin{\beta_l-\sum_{i\prec_\cP j}\lambda_{il}}{\lambda_{jl}}. \end{align*} \end{corollary} Recall, that if $(\{\text{conjugacy classes}\},\Irr(G))$ is the usual character theory of $G$, then $$\left\{\begin{array}{@{}c@{}} \text{Normal sub-}\\ \text{groups of $G$}\end{array}\right\}=\{K_A\mid A\subseteq \Irr(G)\},\quad \text{where}\quad K_A=\bigcap_{\chi\in A} \{g\in G\mid \chi(g)=\chi(1)\}.$$ It is therefore natural to ask which normal subgroups are obtained from a given supercharacter theory; I believe this has been largely unexplored. However, for the case of $\UT_\beta$, the answer to this question is particularly pleasing. \begin{corollary} Fix an integer composition $\beta=(\beta_1,\ldots,\beta_\ell)$ and let $\cL_\beta$ the usual total order $1<2<\cdots<\ell$, \[ \{K_A\mid A\subseteq \cT_\beta^{\cL_\beta}\}=\left\{\UT_{(\beta,\cP)}\ \bigg|\ \cP\triangleleft \cL_\beta\right\} \] where $K_A=\displaystyle{\bigcap_{\mu\in A}} \{g\in \UT_{(\beta,\cP)}\mid \chi_\beta^\mu(g)=\chi_\beta^\mu(1)\}.$ \end{corollary} \begin{proof} Let $A\subseteq \cT_\beta^{\cL_\beta}$, and let $\cP^A$ be the subposet of $\cL_\beta$ given by $$j\prec_{\cP^A} k \quad \text{if and only if } \quad i\leq j