%% 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]{FPSAC2025}
\articlenumber{126}
%% 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}

\usepackage{tikz, bm, young}

\newcommand{\llambda}{{\bm \lambda}}
\newcommand{\CC}{{\mathbb{C}}}
\newcommand{\ZZ}{{\mathbb{Z}}}

\newcommand{\SSS}{{\mathcal{S}}}

\newcommand{\zz}{{\mathbf{z}}}

\newcommand{\initial}{{\mathrm{in}}}


\newcommand{\MMM}{{\mathcal{M}}}
\newcommand{\PM}{{\mathcal{PM}}}
\newcommand{\KKK}{{\mathcal{K}}}

\newcommand{\BBB}{{\mathcal{B}}}

\newcommand{\Zpoints}{{\mathcal{Z}}}

\newcommand{\gr}{{\mathrm{gr}}}
\newcommand{\grFrob}{{\mathrm{grFrob}}}
\newcommand{\Frob}{{\mathrm{Frob}}}
\newcommand{\lis}{{\mathrm{lis}}}
\newcommand{\Mat}{{\mathrm{Mat}}}
\newcommand{\Hilb}{{\mathrm{Hilb}}}
\newcommand{\End}{{\mathrm{End}}}
\newcommand{\SYT}{{\mathrm{SYT}}}
\newcommand{\Res}{{\mathrm{Res}}}

\newcommand{\xx}{{\mathbf{x}}}
\newcommand{\II}{{\mathbf{I}}}
\newcommand{\RRR}{{\mathbf{R}}}

\newcommand{\sss}{{\mathfrak{s}}}
\newcommand{\mmm}{{\mathfrak{m}}}

\newcommand{\symm}{{\mathfrak{S}}}


\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{defn}[thm]{Definition}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{prob}[thm]{Problem}

\usepackage{lipsum}

%% define your title in the usual way
\title[Matrix loci, orbit harmonics, and shadow play]{Matrix loci, orbit harmonics, and shadow play}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
%% for more than 3 names, use the Oxford comma: One Author, Two Author, Red Author, \and Blue Author
\author[J. M. Liu, Y. Ma, B. Rhoades, and H. Zhu]{\texorpdfstring{Jasper M. Liu \thanks{\href{mailto:mol008@ucsd.edu}{mol008@ucsd.edu}. JML was partially supported by NSF Grant DMS-2246846.}\addressmark{1}, {Yichen Ma}\thanks{\href{mailto:ym476@cornell.edu}{ym476@cornell.edu}.}\addressmark{2}, {Brendon Rhoades}\thanks{\href{mailto:bprhoades@ucsd.edu}{bprhoades@ucsd.edu}. BR was partially supported by NSF Grant DMS-2246846.}\addressmark{1}, \and {Hai Zhu}\thanks{\href{mailto:zhuhai1686@stu.pku.edu.cn}{zhuhai1686@stu.pku.edu.cn}}\addressmark{3}}{Jasper M. Liu , {Yichen Ma}, {Brendon Rhoades}, and {Hai Zhu}}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, University of California, San Diego \\ \addressmark{2}Department of Mathematics, Cornell University \\ \addressmark{3}School of Mathematical Sciences, Peking University}

%% 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{Let $\xx_{n \times n}$ be an $n \times n$ matrix of variables and let $\CC[\xx_{n \times n}]$ be the polynomial ring in these variables. We consider the ideal $I_n \subset \CC[\xx_{n \times n}]$ generated by all row sums, column sums, and products of variables in the same row or column. We prove $R_n = \CC[\xx_{n \times n}]/I_n$ has standard monomial theory governed by the Viennot shadow line avatar of the Schensted correspondence and has Hilbert series given by the longest increasing subsequence distribution on permutations (up to reversal). The ring $R_n$ coincides with the orbit harmonics quotient ring attached to the permutation matrix locus in the space $\Mat_{n \times n}(\CC)$ of $n \times n$ complex matrices. With $R_n$ as motivation, we prove results on orbit harmonics quotients for other matrix loci.}

%% 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{quotient ring, permutation, increasing subsequence, $\symm_n$-module}

%% 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, giveninits]{biblatex}
\addbibresource{main.bib}
\appto\bibfont{\setlength{\emergencystretch}{.5em}}
%% 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{Introduction}
\label{sec:Introduction}

This extended abstract covers recent developments \cite{Liu, LMRZ, RhoadesViennot} in the theory of orbit harmonics as applied to loci of $n \times n$ matrices, resulting in quotient rings reflecting combinatorial properties of these matrices. Our fundamental example is as follows.

Let $\symm_n$ denote the symmetric group of permutations of $[n] := \{1, \dots, n\}$. An {\em increasing subsequence} of $w \in \symm_n$ is a set $1 \leq i_1 < \cdots < i_k \leq n$  such that $w(i_1) < \cdots < w(i_k)$. Write $\lis(w)$ for the size of a longest increasing subsequence of $w$ and let
\begin{equation} a_{n,k} := \# \{ w \in \symm_n \,:\, \lis(w) = k \}.\end{equation}
Baik, Deift, and Johansson proved \cite{BDJ} that the sequence $(a_{n,1}, \dots, a_{n,n})$ converges as $n \to \infty$ (after  renormalization) to the {\em Tracy--Widom distribution} modeling the largest eigenvalue of a random GUE matrix.

We show that $(a_{n,1}, \dots, a_{n,n})$ is the Hilbert series of a graded ring, after reversal. Let $\xx_{n \times n} = (x_{i,j})_{1 \leq i,j \leq n}$ be an $n \times n$ matrix of variables and let $\CC[\xx_{n \times n}]$ be the polynomial ring in these variables.


\begin{figure}[!htb]
   \begin{minipage}{0.48\textwidth}
     \centering
     \includegraphics[width=.8\linewidth]{fpsac2025_sample/S_n Hilb.jpeg}
     \caption{$\Hilb(R(\symm_{65});q)$}
     \label{fig:SHilb}
   \end{minipage}\hfill
   \begin{minipage}{0.48\textwidth}
     \centering
     \includegraphics[width=.8\linewidth]{fpsac2025_sample/type B.jpeg}
     \caption{$\Hilb(R(\symm_{40,2});q)$}
     \label{fig:BHilb}
   \end{minipage}
