%% 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{7}
%% 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{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}{Claim}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{def-prop}[theorem]{Definition-Proposition}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{conj}[theorem]{Conjecture}

\theoremstyle{definition}
\newtheorem{ex}{Example}
\newtheorem{quest}{Question}
\newtheorem{defin}[theorem]{Definition}

\theoremstyle{remark}
\newtheorem{remark}{Remark}

\usepackage{lipsum}
\usepackage{tikz}
\usepackage{mathtools}

\DeclareMathOperator{\fl}{fl}
\DeclareMathOperator{\mh}{mHeight}
\DeclareMathOperator{\mcontent}{mCont}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\inv}{Inv}
\DeclareMathOperator{\Lie}{Lie}
\DeclareMathOperator{\spn}{span}
\DeclareMathOperator{\mg}{mag}
\DeclareMathOperator{\sgn}{sign}

\newcommand{\ph}{\varphi}
\newcommand{\mc}{\mathcal}
\newcommand{\mf}{\mathfrak}
\newcommand{\bs}{\boldsymbol}
\renewcommand{\tilde}{\widetilde}
\newcommand{\e}{\varepsilon}
\renewcommand{\arraystretch}{1.4}

\newcommand{\GL}{\mathrm{GL}}
\newcommand{\SL}{\mathrm{SL}}
\newcommand{\SO}{\mathrm{SO}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Q}{\mathbb{Q}}
\renewcommand{\S}{\mathfrak{S}}
\newcommand{\D}{\mathfrak{D}}

\newcommand\precdot{\mathrel{\ooalign{$\prec$\cr
  \hidewidth\raise0.001ex\hbox{$\cdot\mkern0.6mu$}\cr}}}
%% define your title in the usual way
\title{Pattern heights and the minimal power of $q$ in a Kazhdan--Lusztig polynomial}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Christian Gaetz\thanks{\href{mailto:gaetz@berkeley.edu}{gaetz@berkeley.edu}}\addressmark{1} \and Yibo Gao\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, University of California, Berkeley, CA, USA \\ \addressmark{2}Beijing International Center for Mathematical Research, Peking University, Beijing, CN}

%% 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{For $w$ in the symmetric group, we use permutation patterns to provide an exact formula for the smallest positive power $q^{h(w)}$ appearing in the Kazhdan--Lusztig polynomial $P_{e,w}(q)$. We also use Weyl group patterns to provide a tight upper bound on $h(w)$ in simply-laced types, resolving a conjecture of Billey--Postnikov from 2002.}

%% 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{Kazhdan--Lusztig polynomial, permutation pattern, Bruhat order}

