\documentclass[final]{FPSAC2022}
\usepackage{amsfonts, graphics,mathrsfs, mathtools}

\usepackage{tikz}
\usetikzlibrary{matrix, calc, arrows} 
%\usetikzlibrary{arrows}
%\usetikzlibrary{hobby}
\usepackage{hyperref}
\usepackage[all]{xy}
\usepackage{ytableau}
%\usepackage[usenames, dvipsnames]{xcolor}


% use these commands for typesetting doi and arXiv references in the bibliography
%\newcommand{\doi}[1]{\href{https://doi.org/#1}{\texttt{doi:#1}}}
%\newcommand{\arxiv}[1]{\href{https://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

%%\usepackage{ytableau} 


% When you first define a new word, use this macro to make it stand out
% EG We say that an abelian group $I$ is \newword{injective} if, for any
% injection $G \to H$, and any map $G \to I$, there is a map $H \to I$ making the
% obvious diagram commute.
\definecolor{darkblue}{rgb}{0.0,0,0.7}
\newcommand{\darkblue}{\color{darkblue}}
\newcommand{\newword}[1]{\textcolor{darkblue}{\textbf{\emph{#1}}}}
%Arrows 
\newcommand{\into}{\hookrightarrow}
\newcommand{\onto}{\twoheadrightarrow}

%Things LaTeX names by appearance, rather than meaning
% By now, I've learned the standard LaTeX names, but I remember they used to give me trouble, so here are some macros
\newcommand{\isom}{\cong} %The isomorphism symbol
\newcommand{\union}{\cup}
\newcommand{\intersection}{\cap}
\newcommand{\bigunion}{\bigcup}
\newcommand{\bigintersection}{\bigcap}
\newcommand{\disjointunion}{\sqcup}
\newcommand{\bigdisjointunion}{\bigsqcup}

\newcommand{\domzz}
{\raisebox{-0.25\height}{ \begin{tikzpicture}[x=0.75 em,y=0.75 em]
\draw[step=1,gray, thin] (0,0) grid (1,2);
\draw[color=black, thick](0,0)rectangle(1,2);
\draw[thick,rounded corners,color=blue] (0,1.5)--(0.5,1.5)--(0.5,2);
\draw[thick,rounded corners,color=blue] (0,0.5)--(0.5,0.5)--(0.5,1.5)--(1,1.5);
\draw[thick,rounded corners,color=blue] (0.5,0)--(0.5,0.5)--(1,0.5);
\end{tikzpicture}}}

\newcommand{\domzp}
{\raisebox{-0.25\height}{ \begin{tikzpicture}[x=0.75 em,y=0.75 em]
\draw[step=1,gray, thin] (0,0) grid (1,2);
\draw[color=black, thick](0,0)rectangle(1,2);
\draw[thick,rounded corners,color=blue] (0,1.5)--(0.5,1.5)--(0.5,2);
\draw[thick,rounded corners,color=blue] (0,0.5)--(1,0.5);
\draw[thick,rounded corners,color=blue] (0.5,0)--(0.5,1.5)--(1,1.5);
\end{tikzpicture}}}

\newcommand{\dompz}
{\raisebox{-0.25\height}{ \begin{tikzpicture}[x=0.75 em,y=0.75 em]
\draw[step=1,gray, thin] (0,0) grid (1,2);
\draw[color=black, thick](0,0)rectangle(1,2);
\draw[thick,rounded corners,color=blue] (0,1.5)--(1,1.5);
\draw[thick,rounded corners,color=blue] (0,0.5)--(0.5,0.5)--(0.5,2);
\draw[thick,rounded corners,color=blue] (0.5,0)--(0.5,0.5)--(1,0.5);
\end{tikzpicture}}}


\newcommand{\dompp}
{\raisebox{-0.25\height}{ \begin{tikzpicture}[x=0.75 em,y=0.75 em]
\draw[step=1,gray, thin] (0,0) grid (1,2);
\draw[color=black, thick](0,0)rectangle(1,2);
\draw[thick,rounded corners,color=blue] (0,1.5)--(1,1.5);
\draw[thick,rounded corners,color=blue] (0,0.5)--(1,0.5);
\draw[thick,rounded corners,color=blue] (0.5,0)--(0.5,2);
\end{tikzpicture}}}


%Some multiletter functions
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\Ext}{Ext}
\DeclareMathOperator{\End}{End}
\DeclareMathOperator{\Tor}{Tor}
\DeclareMathOperator{\Ker}{Ker}
\DeclareMathOperator{\CoKer}{CoKer}
\DeclareMathOperator{\Spec}{Spec}
\DeclareMathOperator{\MaxSpec}{MaxSpec}
\DeclareMathOperator{\Proj}{Proj}
\DeclareMathOperator{\Frac}{Frac}
\renewcommand{\Im}{\mathop{\mathrm{Im}}}
%Their calligraphic versions; use these for the sheaf constructions
\DeclareMathOperator{\HHom}{\mathcal{H}\emph{om}}
\DeclareMathOperator{\EExt}{\mathcal{E}\emph{xt}}
\DeclareMathOperator{\EEnd}{\mathcal{E}\emph{nd}}
\DeclareMathOperator{\TTor}{\mathcal{T}\emph{or}}
\DeclareMathOperator{\KKer}{\mathcal{K}\emph{er}}
\DeclareMathOperator{\CCoKer}{\mathcal{C}\emph{o}\mathcal{K}\emph{er}}
\newcommand{\IIm}{\mathop{\mathcal{I}\emph{m}}}
\DeclareMathOperator\codim{codim}
\DeclareMathOperator{\vecspan}{span}
\newcommand{\GL}{\mathrm{GL}}
\newcommand{\Flags}{\mathsf{Flags}}
\newcommand{\Gr}{\mathsf{Gr}}
\newcommand{\Sym}{\mathrm{Sym}}
\newcommand{\id}{\mathrm{id}}
\newcommand{\Bubb}{\mathrm{Bubb}}
\newcommand{\rp}{\fbox{+}}
\newcommand{\botp}{P_{\sf bot}}

%This makes alternating tensors look right in displayed equations
\newcommand{\Alt}{\bigwedge\nolimits}


%Blackboard bold letters.
\renewcommand{\AA}{\mathbb{A}}
\newcommand{\BB}{\mathbb{B}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\DD}{\mathbb{D}}
\newcommand{\EE}{\mathbb{E}}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\GG}{\mathbb{G}}
\newcommand{\HH}{\mathbb{H}}
\newcommand{\II}{\mathbb{I}}
\newcommand{\JJ}{\mathbb{J}}
\newcommand{\KK}{\mathbb{K}}
\newcommand{\LL}{\mathbb{L}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\OO}{\mathbb{O}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\renewcommand{\SS}{\mathbb{S}}
\newcommand{\TT}{\mathbb{T}}
\newcommand{\UU}{\mathbb{U}}
\newcommand{\VV}{\mathbb{V}}
\newcommand{\WW}{\mathbb{W}}
\newcommand{\XX}{\mathbb{X}}
\newcommand{\YY}{\mathbb{Y}}
\newcommand{\ZZ}{\mathbb{Z}}

%Calligraphic letters

\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{\bx}{\boldsymbol{x}}
\newcommand{\by}{\boldsymbol{y}}
\newcommand{\bz}{\boldsymbol{z}}

\newcommand{\fm}{\mathfrak{m}}

%\def\leftquot{\delimiter"526E30F\mathopen{}} 

\renewcommand{\sl}{\mathfrak{sl}}
\newcommand{\SL}{\mathrm{SL}}
\newcommand{\fS}{\mathfrak{S}}
\newcommand{\fG}{\mathfrak{G}}
\newcommand{\fR}{\mathfrak{R}}
\newcommand{\fCM}{\mathfrak{CM}}
\newcommand{\Id}{\mathrm{Id}}

\newcommand{\sh}{\alpha} % Have not decided on good notation for this.

\newcommand{\inv}{\mathrm{inv}}
\newcommand{\maj}{\mathrm{maj}}
\newcommand{\raj}{\mathrm{raj}}
\newcommand{\rajc}{\raj{\mathrm{code}}}
\newcommand{\invc}{\inv{\mathrm{code}}}
\newcommand{\majc}{\maj{\mathrm{code}}}

\newcommand{\der}[1]{\tfrac{\ppartial}{\ppartial x_{#1}}}
\newcommand{\diff}{N}

\newcommand{\poly}{\ensuremath{\mathrm{Poly}}}
\newcommand{\W}{W}

\DeclareMathOperator{\im}{\mathrm{im}}

\newcommand{\covered}{\lessdot}
\newcommand{\covers}{\gtrdot}
\newcommand{\word}{{\sf word}}
\newcommand{\greedy}{{\sf greedy}}
\newcommand{\ins}{{\sf insert}}

\newcommand{\splice}{\otimes} %I have no opinion about what symbol to use here. I'm reserving \ast for Demazure product though.
\newcommand{\tpart}{\widetilde{\Pi}}
\newcommand{\ppart}{\Pi}

\newcommand{\pipes}{{\sf Pipes}}
\newcommand{\Rothe}{{\sf RD}}
\newcommand{\wt}{{\tt wt}}
\newcommand{\Mat}{\mathrm{Mat}}

\newcommand{\rN}{\widehat{\partial}} %Feel free to choose a different symbol


%implement theorem enviroments
\newtheorem{Theorem}{Theorem}[section]
\newtheorem{Lemma}[Theorem]{Lemma}
\newtheorem{Corollary}[Theorem]{Corollary}
\newtheorem{cor}[Theorem]{Corollary}
\newtheorem{corollary}[Theorem]{Corollary}
\newtheorem{conj}[Theorem]{Conjecture}
\newtheorem{proposition}[Theorem]{Proposition}
\newtheorem{prop}[Theorem]{Proposition}
\newtheorem{thm}[Theorem]{Theorem}
\newtheorem{theorem}[Theorem]{Theorem}
\newtheorem{prob}[Theorem]{Problem}
\newtheorem{dfn}[Theorem]{Definition}
\newtheorem{lem}[Theorem]{Lemma}
\newtheorem{lemma}[Theorem]{Lemma}
%\newtheorem{ex}[Theorem]{Exercise}
%\newtheorem{eg}[Theorem]{Example}
\newtheorem*{claim}{Claim}

\theoremstyle{definition}
\newtheorem{Definition}[Theorem]{Definition}
\newtheorem{definition}[Theorem]{Definition}

\renewcommand{\bot}{\mathrm{bot}}
\renewcommand{\top}{\mathrm{top}}

\theoremstyle{remark}
\newtheorem{example}[Theorem]{Example}
\newtheorem{Remark}[Theorem]{Remark}
\newtheorem{remark}[Theorem]{Remark}
\newtheorem{rem}[Theorem]{Remark}



\title{Regularity of matrix Schubert varieties}

\author[O.~Pechenik, D.~E~Speyer, and A.~Weigandt]{Oliver Pechenik\thanks{\href{mailto:oliver.pechenik@uwaterloo.ca}{oliver.pechenik@uwaterloo.ca}. Partially supported by a Postdoctoral Fellowship (\#1703696) from the NSF, as well as by a Discovery Grant (RGPIN-2021-02391) and Launch Supplement (DGECR-2021-00010) from NSERC.}\addressmark{1}, David E Speyer\thanks{\href{mailto:speyer@umich.edu}{speyer@umich.edu}. Supported in part by National Science Foundation grants DMS-1600223, DMS-1855135 and DMS-1854225.}\addressmark{2}, \and Anna Weigandt\thanks{\href{mailto:weigandt@mit.edu}{weigandt@mit.edu}. Partially supported by Bill Fulton's Oscar Zariski Distinguished Professor Chair funds.}\addressmark{3}}

\address{\addressmark{1}Dept. of Combinatorics \& Optimization, University of Waterloo, Waterloo ON N2L~3G1, Canada \\ \addressmark{2}Dept. of Mathematics, University of Michigan, Ann Arbor MI 48109, USA \\ \addressmark{3}Dept. of Mathematics, Massachusetts Institute of Technology, Cambridge MA 02139, USA}

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

\begin{document}

\abstract{
    Matrix Schubert varieties are affine varieties arising in the Schubert calculus of the complete flag variety. We give a formula for the Castelnuovo--Mumford regularity of matrix Schubert varieties, answering a question of Jenna Rajchgot. We follow her proposed strategy of studying the highest-degree homogeneous parts of Grothendieck polynomials, which we call Castelnuovo--Mumford polynomials. In addition to the regularity formula, we obtain formulas for the degrees of all Castelnuovo--Mumford polynomials and for their leading terms, as well as a complete description of when two Castelnuovo--Mumford polynomials agree up to scalar multiple. 
    The degree of the Grothendieck polynomial is a new permutation statistic, which we call the Rajchgot index; we develop the properties of Rajchgot index and relate it to major index and to weak order.
}

\maketitle

\section{Introduction}

The \emph{flag variety} $\Flags_n$, the parameter space for complete flags of nested vector subspaces of $\CC^n$, has a complex cell decomposition given by its \emph{Schubert varieties}. The geometry and combinatorics of this cell decomposition are of central importance in Schubert calculus. 
%Intersecting Schubert varieties of $\Flags_{2n}$ with an affine patch yields a family of affine generalized determinantal varieties $X_w$, called \emph{matrix Schubert varieties} 
These Schubert varieties are closely related to certain generalized determinantal varieties $X_w$ of $n \times n$ matrices called  \emph{matrix Schubert varieties} (see~\cite{Fulton} and Section~\ref{sec:background} for the definition).
 It is natural to desire a measure of the algebraic complexity of matrix Schubert varieties. One such measure is the \emph{Castelnuovo--Mumford regularity} of $X_w$, a commutative-algebraic invariant determining the extent to which the defining ideal of $X_w$ can be resolved by low-degree polynomials.


Jenna Rajchgot (\textit{cf.}\ \cite{RRRSW}) observed that, since matrix Schubert varieties are Cohen--Macaulay, the regularity of $X_w$ is given by the difference between the highest-degree and lowest-degree homogeneous parts of the \emph{$K$-polynomial} for $X_w$. These particular $K$-polynomials have been much studied. They were introduced by Lascoux and Sch\"utzenberger \cite{Lascoux.Schutzenberger}, under the name of \emph{Grothendieck polynomials} $\fG_w(\bx)$, as polynomial representatives for structure sheaf classes in $K$-theoretic Schubert calculus of $\Flags_n$. Grothendieck polynomials are inhomogeneous polynomials $\fG_w(\bx)$ in $n$ variables $\bx = x_1, x_2, \ldots, x_n$, indexed by permutations $w$ in the symmetric group $S_n$. 

The lowest-degree homogeneous part of $\fG_w(\bx)$ is the \emph{Schubert polynomial} $\fS_w(\bx)$ \cite{Lascoux.Schutzenberger:Schubert}; Schubert polynomials are well-understood from a combinatorial perspective, and the degree of $\fS_w(\bx)$ equals the codimension of $X_w$ or equivalently the Coxeter length $\inv(w)$ of the permutation $w$. Hence, determining the regularity of $X_w$ reduces to answering the following question of Rajchgot:
``What is the degree of a Grothendieck polynomial?'' 

We term the top-degree part of $(-1)^{\deg \fG_w(\bx) - \inv(w)} \fG_w(\bx)$ the \newword{Castelnuovo--Mumford polynomial} and write it $\fCM_w(\bx)$.
(The power of $-1$ makes the coefficients positive.)
 The goal of this paper is to answer Rajchgot's question by understanding these homogeneous polynomials and in particular their degrees, thereby obtaining a formula for the Castelnuovo--Mumford regularity of $X_w$. In the special case of \emph{symmetric} Grothendieck polynomials, \cite{RRRSW} gives a formula for the degree of $\fCM_w(\bx)$. 
 Our first main result is a degree formula for arbitrary $\fCM_w(\bx)$, answering Rajchgot's question in full generality.
Since our work appeared as a preprint, additional formulas have been given for the case of \emph{vexillary} permutations $w$ in \cite{Hafner,Rajchgot.Robichaux.Weigandt}.

Write a permutation $w \in S_n$ in one-line notation as $w(1) w(2) \cdots w(n)$. For each $k$, find an increasing subsequence of $w(k) w(k+1) \cdots w(n)$ containing $w(k)$ and of greatest length among such subsequences. Let $r_k$ be the number of terms from $w(k) w(k+1) \cdots w(n)$ omitted from this subsequence. \hspace{-.25pt}We call the sequence $(r_1, \dots, r_n) \hspace{-.25pt}=\hspace{-.25pt} \rajc(w)$ the \newword{Rajchgot code} of $w$ and its sum $\raj(w)$ the \newword{Rajchgot index} of $w$.

\begin{Theorem}\label{thm:degree}
For $w \in S_n$, we have $\deg \fCM_w(\bx) = \raj(w)$. Moreover, for any term order satisfying $x_1 < x_2 < \cdots < x_n$, the leading term of $\fCM_w(\bx)$ is a scalar  multiple of the monomial $\bx^{\rajc(w)} =  x_1^{r_1} x_2^{r_2} \cdots x_n^{r_n}$.  
In particular, the Castelnuovo--Mumford regularity of the matrix Schubert variety $X_w$ is $\raj(w) - \inv(w)$.
\end{Theorem}

\begin{example}\label{ex:main}
Consider $w = 293417568 \in S_9$. A longest increasing subsequence starting from $2$ is $2\bullet 34\bullet\bullet568$, which omits three terms, so $r_1 = 3$. In full,  \[\rajc(w) = (r_1, r_2, \ldots, r_9) = (3,7,2,2,1,2,0,0,0).\] 
Hence, by Theorem~\ref{thm:degree}, the leading term of $\fCM_{w}(\bx)$ is a scalar multiple of the monomial $x_1^3 x_2^7 x_3^2 x_4^2 x_5 x_6^2$ and the degree of $\fCM_{w}(\bx)$ is $\raj(w) = 3+7+2+2+1+2+0+0+0 = 17$. Since $\inv(w) = 12$, it follows that the Castelnuovo--Mumford regularity of the matrix Schubert variety $X_{w}$ is $\raj(w) - \inv(w) = 17-12 = 5$.
\end{example}

Our remaining results explore the combinatorics of Castelnuovo--Mumford polynomials and the associated permutation statistics.

 While Schubert polynomials are all distinct and have distinct leading monomials, we observe that many Castelnuovo--Mumford polynomials differ only by a scalar multiple. In fact, we will show that $\fCM_u(\bx)$ and $\fCM_v(\bx)$ differ by a scalar precisely if $\rajc(u) = \rajc(v)$. This phenomenon is best understood in the context of \emph{double} Castelnuovo--Mumford polynomials, as we now explain.
The \emph{double Grothendieck polynomials} are certain polynomials $\fG_w(x_1,\ldots, x_n; y_1, \ldots, y_n)$ in $2n$ variables, also indexed by $w \in S_n$. They represent Schubert classes in the torus-equivariant $K$-theory of $\Flags_n$, and obey the relations $\fG_w(\bx; 0) = \fG_w(\bx)$ and $\fG_w(\bx;\by) = \fG_{w^{-1}}(\by; \bx)$. 
%We recall the definition in Section~\ref{GrothBackground}. 
We define the \newword{double Castelnuovo--Mumford polynomial} $\fCM_w(\bx;  \by)$ to be the highest-degree part of $\fG_w(\bx; \by)$.
We will show (Corollary~\ref{cor:high_degree_xy}) that $\fG_w(\bx; \by)$ has terms whose $\bx$-degree and $\by$-degree are simultaneously maximal, so $\fCM_w(\bx; \by)$ is homogeneous in both $\bx$ and $\by$.


We find that double Castelnuovo--Mumford polynomials factor as a polynomial in $\bx$ times a polynomial in $\by$. We identify a special family of single Castelnuovo--Mumford polynomials, the \newword{Rajchgot polynomials} $\fR_{\pi}(\bx)$, indexed by set partitions of $\{1, \dots, n\}$. For each $w \in S_n$, we associate a set partition $\pi(w)$ so that the following holds.

\begin{Theorem} \label{thm:main}
Double Castelnuovo--Mumford polynomials factor into Rajchgot polynomials as \[\fCM_{w}(\bx;  \by) = \fR_{\pi(w)}(\bx) \fR_{\pi(w^{-1})}(\by).\] 
For any term order satisfying 
$x_1 < \cdots < x_n$ and $y_1 < \cdots < y_n,$ the leading term of $\fCM_w(\bx;\by)$ is exactly $\bx^{\rajc(w)} \by^{\rajc(w^{-1})}$. 
In particular, $\fCM_w(\bx) = \fR_{\pi(w^{-1})}(1, \dots, 1) \fR_{\pi(w)}(\bx)$ has leading term $\fR_{\pi(w^{-1})}(1, \dots, 1) \bx^{\rajc(w)}$.
\end{Theorem}


In particular, Theorem~\ref{thm:main} shows that, up to scalar multiple, the number of distinct Castelnuovo--Mumford polynomials for $w \in S_n$ is not $n!$, but rather the number of set partitions of $n$, which is also known as the  $n$th \emph{Bell number}. 

 The Rajchgot index is related to the classical \emph{major index} statistic. 
 
 \begin{theorem}\label{thm:main_mm}
 	For all $w \in S_n$, we have 
 	\[
 	\raj(w) = \max \{\maj(v) : v \leq_R w \} = \max \{\maj(u^{-1}) : u \leq_L w \} = \deg \fCM_w(\bx),
 	\]
 	 where $\leq_L$ and $\leq_R$ denote the left and right weak orders, respectively.  
 	 \end{theorem}	
 	 
 	 To the best of our knowledge, none of the equalities in Theorem~\ref{thm:main_mm} has been observed previously.
This paper is an extended abstract of \cite{Pechenik.Speyer.Weigandt}, which contains complete proofs.
 
\section{Background}
\label{sec:background}

Let $[n] \coloneqq \{1, 2, \dots, n\}$.
Let $S_n$ denote the symmetric group of permutations of $[n]$. We consider $w \in S_n$ as a map $w \colon [n] \to [n]$ and write $w$ in \newword{one-line notation} as the string $w(1) w(2) \cdots w(n)$. We will often write $w_i \coloneqq w(i)$.  We identify $w \in S_n$ with the permutation matrix having a $1$ in each position $(i, w_i)$ and $0$s elsewhere. We write $\id$ for the identity permutation $12 \cdots n$ and $w_0$ for the reverse permutation $n(n-1) \cdots 1$.


Let $s_i \coloneqq (i \; i+1)$ denote the simple transposition that exchanges $i$ and $i+1$, and recall that $s_1, \dots, s_{n-1} $ generate $S_n$. 
An \newword{inversion} of $w \in S_n$ is a pair $i,j \in [n]$ such that $i<j$ and $w_i > w_j$. We write $\inv(w)$ for the number of inversions in $w$ and call it the \newword{Coxeter length} of $w$. Note $\inv(w)$ is the length of the shortest expression for $w$ as a product of the $s_i$. A factorization $w = s_{i_1} \cdots s_{i_{\inv(w)}}$ is called a \newword{reduced expression} for $w$, and the sequence of subscripts $i_1 \cdots i_{\inv(w)}$ is called a \newword{reduced word} for $w$. 

We need three partial orders on $S_n$. If $w = uv$ with $\inv(w) = \inv(u) + \inv(v)$, then we say $v \leq_L w$ and $u \leq_R w$; the relations $\leq_L$ and $\leq_R$ are known as \newword{left} and \newword{right weak order}, respectively. We write $\leq_{LR}$ for the partial order obtained as the transitive closure of the union of left and right weak orders and call it \newword{two-sided weak order}. For $u \leq_R v$, we write $[u,v]_R$ for the interval from $u$ to $v$ in right weak order. Similarly, we define the notations $[u,v]_L$ and $[u,v]_{LR}$. 
A \newword{descent} of $w \in S_n$ is a value $i$ such that $w_i > w_{i+1}$. 

The \newword{$0$-Hecke monoid} $\mathcal{H}_n$ is the free monoid on generators $\tau_1, \dots, \tau_{n-1}$ subject to the ``idempotent braid relations''
$
\tau_i^2 = \tau_i,$ $\tau_i \tau_j = \tau_j \tau_i,$ for $j \neq i \pm 1$, and  $\tau_i  \tau_{i+1}  \tau_i =  \tau_{i+1}  \tau_i  \tau_{i+1}.
$
There is a natural action of $\mathcal{H}_n$ on $S_n$ induced by
\[
\tau_i \ast w \coloneqq \begin{cases}
	s_i w, & \text{if} \; \inv(s_i w) > \inv(w);  \\
	w, & \text{otherwise.}
\end{cases}
\]
%If $d$ is a word in $\{1, \dots, n-1\}$, we define the \newword{Demazure product} of $d$ to be the permutation
%\[
%\tau_{d_1} \ast (\tau_{d_2} \ast ( \dots \ast \id)) \cdots ) \in S_n.
%\]
%In particular, if $d$ is a reduced word for the permutation $w$, then the Demazure product of $d$ is $w$.
For each $w\in S_n$, there is a unique element $\overline{w}$ in $\mathcal{H}_n$ with $\overline{w} \ast \id = w$. 
We define the \newword{Demazure product} on $S_n$ to be the binary operation $u \ast v$ given by $u \ast v = \overline{u} \ast \overline{v} \ast \id$. 

The \newword{graph} of $w \in S_n$ is obtained by plotting bullets $\bullet$ in the $n\times n$ grid in positions $(i,w_i)$ for $i\in [n]$ (in matrix coordinates).  
The \newword{Rothe diagram} $\Rothe(w)$ is constructed from its graph as follows. From each $\bullet$, fire a laser  directly to the right and another straight down. The cells of the $n \times n$ grid that are hit by no laser are the Rothe diagram $\Rothe(w)$. The number of cells in $\Rothe(w)$ is $\inv(w)$. Write $\ell_i$ for the number of cells in row $i$. We call the sequence $\invc(w) \coloneqq (\ell_1, \dots, \ell_n)$ the \newword{inv code} of $w$. 

 
The \newword{matrix Schubert variety} $X_w$ is an affine variety cut out by certain determinants.  
Let $Z = (z_{ij})_{1 \leq i,j \leq n}$ be a matrix of distinct indeterminates. Then $X_w$ is a subvariety of the $n^2$-dimensional affine space $\Spec \mathbb{C}[Z]$. 
Consider the Rothe diagram $\Rothe(w)$. For each cell $(i,j)$ of $\Rothe(w)$, let $r_{i,j}$ be the number of $1$s appearing in the permutation matrix $w$ northwest of the cell $(i,j)$. 
Let $I_w$ be the ideal generated by, for each such $(i,j)$, the $(r_{i,j} + 1) \times (r_{i,j} + 1)$ minors of the matrix northwest of $(i,j)$. 
The matrix Schubert variety $X_w$ is the subvariety of $n \times n$ matrices defined by the ideal $I_w$. By work of Fulton \cite{Fulton}, the ideal $I$ is prime, so $X_w$ is a reduced and irreducible affine variety; a $n \times n$ matrix $A$ lies in $X_w$ if the rank of each northwest submatrix of $A$ is less than or equal to the rank of the same submatrix of $w$.

Let $R \coloneqq \mathbb{C}[Z]$ be a polynomial ring and let $I \subseteq R$ be a homogeneous ideal. We write $R(-i)$ for $R$ with all degrees shifted by $i$. A \newword{free resolution} of $R/I$ is a diagram of graded $R$-modules
$
0 \to \bigoplus_{i \in \mathbb{Z}} R(-i)^{b^k_i} \to \dots \to \bigoplus_{i \in \mathbb{Z}} R(-i)^{b^0_i} \to R/I \to 0
$ that is \newword{exact}, that is, such that the image of each map is the kernel of the next. There always exists such a free resolution with $k \leq n^2$. Up to isomorphism there is a unique free resolution simultaneously minimizing all $b_i^j$, the \newword{minimal free resolution} of $R/I$. In this case, the $b_i^j$ are invariants of $R/I$. The \newword{Castelnuovo--Mumford regularity} ${\rm reg}(R/I)$ of $R/I$ is the greatest $i - j$ such that $b_i^j \neq 0$. Conflating affine varieties with their coordinate rings, we also refer to this number as the Castelnuovo--Mumford regularity of $\Spec R/I$. When $R/I$ is Cohen--Macaulay, the projective dimension of $R/I$ equals the height of the ideal $I$ as well as the codimension of $\Spec R/I$ in $\Spec R$. 


Write $(R/I)_a$ for the degree $a$ piece of $R/I$.  The \newword{Hilbert series} of $R/I$ is the formal power series $H(R/I;t)=\sum_{a\in \mathbb N} \dim_{\mathbb C}(R/I)_a t^a.$
If we write the Hilbert series as \[H(R/I;t)=\frac{K(R/I;t)}{(1-t)^{n^2}}\] the numerator $K(R/I;t)$ is the \newword{K-polynomial} of $R/I$.
The \newword{height} ${\rm ht}(I)$ of a prime ideal $I$ is the maximum $k$ so that there is a nested chain of prime ideals $I_0\subsetneq I_1\subsetneq \cdots \subsetneq I_k=I.$ If $I$ is prime, ${\rm ht}(I)$ is the codimension of $\Spec R/I$ in $\Spec R$.

\begin{lemma}\label{lem:Benedetti}
Suppose $R/I$ is Cohen--Macaulay.  Then ${\rm reg}(R/I)= \deg(K(R/I;t))-{\rm ht}(I)$.
\end{lemma}

Matrix Schubert varieties are Cohen--Macaulay \cite{Fulton} and the codimension of $X_w$ is the inversion statistic $\inv(w)$. Hence, computing the regularity of matrix Schubert varieties amounts to finding the degree of their K-polynomials.

We recall an explicit combinatorial formula for (double) Schubert polynomials and (double) Grothendieck polynomials.  A \newword{pipe dream} is a subset $P$ of the cells in the strictly upper left triangular part of the $n\times n$ grid, \textit{i.e.}, $P\subseteq \{(i,j):1<i+j\leq n\}.$  We represent this subset pictorially by placing a \newword{crossing tile} \begin{tikzpicture}[x=1em,y=1em]
	\draw[color=black, thick](0,1)rectangle(1,2);
	\draw[thick,rounded corners, color=darkblue] (0,1.5)--(1,1.5);
	\draw[thick,rounded corners,color=darkblue] (.5,1)--(.5,2);
	\end{tikzpicture}
in each cell of $P$ and \newword{bumping tiles}
\begin{tikzpicture}[x=1em,y=1em]
	\draw[color=black, thick](0,1)rectangle(1,2);
	\draw[thick,rounded corners,color=darkblue] (.5,1)--(.5,1.5)--(1,1.5);
	\draw[thick,rounded corners,color=darkblue] (.5,2)--(.5,1.5)--(0,1.5);
	\end{tikzpicture}
 in the other cells.
If there is a crossing tile in cell $(i,j)$, we associate to it the simple transposition $s_{i+j-1}$.  
We then associate a reading word $\word(P)$ to $P$ by reading these simple transpositions within rows from right to left, working from the top row downwards.  We say $P$ is a pipe dream for $w$ if $w$ is the Demazure product of $\word(P)$.
Write $\pipes(w)$ for the set of pipe dreams for $w$. We say $P \in \pipes(w)$ is \newword{reduced} if $\word(P)$ is a reduced word for $w$ and write $\pipes_0(w)$ for the subset of reduced pipe dreams.

\begin{definition}\label{thm:pipedreams}
For any $w \in S_n$, we have
\[ \fG_w(\bx;\by)=\sum_{P\in \pipes(w)}(-1)^{|P|-\inv(w)} \prod_{(i,j)\in P} (x_i+y_j-x_iy_j).\]
\end{definition}

Below are the reduced (blue) and nonreduced (red) pipe dreams for $w=42153$.
\[\begin{tikzpicture}[x=0.8em,y=0.8em]
\draw[step=1,gray, thin] (0,0) grid (5,5);
\draw[color=black, thick](0,0)rectangle(5,5);
\draw[thick,rounded corners,color=blue](0,4.5)--(3.5,4.5)--(3.5,5);
\draw[thick,rounded corners,color=blue] (0,3.5)--(1.5,3.5)--(1.5,5);
\draw[thick,rounded corners,color=blue] (0,2.5)--(.5,2.5)--(.5,5);
\draw[thick,rounded corners,color=blue] (0,1.5)--(1.5,1.5)--(1.5,2.5)--(2.5,2.5)--(2.5,3.5)--(3.5,3.5)--(3.5,4.5)--(4.5,4.5)--(4.5,5);
\draw[thick,rounded corners,color=blue] (0,.5)--(.5,.5)--(.5,2.5)--(1.5,2.5)--(1.5,3.5)--(2.5,3.5)--(2.5,5);
\end{tikzpicture}\quad
\begin{tikzpicture}[x=0.8em,y=0.8em]
\draw[step=1,gray, thin] (0,0) grid (5,5);
\draw[color=black, thick](0,0)rectangle(5,5);
\draw[thick,rounded corners,color=blue](0,4.5)--(3.5,4.5)--(3.5,5);
\draw[thick,rounded corners,color=blue] (0,3.5)--(1.5,3.5)--(1.5,5);
\draw[thick,rounded corners,color=blue] (0,2.5)--(.5,2.5)--(.5,5);
\draw[thick,rounded corners,color=blue] (0,1.5)--(.5,1.5)--(.5,2.5)--(2.5,2.5)--(2.5,3.5)--(3.5,3.5)--(3.5,4.5)--(4.5,4.5)--(4.5,5);
\draw[thick,rounded corners,color=blue] (0,.5)--(.5,.5)--(.5,1.5)--(1.5,1.5)--(1.5,3.5)--(2.5,3.5)--(2.5,5);
\end{tikzpicture}\quad
\begin{tikzpicture}[x=0.8em,y=0.8em]
\draw[step=1,gray, thin] (0,0) grid (5,5);
\draw[color=black, thick](0,0)rectangle(5,5);
\draw[thick,rounded corners,color=blue](0,4.5)--(3.5,4.5)--(3.5,5);
\draw[thick,rounded corners,color=blue] (0,3.5)--(1.5,3.5)--(1.5,5);
\draw[thick,rounded corners,color=blue] (0,2.5)--(.5,2.5)--(.5,5);
\draw[thick,rounded corners,color=blue] (0,1.5)--(.5,1.5)--(.5,2.5)--(1.5,2.5)--(1.5,3.5)--(3.5,3.5)--(3.5,4.5)--(4.5,4.5)--(4.5,5);
\draw[thick,rounded corners,color=blue] (0,.5)--(.5,.5)--(.5,1.5)--(1.5,1.5)--(1.5,2.5)--(2.5,2.5)--(2.5,5);
\end{tikzpicture}
\quad \quad %%%%%%
\begin{tikzpicture}[x=0.8em,y=0.8em]
\draw[step=1,gray, thin] (0,0) grid (5,5);
\draw[color=black, thick](0,0)rectangle(5,5);
\draw[thick,rounded corners,color=red](0,4.5)--(3.5,4.5)--(3.5,5);
\draw[thick,rounded corners,color=red] (0,3.5)--(1.5,3.5)--(1.5,5);
\draw[thick,rounded corners,color=red] (0,2.5)--(.5,2.5)--(.5,5);
\draw[thick,rounded corners,color=red] (0,1.5)--(1.5,1.5)--(1.5,3.5)--(2.5,3.5)--(2.5,3.5)--(2.5,5);
\draw[thick,rounded corners,color=red] (0,.5)--(.5,.5)--(.5,2.5)--(2.5,2.5)--(2.5,3.5)--(3.5,3.5)--(3.5,4.5)--(4.5,4.5)--(4.5,5);
\end{tikzpicture}\quad
\begin{tikzpicture}[x=0.8em,y=0.8em]
\draw[step=1,gray, thin] (0,0) grid (5,5);
\draw[color=black, thick](0,0)rectangle(5,5);
\draw[thick,rounded corners,color=red](0,4.5)--(3.5,4.5)--(3.5,5);
\draw[thick,rounded corners,color=red] (0,3.5)--(1.5,3.5)--(1.5,5);
\draw[thick,rounded corners,color=red] (0,2.5)--(.5,2.5)--(.5,5);
\draw[thick,rounded corners,color=red] (0,1.5)--(1.5,1.5)--(1.5,2.5)--(2.5,2.5)--(2.5,3.5)--(2.5,5);
\draw[thick,rounded corners,color=red] (0,.5)--(.5,.5)--(.5,2.5)--(1.5,2.5)--(1.5,3.5)--(3.5,3.5)--(3.5,4.5)--(4.5,4.5)--(4.5,5);
\end{tikzpicture}\quad
\begin{tikzpicture}[x=0.8em,y=0.8em]
\draw[step=1,gray, thin] (0,0) grid (5,5);
\draw[color=black, thick](0,0)rectangle(5,5);
\draw[thick,rounded corners,color=red](0,4.5)--(3.5,4.5)--(3.5,5);
\draw[thick,rounded corners,color=red] (0,3.5)--(1.5,3.5)--(1.5,5);
\draw[thick,rounded corners,color=red] (0,2.5)--(.5,2.5)--(.5,5);
\draw[thick,rounded corners,color=red] (0,1.5)--(.5,1.5)--(.5,2.5)--(2.5,2.5)--(2.5,3.5)--(2.5,5);
\draw[thick,rounded corners,color=red] (0,.5)--(.5,.5)--(.5,1.5)--(1.5,1.5)--(1.5,3.5)--(3.5,3.5)--(3.5,4.5)--(4.5,4.5)--(4.5,5);
\end{tikzpicture}\quad
\begin{tikzpicture}[x=0.8em,y=0.8em]
\draw[step=1,gray, thin] (0,0) grid (5,5);
\draw[color=black, thick](0,0)rectangle(5,5);
\draw[thick,rounded corners,color=red](0,4.5)--(3.5,4.5)--(3.5,5);
\draw[thick,rounded corners,color=red] (0,3.5)--(1.5,3.5)--(1.5,5);
\draw[thick,rounded corners,color=red] (0,2.5)--(.5,2.5)--(.5,5);
\draw[thick,rounded corners,color=red] (0,1.5)--(1.5,1.5)--(1.5,3.5)--(2.5,3.5)--(3.5,3.5)--(3.5,4.5)--(4.5,4.5)--(4.5,5);
\draw[thick,rounded corners,color=red] (0,.5)--(.5,.5)--(.5,2.5)--(2.5,2.5)--(2.5,3.5)--(2.5,5);
\end{tikzpicture}
\]


We obtain the \newword{(single) Grothendieck polynomials} by specializing $\by$ to 0, that is to say, \ $\fG_w(\bx) \coloneqq \fG_w(\bx;\mathbf 0).$
The \newword{double Schubert polynomial} $\fS_w(\bx, \by)$ is the lowest-degree homogeneous part of the double Grothendieck polynomial $\fG_w(\bx, \by)$ substituting $y_j \mapsto -y_j$, while the \newword{(single) Schubert polynomial} $\fS_w(\bx)$ is the lowest-degree homogeneous part of $\fG_w(\bx)$. 
The degree of the Schubert polynomial $\fS_w(\bx)$ is $\inv(w)$.

\begin{lemma}\label{cor:high_degree_xy}
Let $w$ be a permutation and let $d$ be the degree of $\fG_w(\bx)$. Then $\fG_w(\bx; \by)$ has terms which are of bidegree $(d,d)$ in the $\bx$ and $\by$ variables, and no term in $\fG_w(\bx; \by)$ has $\bx$-degree or $\by$-degree higher than $d$. 
\end{lemma}

Define the  \newword{Castlenuovo--Mumford polynomial} $\fCM(\bx)$ to be $(-1)^{\deg \fG_w(\bx) - \inv(w)}$ times the highest degree part of $\fG_w(\bx)$ and define the \newword{double Castlenuovo--Mumford polynomial}, $\fCM_w(\bx; \by)$, to be $(-1)^{\inv(w)}$ times the highest degree part of $\fG_w(\bx; \by)$. 
These sign factors make $\fCM_w(\bx; \by)$ and $\fCM_w(\bx)$ have positive coefficients.
So the degree of $\fCM_w(\bx)$, and the bidegree of $\fCM_w(\bx; \by)$, are both given by the maximal number of crosses in any pipe dream for $w$.

If we specialize the single Grothendieck polynomial $\fG_w(\bx)$ by setting $x_i \mapsto 1-t$, we obtain the K-polynomial of the matrix Schubert variety $X_w$ \cite{Knutson.Miller}. Note that this specialization does not affect the degrees of the polynomials, since all top-degree terms of $\fG_w(\bx)$ have the same sign. Moreover, $\deg \fS_w(\bx) = \codim X_w = \inv(w)$ \cite{Fulton}. Thus, we can rewrite Lemma~\ref{lem:Benedetti} as follows.

\begin{corollary}\label{cor:reg}
	Let $X_w$ be a matrix Schubert variety. Then ${\rm reg} \; X_w = \deg \fG_w(\bx) - \inv(w)$.
\end{corollary} 

\section{Simple properties of Rajchgot index}
\label{sec:rajchgot}

\begin{lemma}\label{lem:rajinv_inequality}
	Let $w$ be a permutation and let $(\ell_1(w), \ell_2(w), \ldots, \ell_n(w))$ be its inversion code. Then $r_i(w) \geq \ell_i(w)$ with equality if and only if $w$ has no $132$ pattern starting at position $i$. Hence, $\raj(w) \geq \inv(w)$, with equality if and only if $w$ avoids the pattern $132$, \textit{i.e.}\ if and only if $w$ is dominant.
\end{lemma}


Say $w \in S_n$ is \newword{fireworks} if the initial elements of its decreasing runs are in increasing order.  Say $w$ is \newword{inverse fireworks} if $w^{-1}$ is fireworks.
For example,
	the permutation $41|62|853|97$ is fireworks because $4 < 6 < 8 < 9$.

Let $w \in S_n$ and let $m_i(w)$ equal the number of $j \geq i$ such that $w_j > w_{j+1}$.  The \newword{major index} of $w$ is $
\maj(w) = \sum_{i=1}^n m_i(w).
$
Theorem~\ref{thm:raj=mm} will establish a formula for $\raj$ as a maximum of many values of $\maj$. At the moment, we have an inequality:


\begin{lemma}\label{lem:rajmaj_inequality}
	Let $w$ be a permutation and let $m_i(w)$ equal the number of $j \geq i$ such that $w_j > w_{j+1}$. 
	Then $r_i(w) \geq m_i(w)$. Hence,  $\raj(w) \geq \maj(w)$, with equality if and only if $w$ is fireworks.
\end{lemma}

A \newword{set partition} of $[n]$ is a collection $\pi$ of pairwise-disjoint nonempty subsets of $[n]$ with union $[n]$; the subsets are called the \newword{blocks} of $\pi$. We order the blocks of $\pi$ by  their largest elements and index them as $(\pi_t, \pi_{t+1}, \ldots, \pi_n)$, where $\max(\pi_t) < \max(\pi_{t+1}) < \cdots < \max(\pi_n)$. 
For brevity, we omit commas and braces from our notation, for example, writing $( 1,\ 3,\ 45,\ 67,\ 8,\ 29 )$ rather than $\{ \{ 1 \},\ \{ 3 \},\ \{ 4,\ 5 \},\ \{ 6,\ 7 \},\ \{ 8 \},\ \{ 2,9 \} \}$.

\begin{proposition}\label{prop:bell}
	Fireworks permutations are enumerated by the Bell numbers.
\end{proposition}


For example, the fireworks permutation $416285397$ corresponds to $(14,26,358,79)$.



A permutation $w$ is \newword{valley} if there is some index $a$ with $w(1) > w(2) > \cdots > w(a) < w(a+1) < \cdots < w(n)$. 
There are $2^{n-1}$ valley permutations in $S_n$, because a valley permutation is uniquely determined by the subset $\{ w(1), w(2),\ldots, w(a-1) \}$ of $\{ 2,3,\ldots, n \}$. 
A permutation $w$ is \newword{inverse valley} if $w^{-1}$ is valley.

\begin{lemma} \label{lem:dominant_and_fireworks_is_inverse_valley}
A permutation $w$ is a valley permutation if and only if $w$ is both dominant and inverse fireworks; $w$ is inverse valley if and only if $w$ is both dominant and fireworks.
\end{lemma}



\section{Main results} \label{sec:fireworks}

We give a pictorial description of Rajchgot code. 
Draw the graph of $w$.  
Now, draw a lasso around the set of dots that are maximally southeast in the grid.  Call this set of dots $B_n(w)$. Then draw another lasso around the dots that are maximally southeast among dots that are not lassoed.  This next set of dots is $B_{n-1}(w)$, \textit{etc.} We call this the \newword{blob diagram} of $w$ (see example below). \vspace{-2mm}
\[
\begin{tikzpicture}[x=1.3em,y=1.3em]
\draw[step=1,gray, thin] (0,0) grid (9,9);
\draw[color=white, thick](0,0)rectangle(9,10);
\draw[color=black, thick](0,0)rectangle(9,9);
\node at (3.5,8.5) {$\bullet$};
\node at (5.5,7.5) {$\bullet$};
\node at (1.5,6.5) {$\bullet$};
\node at (2.5,5.5) {$\bullet$};
\node at (4.5,4.5) {$\bullet$};
\node at (6.5,3.5) {$\bullet$};
\node at (8.5,2.5) {$\bullet$};
\node at (0.5,1.5) {$\bullet$};
\node at (7.5,0.5) {$\bullet$};
\node at (-0.5,8.5) {$1$};
\node at (-0.5,7.5) {$2$};
\node at (-0.5,6.5) {$3$};
\node at (-0.5,5.5) {$4$};
\node at (-0.5,4.5) {$5$};
\node at (-0.5,3.5) {$6$};
\node at (-0.5,2.5) {$7$};
\node at (-0.5,1.5) {$8$};
\node at (-0.5,0.5) {$9$};
\node at (0.5,9.5) {$1$};
\node at (1.5,9.5) {$2$};
\node at (2.5,9.5) {$3$};
\node at (3.5,9.5) {$4$};
\node at (4.5,9.5) {$5$};
\node at (5.5,9.5) {$6$};
\node at (6.5,9.5) {$7$};
\node at (7.5,9.5) {$8$};
\node at (8.5,9.5) {$9$};
\node at (8.0,1.5) {$B_9$};
\node at (3.5,2.5) {$B_8$};
\node at (5.0,6.0) {$B_7$};
\node at (3.0,7.0) {$B_6$};
\node at (1.0,6.5) {\small $B_5$};
\draw[blue,thick, rotate around={-30:(1,6.5)}] (1,6.5) ellipse (.75 and .75);
\draw[blue,thick, rotate around={-20:(3,7)}] (3,7) ellipse (.75 and 2);
\draw[blue,thick, rotate around={-20:(5,6)}] (5,6) ellipse (.75 and 2);
\draw[blue,thick, rotate around={-70:(3.5,2.5)}] (3.5,2.5) ellipse (.75 and 3.5);
\draw[blue,thick, rotate around={-30:(8,1.5)}] (8,1.5) ellipse (.7 and 1.5);
\end{tikzpicture}
\]	


\begin{lemma}\label{lem:blob_LIS}
Let $(i,w_i)$ be in blob $B_k$. Then the longest increasing subsequence starting at $(i,w_i)$ contains $n+1-k$ elements.
\end{lemma}

\begin{cor} \label{cor:raj_code_from_blobs}
Let $(r_1(w), r_2(w), \ldots, r_n(w))$ be the Rajchgot code of $w$, and let $(i, w_i)$ be in blob $B_k$. Then $r_i(w) = k - i$.
\end{cor}

Define $\pi_k(w)$ to be the set of column labels of the dots in $B_k(w)$.  (By symmetry, $\pi_k(w^{-1})$ is the row labels of the dots in $B_k(w)$.) Then $\pi(w)$ is the set partition of $w$. Note that $i$ and $j$ are in the same block of the set partition exactly if $(w^{-1}(i), i)$ and $(w^{-1}(j), j)$ are in the same blob.
In our example, $\pi(w)$ is the set partition $\{ 2,\ 34,\ 56,\ 17,\ 89 \}$. 
(We obtain $\pi(w^{-1})$ by recording the row labels of the entries in each blob.)
The ordering of the blocks of $\pi(w)$ is recoverable from $\pi(w)$, since the maximum elements of the blocks occur in increasing order.
Index the blocks of $\pi(w)$ as $(\pi_t, \pi_{t+1}, \ldots, \pi_n)$, so that $\pi_k$ corresponds to block $B_k$, and set $\alpha_k(w) = \# \pi_k(w)$. 
Define the composition $(\alpha_t(w), \alpha_{t+1}(w), \ldots, \alpha_n(w))$ to be the \newword{shape} of $w$. 
We can express Rajchgot index in terms of shape.

\begin{lemma}\label{lem:set_partition_to_raj}
For $w\in S_n$, we have 
\[ \raj(w)=\sum_{k=1}^n k\alpha_k - \binom{n+1}{2} = \sum_{k=1}^n (\alpha_k + \alpha_{k+1} + \cdots + \alpha_n) - \binom{n+1}{2} . \]
\end{lemma}

\begin{cor}
We have $\raj(w) = \raj(w^{-1})$. 
\end{cor}

For compositions $(\alpha_j, \alpha_{j+1}, \ldots, \alpha_n)$ and $(\beta_k, \beta_{k+1}, \ldots, \beta_n)$ of $n$,  say  $\alpha$ \newword{dominates} $\beta$ ($\alpha \succeq \beta$) if $\alpha_m + \alpha_{m+1} + \cdots + \alpha_n \geq \beta_m + \beta_{m+1} + \cdots + \beta_n$ for all $m$. We write $\alpha \succ \beta$ to mean $\alpha \succeq \beta$ and $\alpha \neq \beta$.

\begin{cor} \label{cor:dominates_raj}
Let $u$ and $v$ be permutations of shapes $\alpha$ and $\beta$. If $\alpha \succeq \beta$, then $\raj(u) \geq \raj(v)$; if $\alpha \succ \beta$, then $\raj(u) > \raj(v)$.
\end{cor}

We now provide some lemmas without proof that are key to establishing our main results. For more details, see \cite{Pechenik.Speyer.Weigandt}.

\begin{lemma} \label{lem:valley_shape}
For each composition $\alpha$ of $n$, there is exactly one valley permutation, $f_{\alpha}$ of shape $\alpha$, and likewise one inverse valley permutation of shape $\alpha$, which is $f_{\alpha}^{-1}$.
\end{lemma}

\begin{figure}[ht]
\[
\begin{tikzpicture}[x=1.5em,y=1.5em]
\draw[step=1,gray, thin] (0,0) grid (9,9);
\draw[color=white, thick](0,0)rectangle(9,10);
\draw[color=black, thick](0,0)rectangle(9,9);
\node at (7.5,8.5) {$\bullet$};
\node at (6.5,7.5) {$\bullet$};
\node at (4.5,6.5) {$\bullet$};
\node at (1.5,5.5) {$\bullet$};
\node at (0.5,4.5) {$\bullet$};
\node at (2.5,3.5) {$\bullet$};
\node at (3.5,2.5) {$\bullet$};
\node at (5.5,1.5) {$\bullet$};
\node at (8.5,0.5) {$\bullet$};
\node at (-0.5,8.5) {$1$};
\node at (-0.5,7.5) {$2$};
\node at (-0.5,6.5) {$3$};
\node at (-0.5,5.5) {$4$};
\node at (-0.5,4.5) {$5$};
\node at (-0.5,3.5) {$6$};
\node at (-0.5,2.5) {$7$};
\node at (-0.5,1.5) {$8$};
\node at (-0.5,0.5) {$9$};
\node at (0.5,9.5) {$1$};
\node at (1.5,9.5) {$2$};
\node at (2.5,9.5) {$3$};
\node at (3.5,9.5) {$4$};
\node at (4.5,9.5) {$5$};
\node at (5.5,9.5) {$6$};
\node at (6.5,9.5) {$7$};
\node at (7.5,9.5) {$8$};
\node at (8.5,9.5) {$9$};
\node at (8.65,0.9) {\small $B_9$};
\node at (6.5,4.5) {$B_8$};
\node at (4.0,4.0) {$B_7$};
\node at (2.5,3.87) {\small $B_6$};
\node at (1.0,5.0) {$B_5$};
\draw[blue,thick, rotate around={-45:(1,5)}] (1,5) ellipse (.5 and .95);
\draw[blue,thick, rotate around={-40:(2.5,3.8)}] (2.5,3.8) ellipse (.5 and 0.7);
\draw[blue,thick, rotate around={-15:(4,4.4)}] (4,4.4) ellipse (.48 and 2.8);
\draw[blue,thick, rotate around={-15:(6.4,4.77)}] (6.4,4.7) ellipse (1.2 and 4.5);
\draw[blue,thick, rotate around={-30:(8.5,0.5)}] (8.5,0.5) ellipse (.5 and 0.9);
\end{tikzpicture}
\]	
\caption{For $\alpha = (2,1,2,3,1)$, the proof of Lemma~\ref{lem:valley_shape} gives $R = \{1 < 3 < 4 < 6 < 9 \}$ and $[9] \backslash R = \{ 8 > 7 > 5 > 2 \}$. So the corresponding valley permutation is $f = 875213469$. Here we have drawn the blob diagram of $f$.}
\label{fig:valley_figure}
\end{figure}

\begin{lemma} \label{cor:LR_raj_ineq}
Let $u$ and $v$ be permutations with $u \geq_{LR} v$. Then $\raj(u) \geq \raj(v)$. We have $\raj(u) = \raj(v)$ if and only if $u$ and $v$ have the same shape. 
\end{lemma}

\begin{lemma} \label{lem:cover_rajcode}
If $w >_L s_i w$ and $\raj(w) = \raj(s_i w)$, then $\rajc(w) = \rajc(s_i w)$. 
Suppose that $w >_R w s_i$ and $\raj(w) = \raj(w s_i)$. Let $\rajc(w) = (r_1, r_2, \ldots, r_n)$. Then $\rajc(w s_i) = (r_1, r_2, \ldots, r_{i+1}+1, r_i-1, \ldots, r_n)$. 
\end{lemma}

\begin{lemma}\label{lem:consecutiveblobs}
	The permutation $w\in S_n$ is fireworks if and only if the dots in each blob occupy consecutive rows of the graph of $w$.  Likewise, $w$ is inverse fireworks if and only if the dots in each blob occupy consecutive columns.
\end{lemma}

We now describe a \newword{fireworks map} that turns an arbitrary permutation $w$ into a fireworks permutation $\Phi(w)$. 
The fireworks permutation $\Phi(w)$ corresponds to the set partition $\pi(w)$ using the bijection of Proposition~\ref{prop:bell}.  
In other words, we take the dots in the graph of $w$ and shove the dots of each blob into consecutive rows. 
We define $\Phi_{\rm inv}(w) = \Phi(w^{-1})^{-1}$. 

For example, let $w=462357918$. We computed before that $\pi(w) = \{ 2,\, 34,\, 56,\, 17,\, 89 \}$. The corresponding fireworks permutation is $243657198$ with blob diagram below.

\[
\begin{tikzpicture}[x=1.3em,y=1.3em]
\draw[step=1,gray, thin] (0,0) grid (9,9);
\draw[color=white, thick](0,0)rectangle(9,10);
\draw[color=black, thick](0,0)rectangle(9,9);
\node at (3.5,7.5) {$\bullet$};
\node at (5.5,5.5) {$\bullet$};
\node at (1.5,8.5) {$\bullet$};
\node at (2.5,6.5) {$\bullet$};
\node at (4.5,4.5) {$\bullet$};
\node at (6.5,3.5) {$\bullet$};
\node at (8.5,1.5) {$\bullet$};
\node at (0.5,2.5) {$\bullet$};
\node at (7.5,0.5) {$\bullet$};
\node at (-0.5,8.5) {$1$};
\node at (-0.5,7.5) {$2$};
\node at (-0.5,6.5) {$3$};
\node at (-0.5,5.5) {$4$};
\node at (-0.5,4.5) {$5$};
\node at (-0.5,3.5) {$6$};
\node at (-0.5,2.5) {$7$};
\node at (-0.5,1.5) {$8$};
\node at (-0.5,0.5) {$9$};
\node at (0.5,9.5) {$1$};
\node at (1.5,9.5) {$2$};
\node at (2.5,9.5) {$3$};
\node at (3.5,9.5) {$4$};
\node at (4.5,9.5) {$5$};
\node at (5.5,9.5) {$6$};
\node at (6.5,9.5) {$7$};
\node at (7.5,9.5) {$8$};
\node at (8.5,9.5) {$9$};
\draw[blue,thick, rotate around={-60:(1.5,8.5)}] (1.5,8.5) ellipse (.5 and 1);
\draw[blue,thick, rotate around={-45:(3,7)}] (3,7) ellipse (.5 and 1.7);
\draw[blue,thick, rotate around={-45:(5,5)}] (5,5) ellipse (.5 and 1.7);
\draw[blue,thick, rotate around={-80:(3.5,3)}] (3.5,3) ellipse (.6 and 3.7);
\draw[blue,thick, rotate around={-45:(8,1)}] (8,1) ellipse (.5 and 1.7);
\end{tikzpicture}
\]	




\begin{lemma}\label{lem:fireworks_down}
	For any permutation $w$, we have $\Phi(w) \leq_R w$ and $\Phi_{\rm inv}(w)\leq_L w$. 
\end{lemma}

\begin{remark}
	Although $\Phi(w) \leq_R w$, this does not mean that $\Phi$ is order-preserving! For example, $\Phi(4312) = 1432$ and $\Phi(3412) = 3142$. Now $4312 = 3412 \cdot s_1$, so $3412 <_R 4312$, but $3142 \not \leq_R 1432$ since $1$ and $3$ are noninverted in $1432$, but inverted in $3142$.
\end{remark}




\begin{lemma}
\label{lemma:stayfireworks}
The blobs $B_k$ of $\Phi(w)$ and of $w$ consist of dots in the same columns, the permutation $w$ is fireworks if and only if $\Phi(w) = w$, and the permutations $w$ and $\Phi(w)$ have the same shape. 
Corresponding statements hold for $\Phi_{\rm inv}$ and being inverse fireworks. 
\end{lemma}

\begin{corollary}\label{cor:fireworksraj}
For $w \in S_n$, we have $\raj(w) = \raj(w^{-1})= \raj(\Phi(w)) = \raj(\Phi_{\rm inv}(w))$.
\end{corollary}

In the case of the inverse fireworks map, we can state a stronger result.

\begin{cor}\label{cor::leftfireworks_perserves_code}
	For any permutation $w$, we have $\rajc(w) = \rajc(\Phi_{\rm inv}(w))$.
\end{cor}


 For a composition $\alpha = (\alpha_1, \dots, \alpha_r)$, let $S_{\alpha}$ be the Young subgroup $S_{\alpha_1} \times  S_{\alpha_2} \times \cdots \times S_{\alpha_r}$ and let $e_\alpha$ be its longest element. 
A permutation $w$ is called \newword{layered} if $w = e_\alpha$ for some $\alpha$.

\begin{lemma} \label{lem:phi_phiL_layered}
Let $w$ be a permutation of shape $\alpha$. Then $\Phi(\Phi_{\rm inv}(w)) = \Phi_{\rm inv}(\Phi(w)) = e_{\alpha}$.
\end{lemma}

\begin{theorem} \label{thm:raj=mm}
For $w \in S_n$, 
 	$	\raj(w) = \max \{\maj(v) : v \leq_R w \} = \max \{\maj(u^{-1}) : u \leq_L w \}.$
\end{theorem}

We now discuss interactions between the fireworks maps and weak orders.

\begin{lemma}\label{lem:fireworks_factorizations}
	If $w \in S_n$ has shape $\alpha$, then $w$ has a unique length-additive factorization
	$
	w = ue_\alpha v,
	$
	for some permutations $u$, $v \in S_n$. Moreover, we have $\Phi(w) = ue_\alpha$ and $\Phi_{\rm inv}(w) = e_\alpha v$. 
\end{lemma}

We can use this factorization to understand the $\leq_{LR}$ interval $[e_{\alpha}, w]_{LR}$.

\begin{lem} \label{lem:interval_structure}
Let $w$ be a permutation of shape $\alpha$, and let $w = u e_{\alpha} v$ be the unique length-additive factorization of $w$. Then the map $\mu: (u', v') \mapsto u' e_{\alpha} v'$ is a poset isomorphism from the product $[e_\alpha, u]_L \times [e_\alpha,v]_R$ to the two-sided weak interval $[e_{\alpha}, w]_{LR}$.
\end{lem}

Weak order gives a new perspective on fireworks permutations of a given shape.
\begin{lem} \label{lem:maximal_is_valley}
Let $f_{\alpha}$ be the unique valley permutation of shape $\alpha$ (introduced in Lemma~\ref{lem:valley_shape}). Then the set of fireworks permutations of shape $\alpha$ is the left interval $[e_{\alpha}, f_{\alpha}^{-1}]_L$, and the set of inverse fireworks permutations of shape $\alpha$ is the right interval $[e_{\alpha}, f_{\alpha}]_R$. 
\end{lem}

\begin{lemma} \label{lem:ealpha_lemma}
Let $x$ be any permutation in $S_n$, let $\alpha = (\alpha_k, \alpha_{k+1}, \ldots, \alpha_n)$ be a composition of $n$, and let $y = e_{\alpha} \ast x \ast e_{\alpha}$, where $\ast$ denotes the Demazure product. Then $\raj(y) \geq \raj(e_{\alpha})$ and we have equality if and only if $y = e_{\alpha}$.
\end{lemma}

\begin{example} \label{eg:posetExample} 
We list all permutations of shape $\alpha = (1,1,2)$, their factorizations in the form $u e_{\alpha} v$, and the corresponding double Castelnuovo--Mumford polynomials:
\[ 
\begin{array}{|ccc|}
\hline
2341 &          & \\
1342 &          & \\
1243 & 1423 & 4123 \\
\hline
\end{array} \qquad
\begin{array}{|rrr|}
\hline
s_1 s_2 e_{112} && \\
s_2 e_{112} && \\
e_{112} & e_{112} s_2 & e_{112} s_2 s_1 \\
\hline
\end{array}\]
\[ \begin{array}{|lll|}
\hline
(x_1 x_2 x_3) (y_1^3) && \\
(x_1 x_2 x_3) (y_1^2 y_2 + y_1 y_2^2) && \\
(x_1 x_2 x_3) (y_1 y_2 y_3) & (x_1^2 x_2 + x_1 x_2^2) (y_1 y_2 y_3) & (x_1^3) (y_1 y_2 y_3) \\
\hline
\end{array}\]
\smallskip
The layered permutation $e_{112}=1243$ is in the lower left, the valley permutation $f_{112} = 4123$ is in the lower right and the inverse valley permutation $f_{112}^{-1} = 2341$ is in the upper left. 
The permutations in the left column are fireworks; the permutations in the bottom row are inverse fireworks, and the permutations which are maximally northeast are dominant.
The maps $\Phi$ and $\Phi_{\rm inv}$ are the orthogonal projections onto the left column and bottom row, respectively.
\end{example}


\begin{lemma}\label{lem:divided_diffs}
	If $u \leq_{LR} w$, then $\deg \fCM_u(\bx) \leq \deg \fCM_w(\bx)$.
\end{lemma}

\begin{example}
Note that the analogous result does not hold for the strong order.  For instance, $1432\leq 3412$ but $\deg \fG_{1432}(\bx)=5$ and $\deg \fG_{3412}(\bx)=4$.
\end{example}

\begin{lemma}\label{lem:deg_dominant}
	If $w$ is dominant, then 
$
	\deg \fCM_w(\bx) = \deg \fS_w(\bx)=\inv(w) = \raj(w).
$
\end{lemma}

 \begin{lemma}\label{lem:deg_ealpha}
 	If $w= e_\alpha$, then $\deg \fCM_{w}(\bx) = \raj(w)$.
 \end{lemma}

\begin{proposition}\label{prop:dominantMaxShape}
	Let $w \in S_n$ have shape $\alpha$. The permutation $w$ is $\leq_{LR}$-maximal among permutations of shape $\alpha$ if and only if $w$ is dominant.
\end{proposition}

\begin{theorem} \label{thm:raj=deg}
	Let $w \in S_n$. Then $\deg \fCM_w(\bx) = \raj(w)$.
\end{theorem}

\begin{definition}
Let $\pi$ be a set partition of $[n]$ and let $w$ be the unique fireworks permutation with $\pi(w) = \pi$. 
We define the  \newword{Rajchgot polynomial} $\fR_{\pi}(\bx)$ to be $\fCM_w(\bx)$.
\end{definition}

\begin{theorem}\label{thm:factorization}
For any $w \in S_n$, we have
$ \fCM_w(\bx;\by) = \fR_{\pi(w)}(\bx) \fR_{\pi(w^{-1})}(\by). $
\end{theorem}

\begin{lemma}\label{lem:demazure_fireworks}
Let $p \in [\Phi_{\rm inv}(w), w]_L$ and $q \in [\Phi(w), w]_R$. Then $q \ast p = w$ if and only if $p = \Phi_{\rm inv}(w)$ and $q = \Phi(w)$.
\end{lemma}
By Lemma~\ref{lem:fireworks_factorizations}, each permutation $w \in S_n$ with $\alpha(w) = \alpha$ has a unique length-additive factorization $w = ue_\alpha v$, where $\Phi(w) = ue_\alpha$ and $\Phi_{\rm inv}(w) = e_\alpha v$. Therefore, the interval $[\Phi_{\rm inv}(w), w]_L$ is $\{ u' e_{\alpha} v : \id \leq_L u' \leq_L u \}$ and $[\Phi(w), w]_R$ is $\{ u e_{\alpha} v' : \id \leq_R v' \leq_R v \}$. 

\begin{Theorem} \label{thm:exponentbound}
Let $w$ be a permutation, let $\rajc(w) = (r_1, \ldots, r_n)$ and let $\rajc(w^{-1}) = (s_1, \ldots, s_n)$. For any term order satisfying $x_1 < x_2 < \cdots < x_n$ and $y_1 < y_2 < \cdots < y_n$, every monomial of $\fCM_w(\bx; \by)$ is at most $x_1^{r_1} \cdots x_n^{r_n} y_1^{s_1} \cdots y_n^{s_n}$. 
\end{Theorem}

The primary statement now outstanding from Theorems~\ref{thm:degree} and~\ref{thm:main} is that there is a pipe dream for $w$ with
$\rajc_i(w)$ crossing tiles in row $i$ and $\rajc_j(w^{-1})$ crossing tiles in column $j$, thereby contributing the 
 monomial $\bx^{\rajc(w)} \by^{\rajc(w^{-1})}$ to $\fCM_w(\bx;\by)$. We call such a pipe dream a \newword{maximal pipe dream} for $w$.

\begin{Theorem} \label{thm:exponentachieved}
Let $w$ be a permutation, let $\rajc(w) = (r_1, \ldots, r_n)$ and let $\rajc(w^{-1}) = (s_1, \ldots, s_n)$.  
There is a unique pipe dream for $w$ with $r_i$ crosses in row $i$ and $s_j$ crosses in column $j$.  Hence, the monomial $\bx^{\rajc(w)} \by^{\rajc(w^{-1})}$ appears with coefficient $1$ in $\fCM_w(\bx; \by)$.
\end{Theorem}

\acknowledgements{
We are grateful to Jenna Rajchgot and Colleen Robichaux for helpful conversations and to the referees for their helpful comments. 
}

\printbibliography

\end{document}