\end{figure}

\begin{defn}
\label{def:R}
Let $I_n \subseteq \CC[\xx_{n \times n}]$ be the ideal generated by the following polynomials:
\begin{itemize}
\item all row sums $\sum_{j = 1}^n x_{i,j}$ for $1 \leq i \leq n$ and column sums $\sum_{i=1}^n x_{i,j}$ for $1 \leq j \leq n$, and
\item all products $x_{i,j} \cdot x_{i,j'}$ or $x_{i,j} \cdot x_{i',j}$ of variables in the same row or column, including squares $x_{i,j}^2$ of variables.
\end{itemize}
Write $R_n := \CC[\xx_{n \times n}]/I_n$ for the corresponding quotient ring.
\end{defn}

Despite its simple definition, the ring $R_n$ has deep ties to permutation combinatorics. It is a quotient of the Stanley--Reisner ring of the {\em chessboard complex} \cite{BLVZ}.
The ideal $I_n$ is homogeneous, so $R_n$ is a graded $\CC$-algebra. The product $\symm_n \times \symm_n$ of symmetric groups acts naturally on the rows and columns of the matrix of variables $\xx_{n \times n}$, and this induces an action of $\symm_n \times \symm_n$ on $\CC[\xx_{n \times n}]$. The ideal $I_n$ is stable under this action, so $R_n$ is also a graded $(\symm_n \times \symm_n)$-module. 