%% 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{fpsac-revision.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{Introduction}
\label{sec:intro}
Let $G$ be a complex semisimple Lie group, with Borel subgroup $B$ containing maximal torus $T$ and corresponding Weyl group $W$. The Bruhat decomposition $G=\bigsqcup_{w \in W} BwB$ gives rise to the \emph{Schubert varieties} $X_w \coloneqq \overline{BwB/B}$ inside the flag variety $G/B$, whose containments determine the Bruhat order on $W$: $y \leq w$ if $X_y \subset X_w$. The \emph{Kazhdan--Lusztig polynomials} $P_{y,w}(q) \in \mathbb{Z}[q]$ have since their discovery \cite{Kazhdan-Lusztig-1} proven to underlie deep connections between canonical bases of Hecke algebras, singularities of Schubert varieties, and representations of Lie algebras.


\begin{theorem}[Kazhdan and Lusztig \cite{Kazhdan-Lusztig-2}]
\label{thm:IH-interpretation-of-kl-polys}
For $y \leq w$, let $IH^*(X_w)_y$ denote the local intersection cohomology of $X_w$ at the $T$-fixed point $yB$, then 
\[ P_{y,w}(q) = \sum_i \dim(IH^{2i}(X_w)_y) q^i.\]
\end{theorem}

Theorem~\ref{thm:IH-interpretation-of-kl-polys} implies that $P_{y,w}(q)$ has nonnegative coefficients, a property which is completely obscured by their recursive definition (Definition~\ref{def:kl-polys}). It is known that for all $y \leq w$ one has $P_{y,w}(0)=1$.

\begin{theorem}[Deodhar \cite{Deodhar-smooth}; Peterson (see \cite{Carrell-Kuttler-1})]
\label{thm:smooth-iff-kl-poly-trivial}
If $G$ is simply-laced and $y \leq w$, then $X_w$ is smooth at $yB$ if and only if $P_{y,w}(q)=1$. In particular, $X_w$ is smooth if and only if $P_{e,w}(q)=1$.
\end{theorem}

In light of Theorem~\ref{thm:IH-interpretation-of-kl-polys}, one wants to understand $P_{y,w}(q)$ explicitly enough to determine which coefficients vanish. Indeed, the view of the $P_{y,w}$ as a measure of the failure of local Poincar\'{e} duality in $X_w$ was among the original motivations in \cite{Kazhdan-Lusztig-1}. Unfortunately, $P_{y,w}$ may be arbitrarily complicated \cite{Polo} and the formulae \cite{Brenti-combinatorial-formula} which exist involve cancellation, and are thus not well-suited to this problem. If $X_w$ is singular (as is typically true) one can at least ask for the smallest nontrivial coefficient, the first degree in which Poincar\'{e} duality fails. Writing $[q^i]P_{y,w}$ for the coefficient of $q^i$ in $P_{y,w}(q)$, define:
\[
    h(w) \coloneqq \min \{i>0 \mid [q^i]P_{e,w} \neq 0 \}= \min_{y \leq w} \min \{i>0 \mid [q^i]P_{y,w} \neq 0\}.
\]
 The second equality follows from the monotonicity property of the $P_{y,w}$ \cite{Braden-MacPherson-monotonicity}. We make the convention that $h(w)=+ \infty$ when $X_w$ is smooth.

\begin{conj}[Billey and Postnikov \cite{Billey-Postnikov}]
\label{conj:bp-conjecture}
Let $G$ be simply-laced of rank $r$, and suppose $X_w$ is singular. Then $h(w) \leq r$.
\end{conj}

Billey and Postnikov's conjecture is somewhat surprising, since $\deg(P_{y,w})$ may be as large as $\frac{1}{2}(\ell(w)-\ell(y)-1)$ which is of the order of $r^2$, where $\ell$ denotes length. An upper bound on $h(w)$ in certain special infinite Coxeter groups was given in \cite{Richmond-Slofstra-triangle-group}.

The decomposition $X_w = \bigsqcup_{y \leq w} ByB/B$ is an affine paving, with the cell $ByB/B$ having complex dimension $\ell(y)$. We thus have
\[
L(w) \coloneqq \sum_{y \leq w} q^{\ell(y)} = \sum_{j \geq 0} \dim(H^{j}(X_w))q^{j/2},
\]
the Poincar\'{e} polynomial of $X_w$. Bj\"{o}rner--Ekedahl \cite{Bjorner-Ekedahl} gave a precise interpretation of $h(w)$ in terms of $L(w)$, as the smallest homological degree in which Poincar\'{e} duality fails.

\begin{theorem}[Bj\"{o}rner and Ekedahl \cite{Bjorner-Ekedahl}]
\label{thm:bjorner-ekedahl}
For $0 \leq i \leq \ell(w)/2$ we have $[q^i]L(w) \leq [q^{\ell(w)-i}]L(w)$, and 
\[
h(w)=\min \{i > 0 \mid [q^i]L(w) < [q^{\ell(w)-i}]L(w)\}.
\]
\end{theorem}

Theorem~\ref{thm:bjorner-ekedahl} will be a useful tool in this work, but cannot be directly used to resolve Conjecture~\ref{conj:bp-conjecture} since it is difficult to compute $[q^i]L(w)$ in general.

Our first main theorem\footnote{A full version of this work is available at \cite{arxiv-version}} is a refinement and proof of Conjecture~\ref{conj:bp-conjecture}.
\begin{theorem}
\label{thm:simply-laced-upper-bound}
Let $G$ be simply-laced of rank $r$, and suppose $X_w$ is singular. Then $h(w) \leq r-2$.
\end{theorem}
The bound of $r-2$ is tight when $G$ is a member of the infinite families $\SL_{r+1}$ or $\SO_{2r}$. When $G$ is one of the exceptional simply-laced groups of type $E_6,E_7,$ or $E_8$, Theorem~\ref{thm:simply-laced-upper-bound} follows from the computations made by Billey--Postnikov \cite{Billey-Postnikov}. In the case $G=\SL_{n+1}$, the theorem can be derived from the classification of the singular locus of $X_w$ \cite{Billey-Warrington, Manivel}. However, in this case we provide a new exact formula for $h(w)$ for any permutation $w$. This theorem is phrased in terms of \emph{pattern containment} (see Section~\ref{sec:pattern-conventions}).

\begin{theorem}
\label{thm:type-A-formula}
Let $G=\SL_{n+1}$, and suppose $X_w$ is singular. Then 
\[ h(w)=\begin{cases} 1 &\text{ if $w$ contains $4231$,} \\
\mh(w) &\text{ otherwise,} \end{cases}\]
where $\mh(w)$ denotes the minimum height of a $3412$ pattern in $w$. 
\end{theorem}

In the case $P_{e,w}(1)=2$, Theorem~\ref{thm:type-A-formula} follows from the work of Woo \cite{Woo}. Our theorem adds to the deep \cite{Woo-Yong-governing} and ubiquitous \cite{Billey-Abe} links between singularities of Schubert varieties and pattern containment.

\section{Preliminaries}
\label{sec:prelim}
\subsection{Bruhat order and Kazhdan--Lusztig polynomials}
Let $W$ be a Weyl group with simple reflections $S=\{s_1,s_2,\ldots\}$ and length function $\ell$. Write $\mathcal{R}$ for the set of reflections (conjugates of simple reflections), then \emph{Bruhat order $\leq$} on $W$ is defined as the transitive closure of the relation $y<yr$ if $r \in \mathcal{R}$ and $\ell(y)<\ell(yr)$. 

The left (respectively, right) \emph{descents} $D_L(w)$ (resp. $D_R(w)$) are those $s \in S$ such that $sw<w$ (resp. $ws<w$). 

\begin{defin}[Kazhdan and Lusztig \cite{Kazhdan-Lusztig-1}]
\label{def:kl-polys}
Define polynomials $R_{y,w}(q) \in \Z[q]$ by setting $R_{y,w}(q)=0$ if $y \not \leq w$, $R_{y,w}(q)=1$ if $y=w$, and requiring:
\[R_{y,w}(q) = \begin{cases}  R_{ys,ws}(q), &\text{ if $s \in D_R(y) \cap D_R(w)$, and} \\ qR_{ys,ws}(q) + (q-1)R_{y,ws}, &\text{ if $s \in D_R(w)\setminus D_R(y)$.}\end{cases}\]
Then there is a unique family of polynomials $P_{y,w}(q) \in \Z[q],$ the \emph{Kazhdan--Lusztig polynomials} satisfying $P_{y,w}(q)=0$ if $y \not \leq w$, $P_{w,w}(q)=1$, and such that if $y<w$ then $P_{y,w}$ has degree at most $\frac{1}{2}(\ell(w)-\ell(y)-1)$ and 
\[q^{\ell(w)-\ell(y)}P_{y,w}(q^{-1})=\sum_{a \in [y,w]} R_{y,a}(q)P_{a,w}(q).\]
\end{defin}

Although not apparent from Definition~\ref{def:kl-polys}, the $P_{y,w}$ satisfy an inversion symmetry: 

\begin{prop}
\label{prop:kl-of-inverse}
Let $y,w \in W$, then $P_{y,w}(q)=P_{y^{-1},w^{-1}}(q)$. In particular, $h(w)=h(w^{-1})$.
\end{prop}
 
\subsection{Fiber bundles of Schubert varieties}

For $J \subset S$, we write $W_J$ for the subgroup generated by $J$, $P_J$ for the parabolic subgroup of $G$ generated by $B$ and $J$, and $W^J$ for the set of minimal length representatives of the left cosets $W/W_J$. We have $W^J=\{w \in W \mid D_R(w) \cap J = \emptyset\}$. Each $w \in W$ decomposes uniquely as $w^Jw_J$ with $w^J \in W^J$ and $w_J \in W_J$.  Using right cosets instead gives decompositions $w=\prescript{}{J}{w} \prescript{J}{}{w}$ with $\prescript{}{J}{w} \in W_J$ and $\prescript{J}{}{w} \in \prescript{J}{}{W} = (W^J)^{-1}$. Notice that $(w^{-1})_J = (\prescript{}{J}{w})^{-1}.$

We write $w_0(J)$ for the unique element of $W_J$ of maximum length and write $[u,v]^J$ for the set $[u,v] \cap W^J$. Since parabolic decompositions are unique, we have an injection $[e,w^J]^J \times [e,w_J] \hookrightarrow [e,w]$ given by multiplication.

Schubert varieties $X_{w^J}^J \coloneqq \overline{Bw^JP_J/P_J}$ in the partial flag variety $G/P_J$ have an affine paving by $ByP_J/P_J$ for $y \in W^J$ and $y \leq w^J$, and so
\[L^J(w^J) \coloneqq \sum_{\substack{y \in W^J \\ y \leq w^J}} q^{\ell(y)} = \sum_{j \geq 0} \dim(H^j(X^J_{w^J}))q^{j/2}.
\]

\begin{defin}[Richmond and Slofstra \cite{Richmond-Slofstra-fiber-bundle}]
\label{def:bp-decompositions}
The parabolic decomposition $w=w^J w_J$ is called a \emph{Billey--Postnikov decomposition} or \emph{BP-decomposition} of $w$ if $\supp(w^J) \cap J \subset D_L(w_J)$.
\end{defin}

\begin{theorem}[Richmond and Slofstra \cite{Richmond-Slofstra-fiber-bundle}]
\label{thm:bp-decomposition-fiber-bundle}
The map $X_w \twoheadrightarrow X^J_{w^J}$ induced by the map $G/B \to G/P_J$ is a bundle projection if and only if $J$ is a BP-decomposition of $w$, and in this case the fiber is isomorphic to $X_{w_J}$. Taking Poincar\'{e} polynomials, we have $L^J(w^J)L(w_J)=L(w)$ in this case.
\end{theorem}

\subsection{Patterns in Weyl groups}
\label{sec:prelim-patterns}
Let $\Phi$ denote the root system for $G$, with positive roots $\Phi^+$ and simple roots $\Delta$. For $w \in W$, the \emph{inversion set} is $\inv(w)\coloneqq \{\alpha \in \Phi^+ \mid w\alpha \in \Phi^-\}$.

A subgroup $W'$ of $W$ generated by reflections is called a \emph{reflection subgroup}, and is itself a Coxeter group with reflections $\mathcal{R}'=\mathcal{R} \cap W'$. We write $\leq'$ for the intrinsic Bruhat order on $W'$, $\Phi'$ for the root system, and $\inv'$ for inversion sets. 

\begin{prop}[Billey and Braden \cite{Billey-Braden}; Billey and Postnikov \cite{Billey-Postnikov}]
\label{prop:flattening-map}
Let $W' \subset W$ be a reflection subgroup, there is a unique function $\fl: W \to W'$, the \emph{flattening map} satisfying:
\begin{enumerate}
    \item[\normalfont{(1)}] $\fl$ is $W'$-equivariant, and
    \item[\normalfont{(2)}] if $\fl(x) \leq' \fl(wx)$ for some $w \in W'$, then $x \leq wx$.
\end{enumerate}
Furthermore, $\fl$ has the following explicit description: $\fl(w)$ is the unique element $w' \in W'$ with $\inv'(w')=\inv(w) \cap \Phi'$. If $W'=W_J$ is a parabolic subgroup, then $\fl(w)=w_J$.
\end{prop}

\begin{defin}
\label{def:pattern-avoidance}
We say that $w \in W$ \emph{contains the pattern} $w'' \in W''$, if $W$ has some reflection subgroup $W'$, with an isomorphism $W'\xrightarrow{\ph} W''$ as Coxeter systems, such that $\ph(\fl(w))=w''$. Otherwise, $w$ is said to \emph{avoid} $w''$.
\end{defin}

We will make use of the following result, which is proven using patterns.

\begin{theorem}[Billey and Braden \cite{Billey-Braden}]
\label{thm:h-increases-in-parabolic}
Let $J \subset S$, then $h(w) \leq h(w_J)$.
\end{theorem}

Billey and Postnikov gave the following characterization of smooth Schubert varieties, generalizing the work of Lakshmibai--Sandhya \cite{Lakshmibai-Sandhya}. We write $W(Z)$ to denote the Weyl group of Type $Z$, where $Z$ is one of the types in the Cartan--Killing classification.

\begin{theorem}[Billey and Postnikov \cite{Billey-Postnikov}]
\label{thm:bp-smoothness}
Let $G$ be simply-laced, then the Schubert variety $X_w \subset G/B$ is smooth if and only if $w$ avoids the following patterns: $s_2s_1s_3s_2 \in W(A_3)$, $s_1s_2s_3s_2s_1 \in W(A_3)$, and $s_2s_0s_1s_3s_2 \in W(D_4)$.
\end{theorem}

\subsection{Conventions for simply-laced groups}
\subsubsection{$G=\SL_{n}$ (Type $A_{n-1}$)}
We let $B$ be the set of lower triangular matrices in $G$, and $T \subset B$ the diagonal matrices in $G$. We have $\Phi(A_{n-1}) = \{e_j-e_i \mid 1 \leq i \neq j \leq n\}, \Phi^+(A_{n-1}) = \{e_j-e_i \mid 1 \leq i<j \leq n\}$, and $\Delta(A_{n-1}) = \{e_{i+1}-e_i \mid 1 \leq i \leq n-1\}$.

Under these conventions, the Weyl group $W(A_{n-1})$ acts on $\Lie_{\R}(T)^* = \R^n / (1,\ldots,1)$ by permutation of the coordinates, yielding an isomorphism $W(A_{n-1})$ with the symmetric group $\S_n$. Letting $\alpha_i \coloneqq e_{i+1}-e_i$, the corresponding simple reflection $s_i$ is identified with the transposition $(i \: i+1)$. It will often be convenient for us to write permutations $w$ in one-line notation as $w(1)\ldots w(n)$. The Dynkin diagram is shown in Figure~\ref{fig:dynkin-diagrams}.

\begin{figure}
\centering
\begin{tikzpicture}[scale=0.6]
\draw(3,0)--(0,0);
\draw(7,0)--(5,0);
\node[draw,shape=circle,fill=black,scale=0.5] at (0,0) {};
\node[draw,shape=circle,fill=black,scale=0.5] at (1,0) {};
\node[draw,shape=circle,fill=black,scale=0.5] at (2,0) {};
\node[draw,shape=circle,fill=black,scale=0.5] at (3,0) {};
\node[draw,shape=circle,fill=black,scale=0.5] at (5,0) {};
\node[draw,shape=circle,fill=black,scale=0.5] at (6,0) {};
\node[draw,shape=circle,fill=black,scale=0.5] at (7,0) {};
\node[draw,shape=circle,fill=black,scale=0.5][label=below: {$1$}] at (0,0) {};
\node[draw,shape=circle,fill=black,scale=0.5][label=below: {$2$}] at (1,0) {};
\node[draw,shape=circle,fill=black,scale=0.5][label=below: {$3$}] at (2,0) {};
\node[draw,shape=circle,fill=black,scale=0.5][label=below: {}] at (3,0) {};
\node[draw,shape=circle,fill=black,scale=0.5][label=below: {}] at (5,0) {};
\node[draw,shape=circle,fill=black,scale=0.5][label=below: {}] at (6,0) {};
\node[draw,shape=circle,fill=black,scale=0.5][label=below: {$n{-}1$}] at (7,0) {};
\node at (4,0) {$\cdots$};
\node at (-2,0) {$A_{n-1}$};

\draw(12,-.8)--(13,0)--(12,0.8);
\draw(13,0)--(15,0);
\draw(17,0)--(19,0);
\node at (16,0) {$\cdots$};
\node[draw,shape=circle,fill=black,scale=0.5][label=above: {$0$}] at (12,0.8) {};
\node[draw,shape=circle,fill=black,scale=0.5][label=below: {$1$}] at (12,-.8) {};
\node[draw,shape=circle,fill=black,scale=0.5][label=below: {$2$}] at (13,0) {};
\node[draw,shape=circle,fill=black,scale=0.5][label=below: {$3$}] at (14,0) {};
\node[draw,shape=circle,fill=black,scale=0.5][label=below: {}] at (15,0) {};
\node[draw,shape=circle,fill=black,scale=0.5][label=below: {}] at (17,0) {};
\node[draw,shape=circle,fill=black,scale=0.5][label=below: {}] at (18,0) {};
%\node[draw,shape=circle,fill=black,scale=0.5] at (7,-3) {};
\node[draw,shape=circle,fill=black,scale=0.5][label=below: {$n{-}1$}] at (19,0) {};
\node at (10.5,0) {$D_n$};
\end{tikzpicture}
    \caption{The Dynkin diagrams for Types $A_{n-1}$ and $D_n$.}
    \label{fig:dynkin-diagrams}
\end{figure}

\subsubsection{$G=\SO_{2n}$ (Type $D_n$)}
We let $B$ be the set of lower triangular matrices in $G$, and $T \subset B$ the diagonal matrices in $G$. We have $\Phi(D_n) = \{e_j \pm e_i \mid 1 \leq i \neq j \leq n\}, \Phi^+(D_n) = \{e_j \pm e_i \mid 1 \leq i<j \leq n\},$ and $\Delta(D_n) = \{e_2+e_1\} \cup \{e_{i+1}-e_i \mid 1 \leq i \leq n-1\}$.

Under these conventions, the Weyl group $W(D_n)$ acts on $\Lie_{\R}(T)^* = \R^n$ by permuting coordinates and negating pairs of coordinates. This identifies $W(D_n)$ with the permutations $w$ of $\{-n, \ldots, -1, 1, \ldots, n\}$ satisfying $w(i)=-w(-i)$ for all $i$, and such that $|\{w(1),\ldots,w(n)\}\cap \{-n,\ldots,-1\}|$
is even. We write $\D_n$ for this realization of $W(D_n)$. Such a permutation can be uniquely specified by its \emph{window notation} $[w(1)\ldots w(n)]$.

Write $\delta_0=e_2+e_1$ and $\delta_i=e_{i+1}-e_i$, $i=1,2,\ldots,n-1$ for the simple roots. It will often be convenient for us to write $\bar{i}$ for $-i$, and we use these interchangeably. We also make the convention that $e_{\bar i}=e_{-i}\coloneqq -e_i$ for $i>0$. We have simple reflections $s_0=(1 \: \bar{2}) (\bar{1} \: 2)$ and $s_i=(i \: i+1)(\bar{i} \: \overline{i{+}1})$ for $i=1,\ldots,n-1$.

\subsection{Reflection subgroups and diagram automorphisms}

See Figure~\ref{fig:dynkin-diagrams} for our labeling of the Dynkin diagrams. The following is clear:

\begin{prop}
\label{prop:auto-preserves-h}
The diagram of the Type $A_{n-1}$ has an automorphism $\e_A$ sending $\alpha_i \mapsto \alpha_{n-i}$ for $i=1,\ldots,n-1$, and the diagram of Type $D_n$ has an automorphism $\e_D$ interchanging $\delta_0\leftrightarrow \delta_1$. If $\e \in \{\e_A,\e_D\}$, then $h(w)=h(\e_D(w))$.
\end{prop}

\subsubsection{Reflection subgroups}

In light of Theorem~\ref{thm:bp-smoothness}, we will be concerned with reflection subgroups isomorphic to $W(A_3)$ and $W(D_4)$ inside $W(A_{n-1})$ and $W(D_n)$. 

\begin{prop}
\label{prop:reflection-subgroups}
Reflection subgroups isomorphic to $W(A_3)$ and $W(D_4)$ inside $W(A_{n-1})$ and $W(D_n)$ are characterized as follows:
\begin{itemize}
    \item[(a)] No reflection subgroup $W' \subset W(A_{n-1})$ is isomorphic to $W(D_4)$.
    \item[(b)] Reflection subgroups $W' \cong W(A_3)$ inside $W(A_{n-1})$ are conjugate to the parabolic subgroup $W(A_{n-1})_{\{1,2,3\}}$.
    \item[(c)] Reflection subgroups $W' \cong W(D_4)$ inside $W(D_n)$ are conjugate to the parabolic subgroup $W(D_n)_{\{0,1,2,3\}}$.
    \item[(d)] Reflection subgroups $W' \cong W(A_3)$ inside  $W(D_n)$ come in two classes: those related to $W(D_n)_{\{1,2,3\}}$ by conjugacy and $\e_D$ (Class I), and those conjugate to $W(D_n)_{\{0,1,2\}}$ (Class II).
\end{itemize}
\end{prop}


\subsubsection{One line notation and patterns}
\label{sec:pattern-conventions}
We will be interested in occurrences of the patterns from Theorem~\ref{thm:bp-smoothness} in elements $w \in W(A_{n-1})$ or $W(D_n)$. For $w \in W(D_n)$, it will sometimes be useful for us to distinguish between Class I and II patterns (see Proposition~\ref{prop:reflection-subgroups}(d)). Realizing these Weyl groups as $\S_n$ and $\D_n$, respectively, allows for one-line interpretations of pattern containment (summarized in Figure~\ref{fig:smooth-patterns}). This approach to pattern containment is in some sense a hybrid between the approaches of Billey \cite{Billey-signed-patterns} using signed patterns and of Billey, Braden, and Postnikov \cite{Billey-Postnikov, Billey-Braden} using patterns in the sense of Definition~\ref{def:pattern-avoidance}. Our distinction between Class I and II patterns is seemingly novel and reflects the disparate effects that occurrences of these patterns can have on $h(w)$.

\begin{defin} \text{}
\label{def:signed-pattern}
\begin{itemize}
    \item[(i)] For $p$ a signed permutation of $[k]$, we say $w \in \D_n$ contains $p$ at positions $1 \leq i_1 < \cdots < i_k \leq n$ if $\sgn(w(i_j))=\sgn(p(j))$ for $j=1,\ldots,k$ and $|w(i_1)|,\ldots,|w(i_k)|$ are in the same relative order as $|p(1)|,\ldots,|p(k)|$.
    \item[(ii)] For $p \in \S_k$, we say $w \in \S_n$ contains $p$ at positions $1 \leq i_1 < \cdots < i_k \leq n$ if $w(i_1),\ldots,w(i_k)$ have the same relative order as $p(1),\ldots,p(k)$. We say $u \in \D_n$ contains $p$ at positions $i_1 < \cdots <i_k$, where each $i_j \in \pm [n]$ if $u(i_1),\ldots,u(i_k)$ have the same relative order as $p(1),\ldots,p(k)$ and $|i_1|,\ldots,|i_k|$ are distinct.
\end{itemize}
In each case, we say that the \emph{values} of the occurrence are $w(i_1),\ldots,w(i_k)$.
\end{defin}

The following is a translation of Theorem~\ref{thm:bp-smoothness} in light of our conventions for patterns.

\begin{prop}
\label{prop:hybrid-patterns}
Let $G$ be simply-laced; then $X_w \subset G/B$ is smooth if and only if $w$ avoids the patterns $3412, \pm 1 2 \bar{3}, 4231, \pm 1 \bar{3} \bar{2},$ and $\pm 1 4\bar{3}2$ (see Figure~\ref{fig:smooth-patterns}).
\end{prop}

\begin{figure}
    \centering
    \begin{tabular}{|c|c|c|c|}
    \hline 
    Type & Class & Pattern & One-line \\  \hline
    $A_3$ & I & $s_2s_1s_3s_2$ & $3412$ \\ \hline
    $A_3$ & II & $s_2s_1s_3s_2$ & $\pm 1 2 \bar{3}$ \\ \hline
    $A_3$ & I & $s_1s_2s_3s_2s_1$ & $4231$ \\ \hline
    $A_3$ & II & $s_1s_2s_3s_2s_1$ & $\pm 1 \bar{3} \bar{2}$ \\ \hline
    $D_4$ &  & $s_2s_0s_1s_3s_2$ & $\pm 1 4 \bar{3} 2$ \\ \hline
    \end{tabular}
    \caption{The patterns from Theorem~\ref{thm:bp-smoothness} with their one-line notations, divided according to type and class.}
    \label{fig:smooth-patterns}
\end{figure}

The following statistic on occurrences of the pattern $3412$ will be of special importance for us (see Theorem~\ref{thm:type-A-formula}).

\begin{defin}[See \cite{Cortez-2, Woo}]
\label{def:height}
We say an occurrence of $3412$ in $w \in \S_n$ or $\D_n$ at positions $a<b<c<d$ has \emph{height} equal to $w(a)-w(d)$. We let $\mh(w)$ denote the minimum height over all occurrences of $3412$ in $w$.
\end{defin}

\section{Upper bounds on $h(w)$}
\label{sec:upper-bounds}
\subsection{Proof strategy}
We will identify certain patterns $p$ (among those from Proposition~\ref{prop:hybrid-patterns}) such that if $w$ contains $p$, then $h(w)$ can be computed using Theorem~\ref{thm:bjorner-ekedahl} and an analysis of the Bruhat covers of $w$. Then, for $w$ avoiding these patterns and containing others, we will---by a combination of parabolic reduction (Theorem~\ref{thm:h-increases-in-parabolic}), inversion (Proposition~\ref{prop:kl-of-inverse}), and diagram automorphisms (Proposition~\ref{prop:auto-preserves-h})---obtain a bound $h(w) \leq h(u)$ for $u$ in some special family $\mathcal{S}$. Finally, we will show that elements $u \in \mathcal{S}$ have distinguished BP-decompositions such that the base and fiber in the bundle (Theorem~\ref{thm:bp-decomposition-fiber-bundle}) with total space $X_u$ can be understood, allowing for the computation of $h(u)$. In the remainder, we refer primarily to the elements $w \in W$ rather than the Schubert varieties $X_w$ that they index, although each of these steps has a geometric basis. We say $w$ is \emph{smooth} (resp. \emph{singular}) if $X_w$ is smooth (resp. singular).

We only have space to give a few representative proofs and proof ideas in this extended abstract.

\begin{prop}\label{prop:h-equals-1}
Let $w \in \S_n$ or $\D_n$; we have $h(w)=1$ if $w$ contains:
\begin{itemize}
    \item[(i)] $4231$ and $w \in \S_n$,
    \item[(ii)] $\pm 1 2 \bar{3}$,
    \item[(iii)] $\pm 1 4 \bar{3} 2$, or
    \item[(iv)] $3412$ of height one.
\end{itemize}
\end{prop}

\begin{proof}[Proof idea]
The strategies for all cases are similar: containment of any of these patterns implies a relation $\tau_1+\tau_2=\tau_3+\tau_4$ for $\tau_1,\tau_2,\tau_3,\tau_4\in\inv(w)$. We show that this implies a relation between roots indexing lower Bruhat covers of $w$. By results of Dyer \cite{Dyer}, this implies that $[q^{\ell(w)-1}]L(w) > [q] L(w)$, so that $h(w)=1$ by Theorem~\ref{thm:bjorner-ekedahl}. 
\end{proof}

\subsection{Proof of Theorem~\ref{thm:simply-laced-upper-bound} in Type $A$}\label{sub:typeA-upper-bound}
In this section we obtain an upper bound on $h(w)$ for $w \in \S_n$ in terms of $\mh(w)$; this establishes Theorem~\ref{thm:simply-laced-upper-bound} for $W=\S_n$ as well as one direction of Theorem~\ref{thm:type-A-formula}.

\begin{lemma}\label{lem:typeA-extremal-case}
For $n\geq4$, consider $w\in \S_n$ where $w(1)=n-1$, $w(2)=n$, $w(n-1)=1$, $w(n)=2$ and $w(i)=n-i+1$ for $3\leq i\leq n-2$. Then $h(w)=n-3$. 
\end{lemma}
\begin{proof}
Let $J=\{2,3,\ldots,n-2\}$ so that $w_J=w_0(J)$. The parabolic decomposition $w=w^Jw_J$ is a Billey--Postnikov decomposition. Moreover, $L(w_J)=L(w_0(J))$ is palindromic, since $X_{w_0(J)}$ is a product of flag varieties and therefore smooth. Every $u\in W^J$ satisfies $u(2)<u(3)<\cdots<u(n{-}1)$ so by counting inversions with $u(1)$ and $u(n)$, we see $\ell(u)=(u(1)-1)+(n-u(n))-\boldsymbol{1}_{u(1)>u(n)}$. Elements $u\in[e,w^J]^J$ are characterized by $u(1)\leq n-1$ and $u(n)\geq2$ with $u(2)<\cdots<u(n{-}1)$. We are now able to count the rank sizes of $[e,w^J]^J$ to be $1,2,3,\ldots,n-4,n-3,n-2,n-1,n-3,n-4,\ldots,2,1$.
Thus, $h(L^J(w^J))=n-3$ and $h(w)=\min(h(L^J(w^J)),h(L(w_J)))=\min(n-3,\infty)=n-3$.
\end{proof}

For an occurrence of a $3412$ in $w$ at indices $a<b<c<d$ with $w(c)<w(d)<w(a)<w(b)$ its \emph{content} is $1+\left|\{i\:|\: b<i<c, w(d)<w(i)<w(a)\}\right|$. Let $\mcontent(w)$ be the minimum content of a $3412$ pattern in $w$.
\begin{lemma}
For $w\in\S_n$ that contains $3412$, $\mh(w)=\mcontent(w)$.
\end{lemma}

One advantage of working with content instead of height is that we evidently have $\mcontent(w)=\mcontent(w^{-1})$.
\begin{lemma}\label{lem:typeA-3412-upper}
Suppose that $w\in \S_n$ avoids $4231$ and contains $3412$. Then $h(w)\leq \mh(w)$. 
\end{lemma}
\begin{proof}
We use induction on $n$. The statement is true when $n=4$, where $h(3412)=\mh(3412)=1$. For a general $n$ and $w\in\S_n$, let $k=\mh(w)=\mcontent(w)$. For $J=\{2,3,\ldots,n-1\}$, if $w_J$ has $\mcontent(w_J)=k$, then we are done by the induction hypothesis and Theorem~\ref{thm:h-increases-in-parabolic} which says $h(w)\leq h(w_J)\leq \mcontent(w_J)=k$. We can thus assume without loss of generality that the index $1$ appears in all $3412$'s of $w$ with content $k$. Similarly, by considering $J=\{1,2,\ldots,n-2\}$, we can also assume that the index $n$ appears in all $3412$'s of $w$ with content $k$. As $h(w)=h(w^{-1})$, with the same argument on $w^{-1}$, we can reduce to the case that $w$ contains a unique $3412$ of content $k$ on indices $1<w^{-1}(n)<w^{-1}(1)<n$ (see Figure~\ref{fig:3412-upper-bound}).
\begin{figure}[h!]
\centering
\begin{tikzpicture}[scale=0.8]
\draw[step=1.0] (0,0) grid (3,3);
\node at (0,2) {$\bullet$};
\node at (1,3) {$\bullet$};
\node at (2,0) {$\bullet$};
\node at (3,1) {$\bullet$};
\node at (0.5,0.5) {$A$};
\node at (1.5,1.5) {$B$};
\node at (2.5,2.5) {$C$};
\node at (0.5,1.5) {$\emptyset$};
\node at (0.5,2.5) {$\emptyset$};
\node at (1.5,0.5) {$\emptyset$};
\node at (1.5,2.5) {$\emptyset$};
\node at (2.5,0.5) {$\emptyset$};
\node at (2.5,1.5) {$\emptyset$};
\end{tikzpicture}
\caption{The permutation diagram for $w$ with an occurrence of $3412$ on the boundary. We draw permutation diagrams by putting $\bullet$'s at Cartesian coordinates $(i,w(i))$.}
\label{fig:3412-upper-bound}
\end{figure}
As we assume that $w_J$ does not contain a $3412$ of content $k$, there does not exist $i$ such that $1<i<w^{-1}(n)$ with $w(i)>w(n)$. By symmetry, we know six of the regions in Figure~\ref{fig:3412-upper-bound} are empty as shown, and label the other three regions as $A,B,C$. By definition, $|B|=k-1$. If $k=1$, then $h(w)=1$ by Proposition~\ref{prop:h-equals-1}. If $k>1$, $B$ is not empty; since $w$ avoids $4231$, $A$ and $C$ must be empty. Thus $w$ is exactly the permutation in Lemma~\ref{lem:typeA-extremal-case}, which gives $h(w)=n-3=k$. 
\end{proof}

\subsection{Extension to Type $D$}

\begin{prop}
\label{prop:type-D-4231-upper-bound}
If $w \in \D_n$ contains $4231$, then $h(w) \leq 2$.
\end{prop}
\begin{proof}[Proof idea]
We adapt the strategy for Proposition~\ref{prop:h-equals-1} to show that for most occurrences of $4231$, we in fact have $h(w)=1$. The few remaining cases are analyzed separately. 
\end{proof}

\begin{defin}
Define the \emph{magnitude} $\mg(w)$ as the smallest $b>0$ such that $w$ has an occurrence of $\pm 1 \bar{3} \bar{2}$ with values $a \bar{c} \bar{b}$.
\end{defin}

\begin{prop}
\label{prop:132-bound}
Suppose $w \in \D_n$ contains $\pm 1 \bar{3} \bar{2}$ and avoids $4231$, then $h(w) \leq \mg(w)-1$.
\end{prop}

\begin{prop}
\label{prop:type-D-avoids-all-but-3412}
Let $W=\D_n$ for $n \geq 5$, let $J=S \setminus \{1\}, J'=S \setminus \{0\}, K=S \setminus \{n-1\}$, and suppose $w \in \D_n$ is singular, but satisfies:
\begin{itemize}
    \item[(i)] $w$ avoids $4231, \pm 1 \bar{3} \bar{2}, \pm 1 2 \bar{3}, \pm 1 4 \bar{3} 2,$ and neither $w$ nor $\varepsilon_D(w)$ contains any occurrences of $3412$ of height one,
    \item[(ii)] $w_J,w_{J'},w_K,\prescript{}{J}{w},\prescript{}{J'}{w},\prescript{}{K}{w}$ are smooth.
\end{itemize}
Then $w=u \coloneqq [n, 2, \bar{3}, \bar{4}, \ldots, \overline{n{-}1}, \pm 1]$ or $w=\varepsilon_D(u)$.
\end{prop}

We are now ready to complete the proof of Theorem~\ref{thm:simply-laced-upper-bound}, resolving Conjecture~\ref{conj:bp-conjecture}.

\begin{proof}[Proof of Theorem~\ref{thm:simply-laced-upper-bound}]   
First suppose $G=\SL_{r+1}$, and let $w \in W(A_r)=\S_{r+1}$ such that $X_w$ is singular. By Theorem~\ref{thm:bp-smoothness}, $w$ contains $4231$ or $3412$. If $w$ contains $4231$, then $h(w)=1$ by Proposition~\ref{prop:h-equals-1}. Otherwise $w$ avoids $4231$ and contains $3412$, so $h(w) \leq \mh(w)$ by Lemma~\ref{lem:typeA-3412-upper}. It is clear by definition that $\mh(w) \leq r-2$ for any $w$, so we are done.

Now suppose $G=\SO_{2r}$ for $r \geq 5$, and let $w \in W(D_r)=\D_r$. Suppose by induction that the claim is true for $G=\SO_{2r'}$ for $r' < r$ (the base case $r'=4$ is covered by the computations in \cite{Billey-Postnikov}). If $w$ contains $4231$, then $h(w) \leq 2 \leq r-2$ by Proposition~\ref{prop:type-D-4231-upper-bound}, so we may assume that $w$ avoids $4231$. Then by Proposition~\ref{prop:132-bound}, if $w$ contains $\pm 1 \bar{3} \bar{2}$ we have $h(w) \leq \mg(w) \leq r-2$. If $w$ contains any of the patterns from Proposition~\ref{prop:h-equals-1}, then $h(w)=1 \leq r-2$. Let $J=S \setminus \{2\}, J'=S \setminus \{0\}, K=S \setminus \{r-1\}$; if any of $w_J,w_{J'},w_K,\prescript{}{J}{w},\prescript{}{J'}{w},\prescript{}{K}{w}$ is singular, then by the type $A$ result, or by the induction hypothesis, we have $h(w) \leq r-3$. Finally, if $w$ does not fall into any of the above cases, then $w$ satisfies the hypotheses (i) and (ii) of Proposition~\ref{prop:type-D-avoids-all-but-3412}, so $w=u \coloneqq [r, 2, \bar{3}, \bar{4}, \ldots, \overline{r{-}1}, \pm 1]$ or $w=\varepsilon_D(u)$.

We will now compute $h(u)=h(\varepsilon_D(u))$; suppose for convenience that $r$ is even, the other case being exactly analogous. Let $I=\{1,2\ldots,r-2\}$, then we have $u_I=w_0(I)$ is the longest element of $\S_{r-1}$, so $h(u_I)=\infty$. Thus we need to compute $h(L^I(u^I))$ with $u^I=[\overline{r{-}1}, \ldots, \bar{4},\bar{3},2,r,\bar{1}]$. Notice $\ell(u^I)=N \coloneqq \frac{1}{2}(r^2-3r+4)$ with reduced word:
\[
s_0(s_2s_0)(s_3s_2s_1) \cdots (s_{r-4}s_{r-5}\cdots s_3s_2s_0)(s_{r-3}\cdots s_3s_2s_1)(s_{r-2}\cdots s_3s_2s_0)s_{r-1}.
\]

We claim that $L^I(u^I)=1+2q+3q^2+ \cdots + aq^{N-2}+2q^{N-1}+q^N$, with $a \geq 4$, so that $h(u)=h(L^I(u^I))=2 < r-2$. Indeed, the elements of length one in $[e,u^I]^I$ are $\{s_0, s_{r-1}\}$, the elements of length two are $\{s_0s_{r-1}, s_2s_0, s_{r-2}s_{r-1}\}$, and the elements of length $N-1$ are $\{s_0u^I, s_2u^I\}$. Consider the four elements $z_1=s_0s_2 u^I, z_2=s_2s_0u^I, z_3=s_0u^Is_{r-1}, z_4=s_3s_2u^I$. It is easy to check for $i=1,2,3,4$ that $\ell(z_i)=N-2$, that $z_i \leq u^I$, and that $z_i \in W^I$; thus $a \geq 4$ as desired.
\end{proof}


\section{Exact formula when $G=\SL_n$}
\label{sec:lower-bound}
For $w\in\S_n$, we have proved the upper bound in Theorem~\ref{thm:type-A-formula} in Section~\ref{sub:typeA-upper-bound}. The lower bound follows from Lemma~\ref{lem:typeA-3412-lower} below.

\begin{lemma}\label{lem:typeA-3412-lower}
Suppose that $w\in\S_n$ avoids $4231$ and contains $3412$. Then $h(w)\geq\mh(w)$.
\end{lemma}
\begin{proof}[Proof idea]
This is an inductive argument using a diagram analysis, analogous to but more involved than the proof of Lemma~\ref{lem:typeA-3412-upper}. The relevant diagram is shown in Figure~\ref{fig:3412-lower-bound}.

\begin{figure}[h]
\centering
\begin{tikzpicture}[scale=0.8]
\draw(0,6)--(0,0)--(6,0);
\draw(3,0)--(3,6);
\draw(0,3)--(6,3);
\node at (0,3) {$\bullet$};
\node at (3,0) {$\bullet$};
\draw[dashed] (1,5.2)--(1,1)--(5.2,1);
\node at (1,5) {$\bullet$};
\node at (2,5.2) {$(c,w(c))$};
\node at (4,1) {$\bullet$};
\node at (5,1.4) {$(b,w(b))$};
\node at (0.8,2.7) {$\bullet$};
\node at (1.3,2.3) {$\bullet$};
\node at (1.8,1.8) {$\bullet$};
\node at (2.3,1.3) {$\bullet$};
\node at (2.7,0.6) {$\bullet$};
\node at (0.4,0.4) {$A$};
\node at (5.6,0.4) {$B$};
\node at (0.4,5.6) {$C$};
\node at (0.5,4.2) {$\bullet$};
\node at (2,4) {$\emptyset$};
\node at (4,2.3) {$\emptyset$};
\node at (5,0.2) {$\bullet$};
\node at (5.2,3.5) {$\bullet$};
\node at (5.5,5.5) {$\bullet$};
\node at (4.5,5.7) {$\bullet$};
\node at (-1,3) {$(1,w(1))$};
\node[below] at (3,0) {$(w^{-1}(1),1)$};
\node at (2.5,2.5) {$D$};
\end{tikzpicture}
\caption{The permutation diagram of $w$ used in the proof of Lemma~\ref{lem:typeA-3412-lower}.}
\label{fig:3412-lower-bound}
\end{figure}
\end{proof}

\acknowledgements{We are grateful for our very fruitful conversations with Alexander Woo and Sara Billey.}

%% 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}
