%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2024}
\articlenumber{51}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{definition}[thm]{Definition}
\newtheorem{question}[thm]{Question}
\newtheorem{example}[thm]{Example}


\usepackage{comment}

\newcommand{\patty}[1]{\textcolor{olive}{Patty:[#1]}}

\def\kk{\mathbf{k}}


\def\type{\mathrm{type}}
\def\ch{{\mathrm{ch}}}
\def\sgn{\mathrm{sgn}}
\def\stab{\mathrm{Stab}}

\usepackage{tikz} 

\newcommand{\vic}[1]{\textcolor{orange}{[vic: #1]}}

\def\C{{\mathbb{C}}}

\usepackage[table]{xcolor}
\usepackage[boxframe=0.08em, nocentertableaux]{ytableau}
\ytableausetup{smalltableaux}
\usepackage{multirow}
\setlength{\arrayrulewidth}{.5mm}
\setlength{\tabcolsep}{6pt}
\renewcommand{\arraystretch}{1.25}
\usepackage[utf8]{inputenc}
\usepackage{arydshln}
\setcounter{tocdepth}{1}

\usepackage{lipsum}

%% define your title in the usual way
\title{Invariant theory for the face algebra of the braid arrangement}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Patricia Commins\thanks{\href{mailto:hello@world.c}{commi010@umn.edu}. Commins is supported by an NSF Graduate Research Fellowship.}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}School of Mathematics, University of Minnesota Twin Cities} 

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{The faces of the braid arrangement form a monoid. The associated monoid algebra -- the face algebra-- is well-studied, especially in relation to card shuffling and other Markov chains. In this abstract, we explore the action of the symmetric group on the face algebra from the perspective of invariant theory. Bidigare proved the invariant subalgebra of the face algebra is (anti)isomorphic to Solomon's descent algebra. We answer the more general question: what is the structure of the face algebra as a simultaneous representation of the symmetric group and Solomon's descent algebra?

Special cases of our main theorem recover the Cartan invariants of Solomon's descent algebra discovered by Garsia--Reutenauer and work of Uyemura-Reyes on certain shuffling representations. Our proof techniques involve the homology of intervals in the lattice of set partitions.}
%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{descent algebra, higher Lie characters, plethysm, finite dimensional algebras, poset topology, reflection arrangements}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{sample.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above
\section{Background}
\subsection{The braid arrangement and its face algebra}
Write $\mathbf{x}:= (x_1, x_2, \cdots, x_n)$ to denote an element of the vector space $\mathbb{R}^n.$ The \emph{braid arrangement $\mathcal{B}_n$} is the hyperplane arrangement in $\mathbb{R}^n$ consisting of the hyperplanes $\{\mathbf{x}: x_i = x_j\}$ for all $1 \leq i < j \leq n.$ Each hyperplane $\{\mathbf{x}: x_i = x_j\}$ partitions $\mathbb{R}^n$ into three subsets: the halfspace $H_{ij}^+ = \{\mathbf{x}: x_i > x_j\},$ the halfspace $H_{ij}^- = \{\mathbf{x}: x_i < x_j\},$ and the hyperplane itself $H_{ij}^0.$ The \emph{faces} of $\mathcal{B}_n$ are the nonempty intersections of the form \[\bigcap_{1 \leq i < j \leq n}H_{ij}^{\sgn_{ij}}\] for some set of choices $\sgn_{ij} \in \{+, -, 0\}.$


The faces of $\mathcal{B}_n$ naturally correspond to strings of inequalities relating all coordinates. For example, one face $F $ of $\mathcal{B}_7$  corresponds to the string $x_4 < x_1 = x_5 < x_7 < x_2 = x_3 = x_6$. Combinatorially, these strings (and their corresponding faces) are {\emph{ordered set partitions}} of the set $[n]:= \{1, 2, \cdots, n\}$. For example, $F$ is labelled by the ordered set partition $\left (\{4\}, \{1, 5\}, \{7\}, \{2, 3, 6\}\right),$ which we write as $(4, 15, 7, 236).$ The symmetric group \emph{$S_n$} acts on the faces of $B_n$ by $\pi \left(P_1, P_2, \cdots, P_k\right) := \left(\pi(P_1), \pi(P_2), \cdots, \pi(P_k)\right).$ 

\begin{example} \label{ex:braid3labelled}
The braid arrangement $\mathcal{B}_3$ (intersected with the plane $x_1 + x_2 + x_3 = 0$) is shown below. The colors point out the four $S_3$-orbits of faces.
\begin{center}
    \begin{tikzpicture}[scale=3]

\draw[blue, thick, -> ]  (0, 0) -- (-.5, -0.86602540378
) node[anchor=east]{\footnotesize$(3,12)$}; 

\draw[violet, thick, -> ] (0, 0) -- (.5,  0.86602540378) node[anchor=west] {\footnotesize$(12,3)$}
;
%\draw[black]  (.5,  0.86602540378) --(.5, 1.01) node[anchor=south] {$H_{1,2}$} ;
\draw[blue, thick, <-] (-.5, 0.86602540378
) node[anchor=east]{\footnotesize$(2,13)$} --(0, 0); 

%\draw[black]  (1,0) --(1, .15) node[anchor=south] {$H_{2,3}$} ;

\draw[violet, thick, ->](0, 0)-- (.5,  -0.86602540378)
node[anchor=west] {\footnotesize$(13,2)$};
 \draw[violet, thick, <-]  (-1, 0
)-- (0, 0);
\filldraw[violet] (-1,0) circle (0pt) node[anchor=east] {\footnotesize$(23,1)$};
\draw[blue, thick, ->](0, 0)-- (1, 0) node[anchor=west] {\footnotesize$(1,23)$}
;

\filldraw[red] (0,0) circle (1pt) ;

\filldraw[red] (-.225, .005) circle (0pt) node[anchor=south]{\footnotesize$(123)$};

\filldraw[teal] (.6495,.375)  circle (0pt) node[anchor=south]{\footnotesize$(1,2,3)$};
\filldraw[teal] (0,.75)  circle (0pt) node[anchor=north]{\footnotesize$(2,1,3)$};
\filldraw[teal] (.6495,-.375)  circle (0pt) node[anchor=south]{\footnotesize$(1,3,2)$};
\filldraw[teal] (-.6495, .375)  circle (0pt) node[anchor=south]{\footnotesize$(2,3,1)$};
\filldraw[teal] (-.6495, -.375)  circle (0pt) node[anchor=south]{\footnotesize$(3,2,1)$};
\filldraw[teal] (0, -.75)  circle (0pt) node[anchor=south]{\footnotesize$(3,1,2)$};
\end{tikzpicture}
\end{center}
\normalsize
\end{example}

The faces of $\mathcal{B}_n$ have an associative multiplicative structure. This {product} was first considered by Tits in \cite{TITS1976265}. In terms of ordered set partitions, 
\[\left(P_1, P_2, \cdots, P_k \right) \cdot \left(Q_1, Q_2, \cdots, Q_\ell\right) := \left(P_1 \cap Q_1, P_1 \cap Q_2, \cdots, P_1 \cap Q_\ell, P_2 \cap Q_1, \cdots P_k \cap Q_\ell \right)^{\wedge},\] where $\wedge$ indicates the removal of empty sets. For example, in $\mathcal{B}_7,$
\[(4, 15, 7, 236) \cdot (245, 367, 1) = (4, 5, 1, 7, 2, 36).\] 

The ordered set partition with a single block $(12\cdots n)$ is an identity element, so the faces form a monoid, which we denote by $\mathcal{F}_n.$ We are primarily interested in the \emph{face algebra} $\mathbb{C}\mathcal{F}_n$ which is the free $\mathbb{C}-$module with basis $\mathcal{F}_n$ and multiplication
\[\left(\sum_{F \in \mathcal{F}_n}c_FF \right)\cdot \left(\sum_{G \in \mathcal{F}_n}d_GG\right) := \sum_{F, G \in \mathcal{F}_n}c_Fd_G F\cdot G.\]

It is straightforward to check the symmetric group action on $\mathcal{F}_n$ is by monoid homomorphisms. Hence, $S_n$ acts on $\mathbb{C}\mathcal{F}_n$ by algebra homomorphisms. The structure of $\mathbb{C}\mathcal{F}_n$ as an $S_n-$representation is also simple to check. Throughout this abstract, let $\ch$ denote the \emph{Frobenius characteristic map} from characters of symmetric groups to the ring of symmetric functions. We write $\alpha \vDash n$ if $\alpha = (\alpha_1, \alpha_2, \cdots, \alpha_k)$ is an \emph{integer composition} of $n$ (a sequence of positive integers summing to $n$). Using $h_\alpha := h_{\alpha_1}h_{\alpha_2} \cdots h_{\alpha_k}$ for $h_i$ the complete homogeneous symmetric function of degree $i,$ we have $\displaystyle \ch \left(\C \mathcal{F}_n\right) = \sum_{\alpha \vDash n}h_\alpha.$

In \cite{BHR}, Bidigare--Hanlon--Rockmore discovered that the face algebra has rich connections to card shuffling and other Markov chains. These connections were studied further by many others, including  Uyemura-Reyes in \cite{Uyemura-Reyes} and Reiner--Saliola--Welker in \cite{reiner2014spectra}. In addition,
the face algebra has been studied as an interesting algebra in its own right; for instance, see work of Bidigare in \cite{Bidigare}, Saliola in \cite{saliolaquiverdescalgebra, saliolafacealgebra}, Aguiar--Mahajan in \cite{Aguiar-Mahajan}, and Schocker in \cite{Schocker}.

\subsection{Solomon's descent algebra and Bidigare's theorem}
Each permutation  $\pi \in S_n$ has an associated (right) \emph{descent set} $\mathrm{Des}(\pi) := \{i: \pi(i) > \pi(i + 1)\}\subseteq [n - 1].$ For each subset $J \subseteq [n - 1]$, define an element $\mathbf{x}_J$ in the group algebra $\C S_n$ by \[\mathbf{x_J} := \sum_{\pi: \mathrm{Des}(\pi) \subseteq J}\pi.\] In \cite{Solomondescentbirth}, Solomon {proved}
that the  $\C$- span of the elements $\left \{x_J: J \subseteq [n - 1]\right\}$ is closed under multiplication, so it is a subalgebra of $\mathbb{C}S_n.$ This subalgebra is 
known as \emph{Solomon's descent algebra}, which we will denote by \emph{$\Sigma_n$}. The descent algebra is intimately linked to the face algebra. For a subset $J = \{a_1<a_2 < \cdots < a_k\} \subseteq [n - 1],$ write ${\alpha(J)}$ to be the integer composition $(a_1, a_2 - a_1, a_3 - a_2, \cdots, a_k - a_{k - 1}, n - a_k).$ Bidigare proved the following connection in \cite[Theorem 3.8.1]{Bidigare}.


\begin{thm}(Bidigare)\label{thm:bidigare}
The $S_n$-invariant subalgebra of the face algebra is antiisomorphic to Solomon's descent algebra via the map \[\Phi:x_J \mapsto \sum_{\substack{\text{Faces }F\\ \text{with block }\\ \text{sizes } \alpha(J)}}F.\] 
\end{thm}

\begin{example}
     Using one-line notation, the element $x_{\{1\}} = 1 + 21 + 312 \in \Sigma_3$ is mapped under Bidigare's antiisomorphism to the sum of the three rays colored blue in \cref{ex:braid3labelled}.
\end{example}

\section{Our question}\label{sec:quest}
By Maschke's theorem, the face algebra $\C\mathcal{F}_n$ decomposes into a direct sum of irreducible $S_n-$representations. Although this decomposition is not unique, the sums of irreducibles of the same isomorphism type, called the \emph{isotypic subspaces}, are. The irreducible representations of $S_n$ are indexed by partitions $\nu$ of $n$, written $\nu \vdash n.$ Hence, there is an $S_n-$representation decomposition \[\C\mathcal{F}_n = \bigoplus_{\nu \vdash n}\left(\C \mathcal{F}_n \right)^\nu,\] where $\left(\C \mathcal{F}_n\right)^\nu$ is the $S_n-$isotypic subspace associated to the irreducible labelled by $\nu.$  

The trivial isotypic subspace $\left(\C \mathcal{F}_n\right)^{(n)}$ is precisely the invariant subalgebra $\left(\C \mathcal{F}_n\right)^{S_n}$. So, it is a natural extension of Bidigare's theorem to consider what the other $S_n-$isotypic subspaces look like. In fact, in \cite[\S 3.5.3]{Bidigare}, Bidigare studied
the \emph{sign isotypic subspace $\left(\C \mathcal{F}_n\right)^{1^n},$} which he proved is a one-dimensional nilpotent subalgebra of $\C \mathcal{F}_n$.

Moreover, the isotypic subspaces are not only $S_n-$representations; each carries an additional, rich structure as a left module over $\left(\C \mathcal{F}_n\right)^{S_n}.$ Hence, by \cref{thm:bidigare}, each isotypic subspace is actually a (right) module over the descent algebra $\Sigma_n$ by the action \[f \cdot x := \Phi(x)f \text{ for } f \in \left(\C \mathcal{F}_n\right)^\nu, x \in \Sigma_n.\] This brings us to our main question. 


\begin{question}\label{question:OG}
    What is the structure of each $S_n$-isotypic subspace $\left(\mathbb{C} \mathcal{F}_n \right)^{\nu}$ as a $\Sigma_n-$module?
\end{question}

We will answer \cref{question:OG} with \cref{conj:typeA-comp-factors}. Specifically, we will reduce \cref{question:OG} to understanding specific symmetric group representations, which we analyze up to longstanding open problems. To explain this problem conversion and our answer, we must first say a bit about the representation theory of the descent algebra. 
\subsection{Representation theory of Solomon's descent algebra} \label{sec:rep-theory-descent-algebra}

The (right) representation theory of the descent algebra has been studied in great depth by {Garsia and Reutenauer} in \cite{garsia-reutenauer}. Although $\Sigma_n$ is not semisimple, its representation theory is still quite nice. The simple $\Sigma_n-$modules are all one-dimensional and are indexed by integer partitions of $n$. Let ${M_\lambda}$ denote the $\Sigma_n-$simple associated to the partition $\lambda.$ From the {theory of finite dimensional algebras}, we have that as $\Sigma_n-$modules, \[\Sigma_n \cong \bigoplus_{\lambda \vdash n}P_\lambda,\] where $P_\lambda$ is the projective indecomposable $\Sigma_n-$module with {top} $M_\lambda.$ 

Any complete family of primitive orthogonal idempotents \emph{(cfpoi)} for the descent algebra $\Sigma_n$ is necessarily indexed by integer partitions of $n$ too. For notational convenience, we write $\{E_\lambda: \lambda \vdash n\}$ to denote the images of such idempotents under the Bidigare antiisomorphism $\Phi$ (so in $\left(\C \mathcal{F}_n\right)^{S_n}$ rather than $\Sigma_n$). We choose the indexing appropriately so that $P_\lambda \cong \Phi^{-1}\left(E_\lambda\right)\Sigma_n \cong \left(\C \mathcal{F}_n\right)^{S_n}E_\lambda$ as right $\Sigma_n-$modules. 

In a similar fashion, any cfpoi for the face algebra $\C\mathcal{F}_n$ is indexed by (unordered) set partitions of $[n].$ We write \emph{$\Pi_n$} to denote the set partition lattice ordered under refinement and say a set partition \emph{$X \in \lambda$} if it has block sizes $\lambda.$ In \cite{saliolaquiverdescalgebra}, Saliola constructed cfpois $\{E_X: X \in \Pi_n\}$ for $\C \mathcal{F}_n$ for which $\pi \left(E_X\right) = E_{\pi(X)}$ for $\pi \in S_n.$ He proved the orbit sums of such families, $\{\sum_{X \in \lambda} E_X: \lambda \vdash n\}$, form cfpois for $\left(\C \mathcal{F}_n\right)^{S_n}.$ 

Any two cfpois for the invariant subalgebra $\left(\C \mathcal{F}_n\right)^{S_n}$ are conjugate by an invertible element of $\left(\C \mathcal{F}_n\right)^{S_n}$ (see \cite[Lemma D.26]{Aguiar-Mahajan}). By conjugating Saliola's idempotents\footnote{Aguiar and Mahajan further study and characterize such idempotents very thoroughly in \cite[\S 16.8]{Aguiar-Mahajan}.}, any cfpoi for $\left(\C \mathcal{F}_n\right)^{S_n}$ can be written as the $S_n-$orbit sums of some cfpoi for $\C \mathcal{F}_n$ permuted by $S_n.$  For these reasons, our choice of a cfpoi for $\left(\C \mathcal{F}_n\right)^{S_n}$ turns out to not matter. For the remainder of this abstract, let $\{E_\lambda: \lambda \vdash n\}$ be a cfpoi for $\left(\C \mathcal{F}_n\right)^{S_n}$ and let $\{E_X: X \in \Pi_n\}$ be a cfpoi for $\C \mathcal{F}_n$ which is permuted by $S_n$ and has orbit sums $\{E_\lambda\}.$ 
\subsection{Problem conversion}
 As a first step towards answering \cref{question:OG}, we decompose each $S_n-$isotypic subspace $\left(\C \mathcal{F}_n\right)^\nu$ into a direct sum of smaller $\Sigma_n$-modules. Write \emph{$f^\nu$} to denote the number of standard Young tableaux of shape $\nu,$  write $\alpha \sim \mu$ if a composition $\alpha$ rearranges to a partition $\mu,$ and write $K_{\nu, \mu}$ to denote the \emph{Kostka number} which counts the number of semistandard Young tableaux of shape $\nu$ and content $\mu.$ 
\begin{prop}\label{prop:decomp-isos}
As (right) $\Sigma_n-$modules,
    \[\left(\C \mathcal{F}_n\right)^{\nu} =\bigoplus_{\mu \vdash n}(\C \mathcal{F}_n E_\mu)^{\nu}, \text{ and}\] \[ \dim_{\C}(\C \mathcal{F}_nE_\mu )^{\nu} = f^\nu \cdot \#\{\alpha \vDash n \ | \ \alpha \sim \mu\}\cdot K_{\nu, \mu}.\] 
\end{prop}

\cref{prop:decomp-isos} reduces \cref{question:OG} to understanding each $\Sigma_n-$module $\left(\C \mathcal{F}_n E_\mu \right)^\nu$ for any two partitions $\mu, \nu$ of $n.$  Since $\Sigma_n$ is not semisimple, we are unable in general to decompose each $\Sigma_n-$module $\left(\C \mathcal{F}_n E_\mu \right)^\nu$ into a direct sum of simples. However, by the Jordan-H\"{o}lder theorem, we can take the alternative approach of understanding the $\Sigma_n$-\emph{composition factors} of each  $\Sigma_n-$module $\left(\C \mathcal{F}_n E_\mu \right)^\nu$. The number of times a $\Sigma_n$-simple $M_\lambda$ appears as a composition factor of a $\Sigma_n-$module $V$ is the \textit{composition multiplicity} of $M_\lambda$ in $V$, written $[V: M_\lambda]$. Thus, we have converted \cref{question:OG} to the following question.
\begin{question}\label{quest:2'}
For partitions $\mu, \nu, \lambda$ of $n,$  what is the composition multiplicity $[(\C \mathcal{F}_nE_\mu)^{\nu}:M_\lambda]$?
\end{question}

The proposition below follows from the theory of finite dimensional algebras. 

\begin{prop}\label{prop:transform-to-group-rep-q}
The composition multiplicity of the $\Sigma_n-$ simple $M_{\lambda}$ in $\left(\C \mathcal{F}_n E_{\mu}\right)^{\nu}$ is 
    \[\left[(\C \mathcal{F}_nE_{\mu})^{\nu}:M_{\lambda}\right] = f^\nu \cdot \left \langle s_\nu, \ch \left(E_{\lambda}\C \mathcal{F}_n E_{\mu}\right) \right \rangle,\]
    where $s_\nu$ is the Schur function associated to the partition $\nu$ and $\langle \cdot, \cdot \rangle$ is the Hall inner product. 
\end{prop}

Hence, our final conversion of \cref{question:OG} is the question below.

\begin{question}\label{quest:sn-rep-structure}
    What is the $S_n$-representation theoretic structure of $E_\lambda \C\mathcal{F}_nE_\mu$?
\end{question}

\section{Our answer}
Thrall studied a collection of $S_n$-representations in \cite{Thrall} which are (also) indexed by partitions of $n$ and often called the \emph{higher Lie representations}.  We write $L_\lambda$ to denote the Frobenius image of the higher Lie representation associated to $\lambda.$ These representations have many {interpretations} and are closely tied to the free Lie algebra. For our purposes, it is most revealing to define $L_{n}$ as the Frobenius image of the $S_n$-representation carried by the top homology of (the proper part of) the set partition lattice $\Pi_n$ tensored with the sign representation\footnote{This is equivalent to the standard definition by work of Stanley \cite{stanley_grps_on_postes}, Hanlon \cite{hanlon}, and Klyachko \cite{Klyachko}.}. More generally, for a partition $\lambda = 1^{m_1}2^{m_2} \cdots k^{m_k},$ let \[L_\lambda := \prod_{i = 1}^k h_{m_i}[L_i],\] where the brackets denote \emph{plethysm}. Positively expanding $L_\lambda$ into Schur functions is a longstanding open problem, known as \emph{Thrall's problem}.

    A \emph{Lyndon word} is a nonempty finite word on $\{1, 2, \cdots \}$  that is lexicographically \textit{strictly} smaller than all of its cyclic rearrangements. For an integer composition, partition, or word $\alpha = (\alpha_1, \alpha_2, \cdots, \alpha_k)$ on $\{1, 2, \cdots \}$, we write $|\alpha|$ to denote the sum $\alpha_1 + \alpha_2 + \cdots + \alpha_k.$  For any infinite variable set $\mathbf{y} = \{y_1, y_2, \cdots\},$ let \emph{$\mathbf{y}_{\alpha}$} denote the product $\mathbf{y}_\alpha:= y_{\alpha_1}y_{\alpha_2} \cdots y_{\alpha_k}.$  The scaling of $\alpha$ by an integer $m$ is $\alpha \cdot m:= (\alpha_1 \cdot m, \alpha_2 \cdot m, \cdots, \alpha_k \cdot m)$ and raising $\alpha$ to an integer, \emph{$\alpha^m$}, means repeated concatenation of $\alpha$.
    
%    \textcolor{red}{In contrast, later on we will use \emph{$\mathbf{x}^\alpha$} to denote the product $\mathbf{x}^\alpha := x_1^{\alpha_1}x_2^{\alpha_2}\cdots x_k^{\alpha_k}.$ In the definition $\mathbf{x}^\alpha,$ we allow $\alpha$ to be any weak composition (a sequence of non-negative integers, with finite support).}
    
    %In particular, $\alpha^0$ is the empty partition or composition $\emptyset,$ and in general, we define $$\alpha^{m}:= \underbrace{(\alpha_1, \alpha_2 \cdots, \alpha_k, \alpha_1, \alpha_2, \cdots, \alpha_k, \cdots, \alpha_1, \alpha_2, \cdots, \alpha_k).}_{km \text{ total terms}}$$ 

We now have the necessary definitions to state our main theorem.
%which answers \cref{question:OG} by analyzing the $S_n-$representations $E_\lambda \C \mathcal{F}_n E_\mu$ up to open problems (plethysm coefficients and Thrall's problem).

\begin{thm}\label{conj:typeA-comp-factors} There is an equality of generating functions
\begin{align}\label{eqn:ogf}
    \sum_{n \geq 0} \sum_{\substack{\lambda \vdash n\\ \mu \vdash n}}  \mathbf{y}_\lambda \mathbf{z}_\mu\cdot \ch(E_\lambda \C \mathcal{F}_n E_\mu) = \prod_{\substack{\text{Lyndon }\\ w}} \sum_{\substack{\text{partition}\\\rho}} \mathbf{y}_{\rho \cdot |w|}\mathbf{z}_{w^{|\rho|}}L_\rho[h_w].
\end{align}
\end{thm} 

Let $F$ be the generating function on the right side of \cref{eqn:ogf}. \cref{conj:typeA-comp-factors} explains the structure of $\C \mathcal{F}_n$ as a module over $S_n$ and $\Sigma_n$ simultaneously, answering \cref{question:OG}. Indeed, \cref{prop:transform-to-group-rep-q} and \cref{conj:typeA-comp-factors} combine to give
\begin{equation}\label{eqn:answer}
    \left[\left(\C\mathcal{F}_nE_\mu\right)^\nu: M_\lambda\right] = f^\nu \cdot \left \langle s_\nu, \text{coefficient of }\mathbf{y}_\lambda \mathbf{z}_\mu \text{ in }F \right \rangle.
\end{equation}
 Since Thrall's problem and understanding plethysm coefficients are longstanding open problems, this is as far as we are able to simplify our answer for now.

\subsection{Example}\label{subsec:examples}

As an example of \cref{conj:typeA-comp-factors}, we analyze the case $n = 4$ in the table below. The box in row $\nu$ and column $\mu$ is filled with $[\left(\C \mathcal{F}_4E_\mu\right)^\nu: M_\lambda]$ copies of $\lambda,$ where the numbers in parentheses indicate multiplicities. 
\begin{center}\scalebox{.6}{
\begin{tabular}{cc}
     & \huge{$\mu$} \\[.5em]
 \huge{$\nu$} \ & 
\begin{tabular}{c||c|c|c|c|c}
\centering
%&  { \ydiagram{4}} & { \ydiagram{3,1}} & { \ydiagram{2,2}} & { \ydiagram{2,1,1}} &  {\ydiagram{1,1,1,1}}\\[4em]
& \Large $4$ &  \Large $3,1$ & \Large $2,2$ & \Large $2, 1, 1$ &  \Large $1, 1, 1, 1$\\
\hline
\hline
 \Large $1,1,1,1$ & & & & & \ydiagram{2,2}\\[2em]
\hline
 \Large {$2, 1, 1$} & & & & \cellcolor{pink}{\ydiagram{4} \ (3) \hspace{.5cm} \ydiagram{3,1} \  (3)} & {\ydiagram{4} \ (3) \hspace{.5cm} \ydiagram{3,1} \ (3)}\\ 
 & & & & \cellcolor{pink}{\ydiagram{2,2} \ (3)} &{\ydiagram{2,1,1}\ (3)\multirow{-2}{*}{}}\\[2em]
\hline
\Large{$2, 2$} & & & \ydiagram{2,2} \ (2) & \cellcolor{pink}{\ydiagram{4} \ (2) \hspace{.5cm} \ydiagram{3,1} \ (2)} & {\ydiagram{3,1} \ (2) \hspace{.5cm} \ydiagram{2,2}\  (2) }\\[1.2em]
 & & &  & \cellcolor{pink}{\ydiagram{2, 1, 1} \ (2)}&{\multirow{-2}{*}{}}\\[2em] 
\hline
\Large{$3, 1$} & & \ydiagram{4} \ (3) \hspace{.5cm}\ydiagram{3,1} \ (3) & \ydiagram{4} \ (3) & \cellcolor{pink}{\ydiagram{4} \ (6) \hspace{.5cm} \ydiagram{3,1} \ (6)} & {\ydiagram{4} \ (3) \hspace{.5cm} \ydiagram{3,1} \ (3)}\\[1.5em] 
 & &  &  & \cellcolor{pink}{\ydiagram{2,2} \ (3) \hspace{.5cm} \ydiagram{2,1,1} \ (3) }& { \ydiagram{2,1,1} \ (3)}\\[2em]
\hline
 \Large{$4$} \normalsize& {\ydiagram{4}} & {\ydiagram{4} \hspace{.5cm} \ydiagram{3,1}}& {\ydiagram{2,2}}& \cellcolor{pink}{\ydiagram{4} \hspace{.5cm}\ydiagram{3,1}} & \ydiagram{1,1,1,1}\\ 
 &  & & & \cellcolor{pink}{{\ydiagram{2,1,1}}} & {}\multirow{-2}{*}{}\\[2em] 
\end{tabular}
\end{tabular}}
\end{center}

Each term in the expansion of $F$ is formed by choosing one (potentially empty) partition $\rho$ for each Lyndon word factor $w$ and multiplying the corresponding terms $\mathbf{y}_{\rho \cdot |w|}\mathbf{z}_{w^{|\rho|}}L_{\rho}[h_w].$ To obtain terms with $\mathbf{z}-$weight $\mathbf{z}_{211} = z_2z_1^2,$ the only Lyndon words $w$ for which one can choose a nonempty partition $\rho$ are $w = 1, w = 2, w = 12,$ and $w = 112.$ With these relevant factors first, the generating function $F$ is:
\begin{align*}
\underbrace{\left(\sum_{\rho}\mathbf{y}_{\rho}\mathbf{z}_1^{|\rho|}L_\rho[h_1]\right)}_{w = 1}\underbrace{\left(\sum_{\rho}\mathbf{y}_{\rho\cdot 2}\mathbf{z}_2^{|\rho|}L_\rho[h_2]\right)}_{w = 2}\underbrace{\left(\sum_{\rho}\mathbf{y}_{\rho\cdot 3}\mathbf{z}_{12}^{|\rho|}L_\rho[h_{12}]\right)}_{w = 12}\underbrace{\left(\sum_{\rho}\mathbf{y}_{\rho\cdot 4}\mathbf{z}_{112}^{|\rho|}L_\rho[h_{112}]\right)}_{w = 112}\cdots.
\end{align*}
Labelling by the $w$ for which a nonempty $\rho$ was chosen, the coefficient of $\mathbf{z}_{211}$ is 
\begin{align*}
    &\underbrace{\mathbf{y}_{2} L_{2}[h_1]}_{\substack{w = 1\\ \rho = 2}} \cdot \underbrace{\mathbf{y}_{2}L_1[h_2]}_{\substack{w = 2\\ \rho = 1}} + \underbrace{\mathbf{y}_{11} L_{11}[h_1]}_{\substack{w = 1\\ \rho = 11}}\cdot \underbrace{\mathbf{y}_{2}L_1[h_2]}_{\substack{w = 2\\ \rho = 1}} + \underbrace{\mathbf{y}_1L_1[h_1]}_{\substack{w = 1\\ \rho = 1}}\cdot \underbrace{\mathbf{y}_{3}L_1[h_{12}] }_{\substack{w = 12\\ \rho = 1}} + \underbrace{\mathbf{y}_4L_{1}[h_{112}]}_{\substack{w = 112\\ \rho = 1}}\\
    &= \mathbf{y}_{22}\left(L_2[h_1]L_1[h_2]\right) + \mathbf{y}_{211}\left(L_{11}[h_1]L_1[h_2]\right) + \mathbf{y}_{31}\left(L_1[h_1]L_1[h_{12}] \right) + \mathbf{y}_4 \left(L_1[h_{112}]\right)\\
    &= \mathbf{y}_{22} \left(s_{211} + s_{31}\right) + \mathbf{y}_{211} \left(s_4 + s_{22} + s_{31}\right) + {\mathbf{y}_{31}}\normalcolor \left(s_4 + {2s_{31}}\normalcolor + s_{22} + s_{211}\right)\\ &\quad + \color{blue}\mathbf{y}_{4}\normalcolor \left(s_4 + \color{blue}{2s_{31}}\normalcolor + s_{22} + s_{211}\right),
\end{align*}
where the final equality can be computed with SageMath. This process reveals how to fill each box of the pink column. For instance, the composition multiplicity of $M_{4}$ in $\left(\C\mathcal{F}_4E_{211}\right)^{31}$ is $6 = 3 \cdot 2$ because $f^{(3,1)} = 3$ and the coefficient of $\mathbf{y}_{4}s_{31}$ in the above equation is $2,$ as indicated by the coloring.
\subsection{Recovering results of Garsia--Reutenauer and Uyemura-Reyes}

As further examples, we explain how \cref{conj:typeA-comp-factors} specializes to recover results of Garsia--Reutenauer in \cite{garsia-reutenauer} and Uyemura-Reyes in \cite{Uyemura-Reyes}.

\subsubsection{The bottom row ($\nu = (n)$): Garsia--Reutenauer's Cartan invariants of $\Sigma_n$}
In \cite[Theorem 5.4]{garsia-reutenauer}, Garsia and Reutenauer discovered the Cartan invariants\footnote{They actually proved a stronger result by finding bases for the spaces $\Phi^{-1}(E_\mu)\Sigma_n \Phi^{-1}(E_\lambda).$} of the descent algebra. To state their result, let \emph{$\mathrm{type}(\alpha)$} for a composition $\alpha$ be the partition obtained by reordering $|w_1|, |w_2|, \cdots, |w_k|$ where $w_1 w_2\cdots w_k$ is the unique factorization of $\alpha$ into weakly decreasing (lexicographically) Lyndon words (see \cite[Proposition 5.3]{garsia-reutenauer}). 

\begin{thm}[Garsia--Reutenauer]\label{thm:garsia-reutenauer} The composition multiplicity
\[[P_\mu: M_\lambda ] = \# \{\alpha \sim \mu : \mathrm{type}(\alpha) = \lambda\}.\]
\end{thm}

\begin{example}
The compositions rearranging to $(2, 1, 1)$ are $(2, 1, 1)$, $(1, 2, 1)$, and $(1, 1, 2)$. As the table below illustrates, the composition factors of $P_{211}$ are one copy each of $M_{211}$, $M_{31}$, and $M_{4}$. Compare this to the box in row $(4)$ and column $(2, 1, 1)$ of the table in \cref{subsec:examples}.
\begin{table}[h]\label{table:excompmulttypea}
    \centering
    \begin{tabular}{c|c|c}
         $\alpha$ & Lyndon Factorization & $\type(\alpha)$  \\
         \hline
         $(2, 1, 1)$ & $(2)(1)(1)$ & $(2, 1, 1)$\\
         $(1,2, 1)$ & $(1,2)(1)$ & $(3, 1)$\\
          $( 1, 1, 2)$ & $(1,1,2)$ & $(4)$
    \end{tabular}
\end{table}

\end{example}

As descent algebra modules, $P_\mu \cong \left(\C \mathcal{F}_n E_\mu\right)^{(n)}.$ So, by \cref{eqn:answer}, the following proposition recovers Garsia--Reutenauer's discovery.

\begin{prop} For $\lambda, \mu$ partitions of $n,$
\begin{align*}
  \left \langle s_n, [\mathbf{y}_\lambda\mathbf{z}_\mu] \prod_{\substack{\text{Lyndon }\\ w}} \sum_{\substack{\text{partition}\\\rho}} \mathbf{y}_{\rho \cdot |w|}\mathbf{z}_{w^{|\rho|}}L_{\rho}[h_w] \right \rangle =  \# \{\alpha \sim \mu : \mathrm{type}(\alpha) = \lambda\}.
\end{align*}
\end{prop}
\begin{proof}[Proof Sketch.] 
 From properties of plethysm and higher Lie representations, one can show  \[\left \langle s_n, \prod_{\substack{w
 }}L_{\nu^w}[h_w] \right \rangle = 0\] unless each partition $\nu^w$ is of the form $1^{m_w}$ for some integer $m_w$ with $\sum_{w}|w|m_w = n,$ in which case it is one. Hence, the left side of the proposition statement simplifies to \[[\mathbf{y}_\lambda \mathbf{z}_\mu]\prod_{\substack{\text{Lyndon}\\ w}}\sum_{\substack{m \geq 0}}\mathbf{y}_{|w|^m}\mathbf{z}_{w^{m}}.\]
   \item A straightforward combinatorial argument using Lyndon factorization recovers that \[\prod_{\substack{\text{Lyndon }\\ w}} \sum_{m \geq 0}   \mathbf{y}_{|w|^m}\mathbf{z}_{w^{m}} =
\sum_{\substack{\text{partitions}\\ \lambda, \mu}} \# \{\alpha \sim \mu : \mathrm{type}(\alpha) = \lambda\}\mathbf{y}_\lambda \mathbf{z}_\mu. \qedhere\]
\end{proof}

\subsubsection{The rightmost column $(\mu = 1^n$): Uyemura-Reyes's shuffling representations}\label{sec:Uyemura--Reyes}
    In his PhD thesis (see \cite[Theorem 4.1]{Uyemura-Reyes}), Uyemura-Reyes studied  certain shuffling eigenspaces indexed by partitions $\lambda \vdash n,$ which turn out to be the spaces $E_\lambda \C \mathcal{F}_nE_{1^n}$. He proved the $\lambda$-eigenspace has Frobenius characteristic $L_\lambda$. \cref{conj:typeA-comp-factors} recovers this result, since it is simple to check that the coefficient of $\mathbf{z}_{1^n}$ in \cref{eqn:ogf} is \[\displaystyle \sum_{\substack{ \lambda \vdash n}}\mathbf{y}_{\lambda}L_{\lambda}[h_1] = \sum_{\substack{\lambda \vdash n}}\mathbf{y}_{\lambda}L_\lambda.\]
    
    
    
    %It is possible to consider the action of BHR shuffles on the other pieces of the filtration as well, i.e. $E_\lambda \kk \mathcal{F}_n E_\mu$ for $\mu \neq 1^n$. There is a similar theorem to the BHR theorem for general face algebra modules (see \cite[Theorem 9.44]{Aguiar-Mahajan}). BHR shuffles are diagonalizable on any module over the face algebra (see \cite[Corollary 3.4]{reiner2014spectra}), originally a result of Brown (\cite{BrownonLRBs}). Thus, for $S_n$-invariant BHR shuffles, the spaces $E_\lambda \kk \mathcal{F}_n E_\mu$ are the eigenspaces of the eigenvalue corresponding to $\lambda \vdash n$ (see Corollary D.18 of \cite{Aguiar-Mahajan}). Setting $\mathbf{y}$ to $\mathbf{1}$ in \cref{conj:typeA-comp-factors}, gives the Frobenius characteristic of the $\lambda$-eigenspace of $S_n$-invariant BHR shuffles on the entire face algebra. \patty{Include?}

\subsection{More explicit answer for the sign isotypic subspace}
Recall from \cref{sec:quest} that the sign isotypic subspace $\left( \C \mathcal{F}_n \right)^{1^n}$ is always a one-dimensional subspace. Hence, it must be a simple $\Sigma_n-$module.
\begin{prop}\label{prop:sign-iso}
As $\Sigma_n$-modules, the sign isotypic subspace $\left(\C \mathcal{F}_n\right)^{1^n}$ of the face algebra is isomorphic to $M_\lambda$ where $\lambda = \left(2^{\frac{n}{2}}\right)$ if $n$ is even and $\lambda = \left(2^{\frac{n - 1}{2}}, 1\right)$ if $n$ is odd.
\end{prop}

This follows from a result of Gessel--Reutenauer \cite[Theorem 2.1]{gesselreutenauer} which (as a special case) shows $\langle L_\lambda, s_{1^n}\rangle$ counts permutations in $S_n$ with cycle type $\lambda$ and descent set $[n - 1].$ Hence, the scalar product is zero except for when $\lambda$ is the cycle type of the longest word.

\subsection{Outline of the proof of \cref{conj:typeA-comp-factors}}
Although the complete proof of \cref{conj:typeA-comp-factors} is quite long, a nice range of combinatorics is involved. So, we briefly outline the important ideas for the curious reader. For the details, see the full version of this abstract in \cite{Commins}.
\subsubsection{Reduction to homology of intervals in the set partition lattice $\Pi_n$} \label{subsubsec:homology-intervals}
The proposition below relies on special properties holding for any cfpoi of $\C \mathcal{F}_n.$  Let $\stab_{S_n}(X)$ denote the $S_n$-stabilizer subgroup of the set partition $X.$
\begin{prop}\label{prop:double-idemp-sapces}
    If $\mu$ does not refine $\lambda,$ then $E_\lambda \C \mathcal{F}_n E_\mu = 0.$ Otherwise, as $S_n-$representations,
    \begin{align*}
        E_{\lambda}\C \mathcal{F}_nE_{\mu} \cong \bigoplus_{ [X \leq Y]} E_Y \C \mathcal{F}_n E_X\Big\uparrow_{\stab_{S_n}(X) \cap \stab_{S_n}(Y)}^{S_n}
    \end{align*}
     where the direct sum is over $S_n-$orbits of pairs $X \leq Y$ in $\Pi_n$ with $X \in \mu, Y \in \lambda.$
\end{prop}

A twisting character appears when studying the spaces $E_Y \C \mathcal{F}_n E_X.$ The set partition lattice is ($S_n-$equivariantly) isomorphic to the  lattice of intersections of the hyperplanes of $\mathcal{B}_n$. Let $\det(Y)$ be the $\stab_{S_n}(Y)-$character sending $g$ to $+1$ if it preserves orientation on the intersection associated to $Y$ and $-1$ otherwise.

Saliola proves the non-equivariant version of the following proposition in \cite[\S 10.2]{saliolafacealgebra}. The twists making it equivariant appear implicitly in his work in \cite[Theorem 6.2]{saliolaquiverdescalgebra}. Aguiar and Mahajan also explain it in \cite[Proposition 14.44]{Aguiar-Mahajan}. 

\begin{prop}\label{prop:changing-to-hom}
    Assume $X, Y \in \Pi_n$ with $X$ refining $Y.$ As representations of $\stab_{S_n}(X) \cap \stab_{S_n}(Y)$, 
    \[E_Y \C \mathcal{F}_n E_X \cong \Tilde{H}^{\mathrm{top}}\left(X, Y\right) \otimes \det(Y) \otimes \det(X),\] with $\Tilde{H}(X, Y)$ the poset cohomology of the open interval in $\Pi_n$, using the convention that $\Tilde{H}^{\mathrm{top}}\left(X, X\right)$ is the trivial
    %$\stab_{S_n}(X)-$  
    representation.
\end{prop}
By properties of dual representations and induction, we are able to consider the \textit{homology} of intervals $\Tilde{H}_{\mathrm{top}}\left(X, Y\right)$ instead when combining \cref{prop:double-idemp-sapces} and \cref{prop:changing-to-hom}.

\subsubsection{Base case: the spaces $E_n \C\mathcal{F}_nE_\mu$}
A key step in proving \cref{conj:typeA-comp-factors} is to understand the case $\lambda = n.$ If $\{X_\mu\}$ are set partitions with block sizes $\mu$ and $\hat{1}$ denotes the maximal element of $\Pi_n$, then by \cref{subsubsec:homology-intervals}, \begin{align}
     \sum_{\mu \neq \emptyset}\mathbf{z}_\mu \cdot \ch(E_{|\mu|}\C \mathcal{F}_{|\mu|}E_\mu) = \sum_{\mu \neq \emptyset} \mathbf{z}_\mu \cdot \ch \left({\Tilde{H}}_{\mathrm{top}}\left(X_\mu, \hat{1}\right) \otimes \det\left(X_\mu\right)\Big \uparrow_{\stab_{S_{|\mu|}}\left(X_\mu\right)}^{S_{|\mu|}} \right) .\label{eqn:base-case-1}
\end{align} Sundaram  studied the homology of the partition lattice in great depth. In \cite[proof of Thm 1.4]{SundaramAdvances}, she studies the $\stab_{S_{|\mu|}}\left(X_\mu\right)-$representations ${\Tilde{H}}_{\mathrm{top}}\left(X_\mu, \hat{1}\right).$ Adjusting her work with the $\det(X_\mu)$ twists reframes \cref{eqn:base-case-1} as 
\begin{equation}
\label{eqn:base-case-1-reframed}
    \sum_{r \geq 1} L_r[z_1h_1 + z_2h_2  + \cdots].
\end{equation}
In \cite[Equation 2.1]{gesselreutenauer}, Gessel--Reutenauer interpret the symmetric functions $L_r$ with necklaces. Using their interpretation, we construct a necklace bijection to rewrite \eqref{eqn:base-case-1-reframed} as \[\sum_{\substack{\text{Lyndon}\\w}}\sum_{m \geq 1}\mathbf{z}_{w^m}L_m[h_w].\]

\subsubsection{General case: the spaces $E_\lambda \C \mathcal{F}_n E_\mu$}
The general case comes down to understanding the action of the subgroups $\stab_{S_n}(X) \cap \stab_{S_n}(Y)$ on $\Tilde{\mathcal{H}}_{\mathrm{top}} \left(X, Y\right) \otimes \det(X) \otimes \det(Y)$. By identifying the intersections of these stabilizer subgroups, we recast this action as the action of (wreath) products of smaller subgroups on products of smaller partition lattices (with appropriate twists). Sundaram's work in \cite[Prop 2.1, 2.3]{SundaramJerusalem} is helpful in reducing these representations to our base case. Then, a generating function argument comes into play.


\section{A note on other Coxeter types}
Much of this work holds in all Coxeter types. The face algebra, the descent algebra, and Bidigare's theorem were each originally defined or proved in all types. The representation theory of the descent algebra has been studied in other types thoroughly in \cite{Bergerons-hyper1, Bergerons-general, Bergerons-hyper2}. Saliola's work in \cite{saliolaquiverdescalgebra} is also for general type, so analogues of \cref{prop:double-idemp-sapces} and \cref{prop:changing-to-hom} hold. In fact, an analogue of \cref{prop:sign-iso} holds for all types. In \cite[Thm 1.1]{blesshohlshock}, Blessenohl--Hohlweg--Schocker  generalize Gessel--Reutenauer's result to general type. Their work helps us prove that as a descent algebra module, the sign isotypic subspace of the face algebra is the simple indexed by the cycle type\footnote{in the sense of Aguiar--Mahajan \cite[\S 5.5]{Aguiar-Mahajan}} of the longest word. Unfortunately, we do not have analogues of \cref{conj:typeA-comp-factors} since our proof relies heavily on the structure of the partition lattice and symmetric functions.

%The author is currently working

\acknowledgements{The author would like to thank Vic Reiner for proposing this project and providing invaluable guidance at every stage; Sheila Sundaram for helpful discussions about \cite{SundaramAdvances} and for sparking the idea for the combinatorial proof of the base case; Esther Banaian, Sarah Brauner, Trevor Karn, Franco Saliola, and Ben Steinberg for valuable conversations.}

\printbibliography



\end{document}