If $A = \bigoplus_{i \geq 0} A_i$ is a graded algebra,  the {\em Hilbert series} is $\Hilb(A;q) := \sum_{i \geq 0} \dim A_i \cdot q^i$. We prove (\Cref{cor:hilbert-series}) that the Hilbert series of $R_n$ is essentially the generating function of the statistic $\lis$ on $\symm_n$:
\begin{equation}
\label{eq:lis-hilbert}
\Hilb(R_n;q) = \sum_{i = 0}^{n-1} a_{n,n-i} \cdot q^i.
\end{equation}
See \Cref{fig:SHilb} for the Hilbert series at $n=65$.
Equation~\eqref{eq:lis-hilbert} holds because the {\em standard monomial basis} of $R_n$ (with respect to the `Toeplitz term order') may be read off from the Viennot shadow line avatar of the Schensted correspondence (\Cref{thm:shadow-basis}). With respect to a fixed term order, any polynomial ring quotient has a unique standard monomial basis, but this basis does not generally have a nice structure. By contrast, \Cref{thm:shadow-basis} says (loosely) that the standard monomial theory of $R_n$ `knows' the Schensted bijection.

We extend Equation~\eqref{eq:lis-hilbert} to give the graded $(\symm_n \times \symm_n)$-module structure of $R_n$; we show (\Cref{thm:graded-module-structure}) that the degree $d$ piece of $R_n$ is isomorphic to $\bigoplus_\lambda \End_\CC(V^\lambda)$ where the direct sum is over partitions $\lambda \vdash n$ whose first row has length $n-d$ and $V^\lambda$ is the $\symm_n$-irreducible associated to $\lambda$.


The ring $R_n$ turns out (\Cref{thm:shadow-basis}) to arise from a general method in combinatorial deformation theory called {\em orbit harmonics}. This is a machine which linearly deforms a finite locus $\Zpoints$ of points in an affine space $V$ to the origin, resulting in a graded quotient $R(\Zpoints)$ of the coordinate ring $\CC[V]$; see \Cref{sec:Background} for details. If we take $V = \Mat_{n \times n}(\CC)$ to be the affine space of $n \times n$ complex matrices and regard $\symm_n \subseteq V$ as the locus of permutation matrices, we prove (\Cref{thm:shadow-basis}) that $R(\symm_n) = R_n$.

The identification $R(\symm_n) = R_n$ and our theorems on $R_n$ motivate the study of $R(\Zpoints)$ for other matrix loci $\Zpoints \subseteq \Mat_{n \times n}(\CC)$. See \Cref{fig:BHilb} for the Hilbert series when $\Zpoints$ consists of $40 \times 40$ signed permutation matrices. In \Cref{sec:Colored} we give results on the locus $\symm_{n,r}$ of $r$-colored permutation matrices and in \Cref{sec:Involution} we give results on various loci of involution permutation matrices. We close in \Cref{sec:Future} with some open problems.







\section{Background}
\label{sec:Background}


\subsection{Commutative algebra and orbit harmonics}

Let $\xx$ be a finite set of variables and let $\CC[\xx]$ be the polynomial ring in $\xx$. A total order $\prec$ on the monomials in $\CC[\xx]$ is a {\em term order} if $1 \preceq m$ for all monomials $m$ and
\begin{center}
    for all monomials $m, m', m''$, if $m \preceq m'$ we have $m \cdot m'' \preceq m' \cdot m''$.
\end{center}
For a variable order $\xx = \{ x_1 < \cdots < x_N \}$, the {\em lexicographic} term order is $x_1^{a_1} \cdots x_N^{a_N} \prec x_1^{b_1} \cdots x_N^{b_N}$ if there exists $1 \leq i \leq N$ with $a_j  = b_j$ for $j < i$ and $a_i < b_i$. 

 If $f \in \CC[\xx]$ is nonzero and $\prec$ is a term order, write $\initial_\prec (f)$ for the $\prec$-largest monomial appearing with nonzero coefficient in $f$. 
 Let $I \subseteq \CC[\xx]$ be an ideal. The following set of monomials descends to a basis of $\CC[\xx]/I$ called the {\em standard monomial basis}
 $$ \BBB := \{ \text{monomials $m$ in $\CC[\xx]$} \,:\, m \neq \initial_\prec(f) \text{ for any nonzero $f \in I$} \}. $$

 

 
For  $f \in \CC[\xx] - \{0\}$, let $\tau(f) \in \CC[\xx]$ be the top-degree homogeneous component of $f$. Explicitly, if $f = f_d + \cdots + f_1 + f_0$ where $f_i$ is homogeneous of degree $i$ and $f_d \neq 0$, we have $\tau(f) = f_d$. If $I \subseteq \CC[\xx]$ is an ideal, the {\em associated graded ideal} is
$$ \gr \, I := ( \tau(f) \,:\, f \in I, \, \, f \neq 0) \subseteq \CC[\xx].$$


Let $V$ be a finite-dimensional $\CC$-vector space with coordinate ring $\CC[V]$. If $x_1, \dots, x_N$ is a basis of the dual space $V^*$, then  $\CC[V] = \CC[x_1, \dots, x_N]$. Let $\Zpoints \subseteq V$ be a finite locus. We have the vanishing ideal 
$$\II(\Zpoints) := \{ f \in \CC[V] \,:\, f(\zz) = 0 \text{ for all $\zz \in \Zpoints$} \}.$$
Since $\Zpoints$ is finite, the quotient $\CC[V]/\II(\Zpoints)$ coincides with the algebra $\CC[\Zpoints]$ of all functions $\Zpoints \to \CC$. The {\em orbit harmonics method} gives a vector space isomorphism
\begin{equation}
    \label{eq:orbit-harmonics-isomorphism}
    \CC[\Zpoints] = \CC[V]/\II(\Zpoints) \cong \CC[V]/\gr \, \II(\Zpoints)
\end{equation}
where $\CC[V]/\gr \, \II(\Zpoints)$ has the additional structure of a graded vector space. If $G \subseteq GL(V)$ is a finite linear group and the locus $\Zpoints$ is $G$-stable, \eqref{eq:orbit-harmonics-isomorphism} is an isomorphism of $G$-modules, where $\CC[V]/\gr \, \II(\Zpoints)$ has the additional structure of a graded $G$-module. We write
\begin{equation}
    R(\Zpoints) := \CC[V]/\gr \, \II(\Zpoints)
\end{equation}
for the graded orbit harmonics quotient ring of a finite locus $\Zpoints \subseteq V$. Geometrically, \eqref{eq:orbit-harmonics-isomorphism} corresponds to a flat family which linearly deforms the reduced locus $\Zpoints$ to a subscheme of $V$ with degree $\# \Zpoints$ supported at the origin, as shown schematically below. Orbit harmonics quotients $R(\Zpoints)$ arise in the study of Springer fibers \cite{GP}, delta operator coinvariant theory \cite{HRS}, Donaldson--Thomas theory \cite{RRT}, and Ehrhart theory \cite{RR}.


\begin{center}
 \begin{tikzpicture}[scale = 0.2]
\draw (-4,0) -- (4,0);
\draw (-2,-3.46) -- (2,3.46);
\draw (-2,3.46) -- (2,-3.46);

 \fontsize{5pt}{5pt} \selectfont
\node at (0,2) {$\bullet$};
\node at (0,-2) {$\bullet$};


\node at (-1.73,1) {$\bullet$};
\node at (-1.73,-1) {$\bullet$};
\node at (1.73,-1) {$\bullet$};
\node at (1.73,1) {$\bullet$};

\draw[thick, ->] (6,0) -- (8,0);


\draw (10,0) -- (18,0);
\draw (12,-3.46) -- (16,3.46);
\draw (12,3.46) -- (16,-3.46);

\draw (14,0) circle (15pt);
\draw(14,0) circle (25pt);
\node at (14,0) {$\bullet$};



 \end{tikzpicture}
\end{center}
 
 
 
 



\subsection{Representation theory of \texorpdfstring{$\symm_n$}{Sn} and shadow lines}

For $n \geq 0$, a {\em partition} of $n$ is a sequence $\lambda = (\lambda_1 \geq \lambda_2 \geq \cdots )$ of positive integers with $\lambda_1 + \lambda_2 + \cdots = n$. We write $\lambda \vdash n$ to mean that $\lambda$ is a partition of $n$ and let $|\lambda| := n$. We identify $\lambda$ with its (English) Young diagram with $\lambda_i$ left-justified boxes in row $i$. A {\em standard $\lambda$-tableau} is a filling of the boxes of $\lambda$ with $1, 2, \dots, n$ which increases across rows and down columns. Let $\SYT(\lambda)$ be the set of standard $\lambda$-tableaux.

Let $\Lambda = \bigoplus_{n \geq 0} \Lambda_n$ be the ring of symmetric functions.  Bases of $\Lambda_n$ are indexed by partitions $\lambda \vdash n$; we will use the {\em Schur basis} $\{s_\lambda \,:\, \lambda \vdash n\}$.
Irreducible representations of $\symm_n$  are also indexed by  partitions  $\lambda \vdash n$; we write $V^\lambda$ for the $\symm_n$-irreducible attached to $\lambda \vdash n$. If $V$ is a finite-dimensional $\symm_n$-module, there exist unique integers $c_\lambda \geq 0$ such that $V \cong \bigoplus_{\lambda \vdash n} c_\lambda V^\lambda$. The {\em Frobenius image} of $V$ is the symmetric function 
$$\Frob(V) := \sum_{\lambda \vdash n} c_\lambda \cdot s_\lambda.$$
More generally, if $V = \bigoplus_{i \geq 0} V_i$ is a graded $\symm_n$-module with each $V_i$ finite-dimensional, the {\em graded Frobenius image} is
$$ \grFrob(V;q) := \sum_{i \geq 0} \Frob(V_i) \cdot q^i.$$


The {\em Schensted correspondence} \cite{Schensted} is an explicit bijection
\begin{equation}
    \label{eq:schensted-bijection}
    \symm_n \longrightarrow \bigsqcup_{\lambda \vdash n} \SYT(\lambda) \times \SYT(\lambda).
\end{equation}
from $\symm_n$ to pairs $(P,Q)$ of $n$-box standard tableaux of the same shape. We refer the reader to Sagan's textbook \cite{Sagan} for a wonderful exposition on this bijection. For example, if $w = [4,3,1,2,7,5,6] \in \symm_7$ then $w \mapsto (P(w), Q(w))$ where $P(w), Q(w)$ are shown below.
$$
\begin{Young}
,& ,& ,& 1 & 2& 5& 6\cr
,P(w):& ,& ,&  3 & 7\cr
,& ,& ,& 4 \cr
\end{Young} \quad \quad
\begin{Young}
 ,&,&,&  1 & 4& 5& 7\cr
 ,Q(w):&,&,&  2 & 6\cr
  ,&,&,& 3 \cr
\end{Young}$$
Our example permutation $w = [4,3,1,2,7,5,6]$ has $\lis(w) = 4$, and both $P(w),Q(w)$ have 4 boxes in their first row. This is a general phenomenon.


    





\begin{thm}[Schensted \cite{Schensted}]
    \label{thm:schensted-theorem} 
    Suppose $w \in \symm_n$ maps to $(P(w),Q(w))$ under the Schensted bijection, and that $P(w), Q(w)$ have the common shape $\lambda \vdash n$. Then $\lis(w) = \lambda_1$.
\end{thm}







\begin{figure}
\begin{center}
    \begin{tikzpicture}[scale = 0.5]
        \draw[step = 1.0,black,very thin] (1,1) grid (7,7);

        \node at (1,4) {$\bullet$};
        \node at (2,3) {$\bullet$};
        \node at (3,1) {$\bullet$};
        \node at (4,2) {$\bullet$};
        \node at (5,7) {$\bullet$};
        \node at (6,5) {$\bullet$};
        \node at (7,6) {$\bullet$};
    \end{tikzpicture}
    \begin{tikzpicture}[scale = 0.5]
        \draw[step = 1.0,black,very thin] (1,1) grid (7,7);

        \node at (1,4) {$\bullet$};
        \node at (2,3) {$\bullet$};
        \node at (3,1) {$\bullet$};
        \node at (4,2) {$\bullet$};
        \node at (5,7) {$\bullet$};
        \node at (6,5) {$\bullet$};
        \node at (7,6) {$\bullet$};

        \draw[black,ultra thick] (1,8) -- (1,4) -- (2,4) -- (2,3) -- (3,3) -- (3,1) -- (8,1);

        \draw[black,ultra thick] (4,8) -- (4,2) -- (8,2);

        \draw[black,ultra thick] (5,8) -- (5,7) -| (6,5) -- (8,5);

        \draw[black,ultra thick] (5,8) -- (5,7) -| (6,5) -- (8,5);

        \draw[black,ultra thick] (7,8) |- (8,6);

        \node at (2,4) {${\color{red} \bullet}$};
        \node at (3,3) {${\color{red} \bullet}$};
        \node at (6,7) {${\color{red} \bullet}$};
        \draw[step = 1.0,black,very thin] (9,1) grid (15,7);

       

        

        \draw[black,ultra thick] (10,8) |- (11,4) |- (16,3);

        \draw[black,ultra thick] (14,8) |- (16,7);

        \draw[black,ultra thick,dotted] (11,8) |- (16,4);

        \node at (10,4) {${\color{red} \bullet}$};
        \node at (11,3) {${\color{red} \bullet}$};
        \node at (14,7) {${\color{red} \bullet}$};

        \node at (11,4) {${\color{blue} \bullet}$};
    \end{tikzpicture}
\end{center}

    \caption{The Viennot construction on $w = [4,3,1,2,7,5,6] \in \symm_7$. We have the shadow set $\SSS(w) = \{(2,4),(3,3),(6,7)\}.$}
    \label{fig:shadow}
\end{figure}

Schensted defined the bijection \eqref{eq:schensted-bijection} as an algorithm involving insertion and bumping. We will use a beautiful `geometric' reformulation of \eqref{eq:schensted-bijection} due to Viennot \cite{Viennot}. We represent a permutation $w \in \symm_n$ with its {\em graph} $\{(i,w(i)) \,:\, 1 \leq i \leq n \}$. The left of \Cref{fig:shadow} shows the graph of our example permutation $w = [4,3,1,2,7,5,6]$. 

Shine a light northeast from the origin onto the graph of $w$. The lattice points in this graph cast overlapping shadows to the northeast. The {\em first shadow line} $L_1$ is the boundary of the shaded region. If we remove $L_1$ and shine the light again, we obtain the {\em second shadow line} $L_2$. Iterating, we obtain the {\em third shadow line} $L_3$, the {\em fourth shadow line} $L_4$, and so on. See the middle of \Cref{fig:shadow} for an example. Observe that the $y$-coordinates of the infinite horizontal rays of the shadow lines are $1,2,5,6$ (which is the first row of $P(w)$) and the $x$-coordinates of the infinite vertical rays are $1,4,5,7$ (which is the first row of $Q(w)$).
The northeastern corners of the shadow lines of $w$ play an important role.

\begin{defn}
    \label{def:shadow-set}
    Let $w \in \symm_n$. The {\em shadow set} $\SSS(w) \subseteq [n] \times [n]$ is the set of pairs $(i,j)$ of coordinates of the northeastern corners of the shadow lines of $w$.
\end{defn}

In our example, the shadow set (shown in red) is $\SSS(w) = \{(2,4),(3,3),(6,7)\}$. We may apply the  shadow construction to $\SSS(w)$, resulting in a new family of shadow lines; these are shown in solid black on the right of \Cref{fig:shadow}. The $y$-coordinates of the horizontal rays are $3,7$ (which is the second row of $P(w)$) and the $x$-coordinates of the vertical rays are $2,6$ (which is the second row of $Q(w)$). Viennot proved \cite{Viennot} that iteration on $w, \SSS(w), \SSS(\SSS(w)), \dots$ gives the tableaux $P(w), Q(w)$ for any $w \in \symm_n$.
































\section{The quotient ring \texorpdfstring{$R_n$}{Rn} and the permutation matrix locus}
\label{sec:R}


Algebraic properties of the ring $R_n$ of \Cref{def:R} are governed by the combinatorics of Viennot shadow lines. For a permutation $w \in \symm_n$, the {\em shadow monomial} $\sss(w)$ is the product of variables indexed by the shadow set of $w$, i.e.
\begin{equation}
    \sss(w) := \prod_{(i,j) \in \SSS(w)} x_{i,j}.
\end{equation}
In the example of \Cref{fig:shadow} we have $\sss(w) = x_{2,4} \cdot x_{3,3} \cdot x_{6,7}$. The {\em Toeplitz term order} on $\CC[\xx_{n \times n}]$ is  lexicographic order with respect to the variable ordering
$$ x_{1,1} \prec x_{1,2} \prec x_{2,1} \prec x_{1,3} \prec x_{2,2} \prec x_{3,1} \prec \cdots \prec x_{n-1,n} \prec x_{n,n-1} \prec x_{n,n}.$$



\begin{thm}
\label{thm:shadow-basis}
We have the equality $\gr \, \II(\symm_n) = I_n$ of ideals in $\CC[\xx_{n \times n}]$ where $\symm_n \subseteq \Mat_{n \times n}(\CC)$ is the locus of $n \times n$ permutation matrices. The standard monomial basis of $R_n = \CC[\xx_{n \times n}]/I_n$ with respect to the Toeplitz term order is the set $\{ \sss(w) \,:\, w \in \symm_n \}$ of shadow monomials.
\end{thm}

\begin{proof}
    (Sketch.) Every generator of $I_n$ is the highest degree component of an element of $\II(\symm_n)$. The generator $\sum_{j = 1}^n x_{i,j}$ is the top component of $\sum_{j = 1}^n x_{i,j}-1 \in \II(\symm_n)$ and similarly for $\sum_{i=1}^n x_{i,j}$. The square $x_{i,j}^2$ is the top component of $x_{i,j} (x_{i,j} - 1) \in \II(\symm_n)$, and we have  $x_{i,j} \cdot x_{i,j'}, x_{i,j} \cdot x_{i',j} \in \II(\symm_n)$ when $j \neq j'$ and $i \neq i'$. This proves $I_n \subseteq \gr \, \II(\symm_n)$.

    Let $\BBB$ be the standard monomial basis for $R_n = \CC[\xx_{n \times n}]/I_n$ with respect to the Toeplitz term order. It suffices to prove the containment
    \begin{equation}
    \label{eq:desired-containment}
        \BBB \subseteq \{ \sss(w) \,:\, w \in \symm_n \}
    \end{equation}
    for then one has the chain of (in)equalities
    \begin{equation}
        \dim_\CC R_n = |\BBB| \leq \# \{ \sss(w) \,:\, w \in \symm_n \} \leq n! = \dim_\CC R(\symm_n) \leq \dim_\CC R_n
    \end{equation}
    where the final inequality $\dim_\CC R(\symm_n) \leq \dim_\CC R_n$ holds because $I_n \subseteq \gr \, \II(\symm_n)$. This forces $I_n = \gr \, \II(\symm_n)$ and, together with \eqref{eq:desired-containment}, we have $\BBB = \{ \sss(w) \,:\, w \in \symm_n \}$.

    The required containment \eqref{eq:desired-containment} itself is established as follows. For subsets $S,T \subseteq [n]$ with $|S| \leq |T|$, define polynomials $a_{S,T},b_{S,T} \in \CC[\xx_{n \times n}]$ by
    \begin{equation}
        a_{S,T} := \sum_{f:S \hookrightarrow T} \prod_{s \in S} x_{s,f(s)} \quad \quad
        b_{S,T} := \sum_{f:S \hookrightarrow T} \prod_{s \in S} x_{f(s),s}
    \end{equation}
    where both sums are over injective maps $f: S \hookrightarrow T$. One uses induction to prove
    \begin{equation}
    \label{eq:ab-relations}
    \text{$a_{S,T},b_{S,T} \in I_n$ whenever $|S| + |T| > n$.}
    \end{equation}
    Let $m$ be a monomial in $\CC[\xx_{n \times n}]$. If $m$ is not squarefree, or if $m$ contains two variables in the same row or column, then $m \in I_n$ so that $m \notin \BBB$. If the variables in $m$ form a non-attacking rook placement on $[n] \times [n]$ which is not the shadow set of a permutation $w \in \symm_n$, one argues using the relations \eqref{eq:ab-relations} that $m$ is the Toeplitz-leading monomial of an element of $I_n$.   
\end{proof}

If $w \in \symm_n$, Schensted's \Cref{thm:schensted-theorem} and the definition of $\sss(w)$ imply
\begin{equation}
    \lis(w) + \deg (\sss(w)) = n.
\end{equation}
This leads to the following corollary of \Cref{thm:shadow-basis}. Recall that $a_{n,k}$ counts permutations $w \in \symm_n$ with $\lis(w) = k$.


\begin{cor}
\label{cor:hilbert-series}
The Hilbert series of $R_n$ is given by $\Hilb(R_n;q) = \sum_{i = 0}^{n-1} a_{n,n-i} \cdot q^i$.
\end{cor}


Row and column permutation on $\xx_{n \times n}$ turns $R_n$ into a graded $(\symm_n \times \symm_n)$-module. The module structure of the degree $d$ piece $(R_n)_d$ is as follows. If $G$ is a group and $W$ is a $G$-module, then $\End_\CC(W)$ is a $(G \times G)$-module via $((g_1,g_2) \cdot \varphi)(w) := g_1 \cdot \varphi(g_2^{-1} \cdot w)$ for $g_1,g_2 \in G$, $\varphi \in \End_\CC(W)$, and $w \in W$. 
%We have $\End_\CC(W) \cong W \otimes_\CC W^*$ as $(G \times G)$-modules.




\begin{thm}
\label{thm:graded-module-structure}
For $0 \leq d \leq n-1$, we have an isomorphism of $(\symm_n \times \symm_n)$-modules
$$(R_n)_d \cong \bigoplus_{\substack{\lambda \vdash n \\ \lambda_1 = n-d}} \End_\CC(V^\lambda).$$
\end{thm}

\begin{proof}
    (Sketch.) If $A = \bigoplus_{i \geq 0} A_i$ is a graded algebra, write $A_{\leq d} := \bigoplus_{i=0}^d A_i$. \Cref{thm:shadow-basis} says that $R_n = \CC[\xx_{n \times n}]/\gr \, \II(\symm_n)$, where $\symm_n \subseteq \Mat_{n \times n}(\CC)$ is the permutation matrix locus. For fixed $d$, it follows that 
    \begin{equation}
    \label{eq:orbit-isomorphism}
        (R_n)_{\leq d} \cong_{\symm_n \times \symm_n} \CC[\xx_{n \times n}]_{\leq d}/(\II(\symm_n) \cap \CC[\xx_{n \times n}]_{\leq d})
    \end{equation}
    as ungraded $(\symm_n \times \symm_n)$-modules. The quotient $\CC[\xx_{n \times n}]_{\leq d}/(\II(\symm_n) \cap \CC[\xx_{n \times n}]_{\leq d})$ is the space of functions $f: \symm_n \to \CC$ which are restrictions of polynomials in $\CC[\xx_{n \times n}]_{\leq d}$. With this identification, Hamaker and Rhoades proved \cite[Theorem 3.8]{HR}
    \begin{equation}
    \label{eq:hr-isomorphism}
        \CC[\xx_{n \times n}]_{\leq d}/(\II(\symm_n) \cap \CC[\xx_{n \times n}]_{\leq d}) \cong \bigoplus_{\substack{\lambda \vdash n \\ \lambda_1 \geq n-d}} \End_\CC(V^\lambda).
    \end{equation}
    Since the isomorphisms \eqref{eq:orbit-isomorphism} and \eqref{eq:hr-isomorphism} of ungraded $(\symm_n \times \symm_n)$-modules hold for any $d$ and the group algebra $\CC[\symm_n \times \symm_n]$ is semisimple, the theorem follows.
\end{proof}







\section{Matrix groups and colored permutation matrices}
\label{sec:Colored}

\Cref{thm:shadow-basis} states that the quotient ring $R_n = \CC[\xx_{n \times n}]/I_n$ of \Cref{def:R} is the orbit harmonics ring $R(\symm_n)$ of the permutation matrix locus $\symm_n \subseteq \Mat_{n \times n}(\CC)$. This opens the door to the following problem.

\begin{prob}
    \label{prob:matrix-group}
    Let $G \subseteq \Mat_{n \times n}(\CC)$ be a finite matrix group. Then $R(G)$ is a graded $(G \times G)$-module. Determine the graded structure of this module.
\end{prob}

With \Cref{thm:shadow-basis} in mind, $\Hilb(R(G);q)$ is a kind of `longest increasing subsequence distribution' for $G$. We present a solution to \Cref{prob:matrix-group} for the group of colored permutation matrices.

A {\em monomial matrix} is a square matrix with a unique nonzero entry in each row and column. For $n, r > 0$, the group $\symm_{n,r}$ of {\em $r$-colored permutations of $[n]$} consists of $n \times n$ monomial matrices whose nonzero entries are $r^{th}$ roots-of-unity. Letting $\zeta := \exp(2 \pi i/r)$, we think of $\zeta^0, \zeta^1, \dots, \zeta^{r-1}$ as `colors'. 

Let $w \in \symm_{n,r}$ be a colored permutation. For $0 \leq p \leq r-1$ define $C_p(w) \subseteq [n] \times [n]$ by
$$C_p(w) := \{ (i,j) \,:\, 1 \leq i \leq n, \, \text{the $(i,j)$-entry of $w$ is $\zeta^p$} \}.$$
If $I,J \subseteq [n]$ are the projections of $C_0(w)$ to the $x$- and $y$-axes, we naturally have a shadow monomial $\sss(C_0(w))$ in the variables $\{ x_{i,j} \,:\, i \in I, \, j \in J \}$ and a longest increasing subsequence $\lis(C_0(w))$. The {\em shadow monomial} of a colored permutation $w \in \symm_{n,r}$ is 
\begin{equation}
    \sss(w) := \sss( C_0(w))^r \times \prod_{p = 1}^{r-1} \prod_{(i,j) \in C_p(w)} x_{i,j}^p.
\end{equation}
For $d \geq 0$, let $c_{n,r,d}$ be the number of $\symm_{n,r}$-shadow monomials of degree $d$:
\begin{equation}
    c_{n,r,d} := \# \{ w \in \symm_{n,r} \,:\, \deg \sss(w) = d \}.
\end{equation}


\begin{thm}
    \label{thm:colored-basis}
    The set $\{ \sss(w) \,:\, w \in \symm_{n,r} \}$ is the standard monomial basis of $R(\symm_{n,r})$ with respect to the Toeplitz term order. We have 
    $\Hilb(R(\symm_{n,r});q) = \sum_{d \geq 0} c_{n,r,d} \cdot q^d$.
\end{thm}



Irreducible representations of $\symm_{n,r}$ are  indexed by $r$-tuples $\llambda = (\lambda^{(0)}, \lambda^{(1)}, \dots, \lambda^{(r-1)})$ of partitions such that $\sum_{p = 0}^{r-1} |\lambda^{(p)}| = n$. If $\llambda$ is such an $r$-tuple, write $V^\llambda$ for the associated $\symm_{n,r}$-irreducible; see e.g. \cite{Macdonald} for its definition. The $\symm_{n,r}$-analog of \Cref{thm:graded-module-structure} is as follows.

\begin{thm}
    \label{thm:colored-character}
    The degree $d$ piece of the graded $(\symm_{n,r} \times \symm_{n,r})$-module $R(\symm_{n,r})$ is isomorphic to 
    $$ R(\symm_{n,r})_d \cong \bigoplus_{\llambda} \End_\CC(V^\llambda)$$
    where $\llambda$ ranges over $r$-tuples $\llambda = (\lambda^{(0)}, \lambda^{(1)}, \dots, \lambda^{(r)})$  which satisfy $\sum_{p = 0}^{r-1} |\lambda^{(p)}| = n$ and $r \cdot (|\lambda^{(0)}| - \lambda^{(0)}_1) + \sum_{p = 1}^{r-1} p \cdot |\lambda^{(p)}| = d$.
\end{thm}










\section{Permutation matrices of involutions}
\label{sec:Involution}


Let $G \subseteq GL_n(\CC)$ be a finite matrix group and $\KKK \subseteq G$ be a subset such that $g \KKK g^{-1} = \KKK$ for all $g \in G$. The conjugation action of $G$ on $\KKK$ induces a graded $G$-module structure on $R(\KKK)$. This leads to the following variant of \Cref{prob:matrix-group}.

\begin{prob}
    \label{prob:conjugacy}
    Let $G \subseteq GL_n(\CC)$ be a finite matrix group and let $\KKK \subseteq G$ be a subset closed under the conjugation action of $G$. Find the graded $G$-module structure of $R(\KKK)$.
\end{prob}

We present solutions to \Cref{prob:conjugacy} when $G = \symm_n$ is the group of permutation matrices and $\KKK$ consists of various classes of involutions. The graded $\symm_n$-modules so obtained have Frobenius images best described in terms of plethysm. If $F, G \in \Lambda$ are symmetric functions, let $F[G] \in \Lambda$ denote the plethysm of $G$ into $F$; see e.g. \cite{Macdonald} for its definition.
%If $F, G \in \Lambda$ are symmetric functions, the plethysm $F[G] \in \Lambda$ is characterized by
%$$(c_1 F_1 + c_2 F_2)[G] = c_1 F_1[G] + c_2 F_2[G] \quad \text{and} \quad (F_1 \cdot F_2)[G] = F_1[G] \cdot F_2[G]$$
%together with the initial conditions
%$$p_d[F] = p_d[F(x_1, x_2, \dots )] = F(x_1^d, x_2^d, \dots) \quad \text{and} \quad c[F] = c.$$
%Here $c, c_1, c_2 \in \CC$ are constants, $F, F_1, F_2, G \in \Lambda$ are symmetric functions, and for $d > 0$ we write $p_d = \sum_{i > 0} x_i^d \in \Lambda$ for the power sum.

We first consider the locus of all permutation matrices of involutions $w \in \symm_n$:
\begin{equation}
    \MMM_n := \{ w \,:\, w \in \symm_n, \,\, w^2 = 1 \} \subseteq \Mat_{n \times n}(\CC).
\end{equation}
The notation $\MMM_n$ reflects the status of its elements as (not necessarily perfect) matchings on $[n]$. If $w \in \MMM_n$, we have the {\em matching monomial}
\begin{equation}
    \mmm(w) := \prod_{i \,:\, w(i) > i} x_{i,w(i)}
\end{equation}
whose variables correspond to the 2-cycles of $w$.



\begin{thm}
    \label{thm:matching}
    The set $\{ \mmm(w) \,:\, w \in \MMM_n \}$ of matching monomials descends to a basis of $R(\MMM_n)$. The graded Frobenius image of $R(\MMM_n)$ is
    $$ \grFrob(R(\MMM_n);q) = \sum_{k = 0}^{\lfloor n/2 \rfloor} s_k[s_2] \cdot s_{n-2k} \cdot q^k.$$
\end{thm}

If $n$ is even, we may consider the locus of perfect matchings
\begin{equation}
    \PM_n := \{ w \in \symm_n \,:\, w^2 = 1, \, \text{$w$ has no fixed points} \} \subseteq \Mat_{n \times n}(\CC).
\end{equation}
The ungraded $\symm_n$-structure of $\PM_n$ is given by the plethysm $\Frob(\CC[\PM_n]) = s_{n/2}[s_2]$. It is known that $s_{n/2}[s_2]$ has $s$-expansion
\begin{equation}
    \label{eq:plethysm-expansion}
   \Frob(\CC[\PM_n]) =  s_{n/2}[s_2] = \sum_{\substack{\lambda \vdash n \\ \text{$\lambda$ even}}} s_\lambda,
\end{equation}
where a partition $\lambda \vdash n$ is {\em even} if all of its parts are even. The graded $\symm_n$-structure of $R(\PM_n)$ refines Equation~\eqref{eq:plethysm-expansion} by the length of the first row of $\lambda$.






\begin{thm}
    \label{thm:matching-character}
    Assume $n$ is even. The graded Frobenius image of $R(\PM_n)$ is
    $$ \grFrob(R(\PM_n);q) = \sum_{\substack{\lambda \vdash n \\ \text{$\lambda$ even}}} s_\lambda \cdot q^{\frac{n-\lambda_1}{2}}.$$
\end{thm}

\Cref{thm:matching-character} and a result of Baik and Rains \cite{BR} show that the coefficient sequence of $\Hilb(R(\PM_n);q)$ converges to the distribution of the largest eigenvalue of a random GSE matrix as $n \to \infty$, after renormalization and reversal.

Finally, we  generalize \Cref{thm:matching-character} by considering arbitrary conjugacy classes of involutions. For $n, a \geq 0$, let
\begin{equation}
    \MMM_{n,a} := \{ w \in \symm_n \,:\, w^2 = 1, \, \, \text{$w$ has $a$ fixed points} \} \subseteq \Mat_{n \times n}(\CC).
\end{equation}
Observe that $\MMM_{n,a} = \varnothing$ unless $a \equiv n \mod 2$. If $F = \sum_\lambda c_\lambda s_\lambda$ is a symmetric function written in the $s$-basis and $k \geq 0$, we write
\begin{equation}
    \{ F \}_{\lambda_1 \leq k} := \sum_{\lambda_1 \leq k} c_\lambda s_\lambda
\end{equation}
for the truncation of its $s$-expansion to partitions whose first row has length $\leq k$. The $s$-expansion of $\grFrob(R(\MMM_{n,a};q)$ is as follows; its $s$-positivity is not combinatorially obvious.





\begin{thm}
    \label{thm:conjugacy-character}
    Suppose $a \equiv n \mod 2$. The graded Frobenius image of $R(\MMM_{n,a})$ is 
    $$ \grFrob(R(\MMM_{n,a});q) = \sum_{d = 0}^{(n-a)/2} \{ s_d[s_2] \cdot s_{n-2d} - s_{d-1}[s_2] \cdot s_{n-2d+2} \}_{\lambda_1 \leq n-2d+a} \cdot q^d.$$
\end{thm}

%It is not so easy to show combinatorially that the formula in \Cref{thm:conjugacy-character} is $s$-positive from Equation~\eqref{eq:plethysm-expansion} and the Pieri rule.



\section{Future directions: log-concavity and distributions}
\label{sec:Future}


A sequence $(b_1, \dots, b_n)$ of positive real numbers is {\em log-concave} if $b_k^2 \geq b_{k-1} \cdot b_{k+1}$ for all $1 < k < n$. Chen conjectured \cite{Chen} that the sequence $(a_{n,1}, \dots, a_{n,n})$ obtained by counting permutations in $\symm_n$ by the length of their longest increasing subsequence is log-concave.

\begin{conj}[Chen \cite{Chen}]
    \label{conj:chen} 
The sequence $(a_{n,1}, \dots, a_{n,n})$ is log-concave.
\end{conj}

Novak and Rhoades formulated \cite{NR} a character-theoretic strengthening of Chen's conjecture. For $1 \leq k \leq n$, let $A_{n,k}$ be the $\symm_n$-module 
$$ A_{n,k} := \bigoplus_{\substack{\lambda \vdash n \\ \lambda_1 = k}} f^\lambda \cdot V^\lambda$$
where $f^\lambda := |\SYT(\lambda)|$. Let $\alpha_{n,k}: \symm_n \to \CC$ be the character of $A_{n,k}$. It is known that $\alpha_{n,k}(1) = \dim_\CC A_{n,k} = a_{n,k}$, so the following conjecture would imply \Cref{conj:chen}.




\begin{conj}[Novak--Rhoades \cite{NR}]
    \label{conj:NR}  
    The class function $\alpha_{n,k} \cdot \alpha_{n,k} - \alpha_{n,k-1} \cdot \alpha_{n,k+1}$ on $\symm_n$ is the character of a representation for $1 \leq k \leq n-2$.
\end{conj}

Since pointwise product of $\symm_n$-class functions is Kronecker product of symmetric functions, \Cref{conj:NR} is likely to be challenging. It follows from \Cref{thm:graded-module-structure} that 
\begin{equation}
    \label{eq:alpha-realization}
    A_{n,n-d} \cong_{\symm_n} \Res^{\symm_n \times \symm_n}_{1 \times \symm_n} (R_n)_d = 
    \Res^{\symm_n \times \symm_n}_{1 \times \symm_n} R(\symm_n)_d
\end{equation}
for $0 \leq d \leq n-1$.
The graded pieces of $R_n$ therefore give an occurrence of the $A_{n,k}$-modules `in nature'. This is the simplest such occurrence known to the authors.

Equation~\eqref{eq:alpha-realization} suggests a further strengthening of \Cref{conj:NR}. Let $G$ be a group. If $V, W$ are $\CC[G]$-modules, let $G$ act on $V \otimes W$ diagonally. A sequence $(V_1, \dots, V_n)$ of $G$-modules is {\em equivariantly log-concave} \cite{MMPR} if there exists a $G$-equivariant injection $V_{k-1} \otimes V_{k+1} \hookrightarrow V_k \otimes V_k$ for all $1 < k < n$. A graded $G$-module $W = \bigoplus_{i = 0}^d W_i$ is {\em equivariantly log-concave} if the sequence $(W_0, W_1, \dots, W_d)$ of $G$-modules is equivariantly log-concave.


\begin{conj}
\label{conj:R-log-concave}
The graded $(\symm_n \times \symm_n)$-module $R_n = R(\symm_n)$ as well as the graded $\symm_n$-modules $R(\MMM_n), R(\MMM_{n,a})$ are equivariantly log-concave.
\end{conj}



%\begin{figure}[!htb]
%   \begin{minipage}{0.48\textwidth}
%     \centering
%     \includegraphics[width=.8\linewidth]{fpsac2025_sample/S_n Hilb.jpeg}
%     \caption{$\Hilb(R(\symm_{65});q)$}
%     \label{fig:SHilb}
%   \end{minipage}\hfill
%   \begin{minipage}{0.48\textwidth}
%     \centering
%     \includegraphics[width=.8\linewidth]{fpsac2025_sample/type B.jpeg}
%     \caption{$\Hilb(R(\symm_{40,2});q)$}
%     \label{fig:BHilb}
%   \end{minipage}
%\end{figure}

\Cref{conj:R-log-concave} has been checked for $n \leq 16$. The first assertion of \Cref{conj:R-log-concave} would imply \Cref{conj:NR}, and therefore \Cref{conj:chen}. Although the Hilbert series of $R(\symm_{n,r})$ does not have log-concave coefficients for $r > 1$, \Cref{fig:BHilb} suggests the following conjecture on its coefficient sequence.



\begin{conj}
    \label{conj:unimodality}
    For fixed $r > 1$, the coefficient sequence of the Hilbert series of $R(\symm_{n,r})$ is unimodal. That is, there exists  $d$ such that $\dim R(\symm_{n,r})_k \leq \dim R(\symm_{n,r})_{k+1}$ for $k < d$ and $\dim R(\symm_{n,r})_k \geq \dim R(\symm_{n,r})_{k+1}$ for $k \geq d$.
\end{conj}

\Cref{fig:SHilb,fig:BHilb} suggest one last conjecture. A polynomial $f(q) = a_0 + a_1 q + \cdots + a_d q^d$  with real coefficients and $a_d \neq 0$ is {\em top heavy} if $a_i \leq a_{d-i}$ for all $i < d/2$. The following conjecture is true for $R(\MMM_n)$.



\begin{conj}
    \label{conj:top_heavy}
    The Hilbert series of $R(\symm_n), R(\symm_{n,r}),$ and $R(\MMM_{n,a})$ are top heavy.
\end{conj}


\acknowledgements{The authors are grateful to Pierre Briaud, Melody Chan, Morten {\O}ygarden, Dennis Stanton, and Jessica Striker for helpful conversations.}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
