<figure><img src="image_1.png" /></figure>

HAL
open science

Permutations with Kazhdan-Lusztig polynomial

$$P_{\_id}, w(q) = 1 + q^h$$

Alexander Woo

► To cite this version:

Alexander Woo. Permutations with Kazhdan-Lusztig polynomial $P_{\_id}, w(q) = 1 + q^h$. 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), 2009, Hagenberg, Austria. pp.893-902, 10.46298/dmtcs.2705. hal-01185397

HAL Id: hal-01185397

https://inria.hal.science/hal-01185397

Submitted on 20 Aug 2015

**HAL** is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire **HAL**, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Permutations with Kazhdan-Lusztig polynomial $P_{id,w}(q) = 1 + q^h$

Alexander Woo†

Mathematics, Statistics, and Computer Science, Saint Olaf College, 1520 Saint Olaf Ave., Northfield, MN 55057

**Abstract.** Using resolutions of singularities introduced by Cortez and a method for calculating Kazhdan-Lusztig polynomials due to Polo, we prove the conjecture of Billey and Braden characterizing permutations $w$ with Kazhdan-Lusztig polynomial $P_{id,w}(q) = 1 + q^h$ for some $h$.

**Résumé.** On démontre la conjecture de Billey et Braden sur les permutations $w$ pour lesquelles le polynôme de Kazhdan-Lusztig $P_{id,w}(q) = 1 + q^h$ pour un entier $h$. On emploie une résolution des singularités présentées par Cortez et une méthode de Polo pour calculer ces polynômes.

**Keywords:** Kazhdan-Lusztig polynomials, Schubert varieties

# 1 Introduction

The results mentioned in this extended abstract have been published in [33] along with most of the introductory material. We explain here the alternative approach mentioned in [33, Remark 4.7]. This approach recasts some of the geometry into combinatorial language, but the details in the proofs of the lemmas will be essentially the same.

Kazhdan-Lusztig polynomials are polynomials $P_{u,w}(q)$ in one variable associated to each pair of elements $u$ and $w$ in the symmetric group $S_n$ (or more generally in any Coxeter group). They have an elementary definition in terms of the Hecke algebra [24, 21, 9] and numerous applications in representation theory, most notably in [24, 1, 13], and the geometry of homogeneous spaces [25, 17]. While their definition makes it fairly easy to compute any particular Kazhdan-Lusztig polynomial, on the whole they are poorly understood. General closed formulas are known [5, 10], but they are fairly complicated; furthermore, although Kazhdan-Lusztig polynomials are known to be positive (for $S_n$ and other Weyl groups), these formulas have negative signs. For $S_n$, positive formulas are known only for 3412 avoiding permutations [26, 27], 321-hexagon avoiding permutations [7], and some isolated cases related to the generic singularities of Schubert varieties [8, 29, 16, 32].

One important interpretation of Kazhdan-Lusztig polynomials is as local intersection homology Poincaré polynomials for Schubert varieties. This interpretation, originally established by Kazhdan and

<footnote>†AW gratefully acknowledges support from NSF VIGRE grant DMS-0135345.</footnote>
Lusztig [25], shows, in an entirely non-constructive manner, that Kazhdan-Lusztig polynomials have non-negative integer coefficients and constant term 1. Furthermore, as shown by Deodhar [17], $P_{id,w}(q) = 1$ (for $S_n$) if and only if the Schubert variety $X_w$ is smooth, and, more generally, $P_{u,w}(q) = 1$ if and only if $X_w$ is smooth over the Schubert cell $X_w^\circ$.

The purpose of this paper is to prove the following theorem.

**Theorem 1.1** Suppose the singular locus of $X_w$ has exactly one irreducible component, and $w$ avoids the patterns 653421, 632541, 463152, 526413, 546213, and 465132. Then $P_{id,w}(1) = 2$.

More precisely, when the hypotheses are satisfied, $P_{id,w}(q) = 1 + q^h$ where $h$ is the minimum height of a 3412 embedding, with $h = 1$ if no such embedding exists.

Here, a 3412 embedding is a sequence of indices $i_1 < i_2 < i_3 < i_4$ such that $w(i_3) < w(i_4) < w(i_1) < w(i_2)$, and its height is $w(i_1) - w(i_4)$. Given the first part of the theorem, the second part can be immediately deduced from the unimodality of Kazhdan-Lusztig polynomials [22, 12] and the calculation of the Kazhdan-Lusztig polynomial at the unique generic singularity [8, 29, 16]. Indeed, unimodality and this calculation imply the following corollary.

**Corollary 1.2** Suppose $w$ satisfies the hypotheses of Theorem 1.1. Let $X_v$ be the singular locus of $X_w$. Then $P_{u,w}(q) = 1 + q^h$ (with $h$ as in Theorem 1.1) if $u \le v$ in Bruhat order, and $P_{u,w}(q) = 1$ otherwise.

The permutation $v$ and the singular locus in general has a combinatorial description given in Theorem 2.1, which was originally proved independently in [8, 16, 23, 28]. This description is used in our proof. Furthermore, Billey and Weed recently found a combinatorial version [33, Theorem A.1] of Theorem 1.1, replacing the geometric condition that $X_w$ has one irreducible component with sixty additional patterns.

Theorem 1.1 was conjectured by Billey and Braden [6]. They claim to have a proof for the converse in their paper. An outline of their proof is as follows. If $P_{id,w}(1) = 1$ then $X_w$ is nonsingular [17]. The methods for calculating Kazhdan-Lusztig polynomials due to Braden and MacPherson [12] show that $P_{id,w}(1) \le 2$ implies that the singular locus of $X_w$ has at most one component. That $P_{id,w}(1) \le 2$ implies the pattern avoidance conditions follows from [6, Thm. 1] and the computation of Kazhdan-Lusztig polynomials for the six pattern permutations.

**Example 1.3** To illustrate the theorem, $P_{id,643521}(q) = 1+q$ (as 643521 has no 3412 embedding), $P_{id,254613}(q) = 1+q$ (as $h=1$), $P_{id,2657413}(q) = 1+q^2$, and $P_{id,564312}(q) = 1+q^3$. On the other hand, $P_{id,34512}(q) = 1+2q$ (as the singular locus of $X_{34512}$ has three irreducible components), and $P_{id,2574163}(q) = 1+q+q^2$ (as 2574163 does not avoid 463152).

The proof of Theorem 1.1 outlined in this abstract requires two cases. When $w$ has no 3412 embedding, we analyze the algorithm of Lascoux [26] for calculating Kazhdan-Lusztig polynomials for such $w$. For $w$ containing a 3412 embedding, we use a resolution of singularities for Schubert varieties introduced by Cortez [16]. In general, the maps introduced by Cortez [16] do not necessarily come from a smooth variety, but they are actual resolutions for $w$ satisfying the conditions of Theorem 1.1. A Bialynicki-Birula decomposition [3, 4, 14] of the resolution gives us a combinatorial formula purely in terms of permutations for the Poincaré polynomials for the fibers of the resolution. Polo [30] gave a combinatorial interpretation of the Decomposition Theorem [2] which allows us to then calculate Kazhdan-Lusztig polynomials from these Poincaré polynomials. This calculation is in the spirit of Deodhar’s approach [18] to calculating
Kazhdan-Lusztig polynomials $P_{u,w}(q)$ from a reduced expression for $w$, but our calculation is simpler in this particular case.

Corollary 1.2 suggests the problem of describing all pairs $u$ and $w$ for which $P_{u,w}(1) = 2$. It seems possible to extend the methods of this paper to characterize such pairs; presumably $X_u$ would need to lie in no more than one component of the singular locus of $X_w$, and $[u, w]$ would need to avoid certain intervals (see Section 2.3). Our methods in theory extend to more permutations, but any further extension to characterize $w$ for which $P_{id,w}(1) = 3$ is likely to be extremely combinatorially intricate. An extension to other Weyl groups would also be interesting, not only for its intrinsic value, but because methods for proving such a result may suggest methods for proving any (currently nonexistent) conjecture combinatorially describing the singular loci of Schubert varieties for these other Weyl groups.

I wish to thank Eric Babson for encouraging conversations and Sara Billey for helpful comments and suggestions on earlier drafts. I used Greg Warrington's software [31] for computing Kazhdan-Lusztig polynomials in explorations leading to this work.

# 2 Preliminaries

## 2.1 The symmetric group and Bruhat order

We begin by setting notation and basic definitions. We let $S_n$ denote the symmetric group on $n$ letters. We let $s_i \in S_n$ denote the adjacent transposition which switches $i$ and $i + 1$; the elements $s_i$ for $i = 1, \dots, n - 1$ generate $S_n$. Given an element $w \in S_n$, its **length**, denoted $\ell(w)$, is the minimal number of generators such that $w$ can be written as $w = s_{i_1}s_{i_2}\cdots s_{i_\ell}$. An **inversion** in $w$ is a pair of indices $i < j$ such that $w(i) > w(j)$. The length of a permutation $w$ is equal to the number of inversions it has.

Unless otherwise stated, permutations are written in one-line notation, so that $w = 3142$ is the permutation such that $w(1) = 3$, $w(2) = 1$, $w(3) = 4$, and $w(4) = 2$.

Given a permutation $w \in S_n$, the **graph** of $w$ is the set of points $(i, w(i))$ for $i \in \{1, \dots, n\}$. We will draw graphs according to the Cartesian convention, so that $(0, 0)$ is at the bottom left and $(n, 0)$ the bottom right.

The **rank function** $r_w$ is defined by

$$r_w(p, q) = \#\{i \mid 1 \le i \le p, 1 \le w(i) \le q\}$$

for any $p, q \in \{1, \dots, n\}$. We can visualize $r_w(p, q)$ as the number of points of the graph of $w$ in the rectangle defined by $(1, 1)$ and $(p, q)$. There is a partial order on $S_n$, known as **Bruhat order**, which can be defined as the reverse of the natural partial order on the rank function; explicitly, $u \le w$ if $r_u(p, q) \ge r_w(p, q)$ for all $p, q \in \{1, \dots, n\}$. The Bruhat order and the length function are closely related. If $u < w$, then $\ell(u) < \ell(w)$; moreover, if $u < w$ and $j = \ell(w) - \ell(u)$, then there exist (not necessarily adjacent) transpositions $t_1, \dots, t_j$ such that $u = t_j \cdots t_1 w$ and $\ell(t_{i+1} \cdots t_1 w) = \ell(t_i \cdots t_1 w) - 1$ for all $i, 1 \le i < j$. For a thorough exposition covering various definitions and properties of Bruhat order see [9, Chap. 2].

## 2.2 Schubert varieties

Now we briefly define Schubert varieties. A **(complete flag)** $F_\bullet$ in $\mathbb{C}^n$ is a sequence of subspaces $\{0\} \subseteq F_1 \subset F_2 \subset \cdots \subset F_{n-1} \subset F_n = \mathbb{C}^n$, with $\dim F_i = i$. As a set, the **flag variety** $\mathcal{F}_n$ has one point for every flag in $\mathbb{C}^n$. The flag variety $\mathcal{F}_n$ has an algebraic and geometric structure as $GL(n)/B$, where $B$ is
the group of invertible upper triangular matrices, as follows. Given a matrix $g \in GL(n)$, we can associate to it the flag $F_\bullet$ with $F_i$ being the span of the first $i$ columns of $g$. Two matrices $g$ and $g'$ represent the same flag if and only if $g' = gb$ for some $b \in B$, so complete flags are in one-to-one correspondence with left $B$-cosets of $GL(n)$.

Fix an ordered basis $e_1, \dots, e_n$ for $\mathbb{C}^n$, and let $E_\bullet$ be the flag where $E_i$ is the span of the first $i$ basis vectors. Given a permutation $w \in S_n$, the **Schubert cell** associated to $w$, denoted $X_w^\circ$, is the subset of $\mathcal{F}_n$ corresponding to the set of flags

$$ \{F_\bullet \mid \dim(F_p \cap E_q) = r_w(p, q) \ \forall p, q\}. \qquad (1) $$

The conditions in (1) are called **rank conditions**. The **Schubert variety** $X_w$ is the closure of the Schubert cell $X_w^\circ$; its points correspond to the flags

$$ \{F_\bullet \mid \dim(F_p \cap E_q) \geq r_w(p, q) \ \forall p, q\}. $$

Bruhat order has an alternative definition in terms of Schubert varieties; the Schubert variety $X_w$ is a union of Schubert cells, and $u \le w$ if and only if $X_u^\circ \subset X_w$. In each Schubert cell $X_w^\circ$ there is a **Schubert point** $e_w$, which is the point associated to the permutation matrix $w$; in terms of flags, the flag $E_\bullet^{(w)}$ corresponding to $e_w$ is defined by $E_\bullet^{(w)} = \mathbb{C}\{e_{w(1)}, \dots, e_{w(i)}\}$. The Schubert cell $X_w^\circ$ is the orbit of $e_w$ under the left action of the group $B$.

Many of the rank conditions in (1) are actually redundant. Fulton [20] showed that for any $w$ there is a minimal set, called the **coessential set**$^{(i)}$, of rank conditions which suffice to define $X_w$. To be precise, the coessential set is given by

$$ \mathrm{Coess}(w) = \{(p, q) \mid w(p) \le q < w(p+1), w^{-1}(q) \le p < w^{-1}(q+1)\}, $$

and a flag $F_\bullet$ corresponds to a point in $X_w$ if and only if $\dim(F_p \cap E_q) \ge r_w(p, q)$ for all $(p, q) \in \mathrm{Coess}(w)$.

While we have distinguished between points in flag and Schubert varieties and the flags they correspond to here, we will freely ignore this distinction in the rest of the paper.

## 2.3 Pattern avoidance and interval pattern avoidance

Let $v \in S_m$ and $w \in S_n$, with $m \le n$. A **(pattern) embedding** of $v$ into $w$ is a set of indices $i_1 < \dots < i_m$ such that the entries of $w$ in those indices are in the same relative order as the entries of $v$. Stated precisely, this means that, for all $j, k \in \{1, \dots, m\}, v(j) < v(k)$ if and only if $w(i_j) < w(i_k)$. A permutation $w$ is said to **avoid** $v$ if there are no embeddings of $v$ into $w$.

Now let $[x, v] \subseteq S_m$ and $[u, w] \subseteq S_n$ be two intervals in Bruhat order. An **(interval) (pattern) embedding** of $[x, v]$ into $[u, w]$ is a simultaneous pattern embedding of $x$ into $u$ and $v$ into $w$ using the same set of indices $i_1 < \dots < i_m$, with the additional property that $[x, v]$ and $[u, w]$ are isomorphic as posets. For the last condition, it suffices to check that $\ell(v) - \ell(x) = \ell(w) - \ell(u)$ [34, Lemma 2.1].

Note that given the embedding indices $i_1 < \dots < i_m$, any three of the four permutations $x, v, u$, and $w$ determine the fourth. Therefore, for convenience, we sometimes drop $u$ from the terminology and discuss embeddings of $[x, v]$ in $w$, with $u$ implied. We also say that $w$ **(interval) (pattern) avoids** $[x, v]$ if there are no interval pattern embeddings of $[x, v]$ into $[u, w]$ for any $u \le w$.

<footnote>$^{(i)}$ Fulton [20] indexes Schubert varieties in a manner reversed from our indexing as it is more convenient in his context. As a result, his Schubert varieties are defined by inequalities in the opposite direction, and he defines the **essential set** with inequalities reversed from ours. Our conventions also differ from those of Cortez [15] in replacing her $p-1$ with $p$.</footnote>
## 2.4 Singular locus of Schubert varieties

Now we describe combinatorially the singular loci of Schubert varieties. The results of this section are due independently to Billey and Warrington [8], Cortez [15, 16], Kassel, Lascoux, and Reutenauer [23], and Manivel [28].

Stated in terms of interval pattern embeddings as in [34, Thm. 6.1], the theorem is as follows. Permutations are given in 1-line notation. We use the convention that the segment “j, ..., i” means j, j-1, j-2, ..., i+1, i. In particular, if j < i then the segment is empty.

**Theorem 2.1** The Schubert variety $X_w$ is singular at $e_{u'}$ if and only if there exists $u$ with $u' \le u < w$ such that one of the following (infinitely many) intervals embeds in $[u, w]$:

I: $[(y+1), z, \dots, 1, (y+z+2), \dots, (y+2); (y+z+2), (y+1), y, \dots, 2, (y+z+1), \dots, (y+2), 1]$ for some integers $y, z > 0$.

IIA: $[(y+1), \dots, 1, (y+3), (y+2), (y+z+4), \dots, (y+4); (y+3), (y+1), \dots, 2, (y+z+4), 1, (y+z+3), \dots, (y+4), (y+2)]$ for some integers $y, z \ge 0$.

IIB: $[1, (y+3), \dots, 2, (y+4); (y+3), (y+4), (y+2), \dots, 3, 1, 2]$ for some integer $y > 1$.

Equivalently, the irreducible components of the singular locus of $X_w$ are the subvarieties $X_u$ for which one of these intervals embeds in $[u, w]$.

## 2.5 Bialynicki-Birula decompositions

Given a $\mathbb{C}^*$ action on a smooth complex projective variety $Y$ with finitely many fixed points, Bialynicki-Birula [3, 4] defined a decomposition of $Y$ into cells, which he showed are each isomorphic to $\mathbb{C}^n$ for some $n$. More precisely, given a $\mathbb{C}^*$-fixed point $p$, we can associate the cell

$$Y_p^\circ := \{y \in Y \mid \lim_{t \to 0} t \cdot y = p\}.$$

In the case where $Y$ is the flag variety, there is a $\mathbb{C}^*$ action whose fixed points are the Schubert points and whose resulting cells are the Schubert cells. Therefore, even though Schubert varieties are not smooth, they have a Bialynicki-Birula decomposition.

Given a $\mathbb{C}^*$-equivariant resolution of singularities $\pi : Z \to X_w$, we also have a Bialynicki-Birula decomposition of $Z$. Furthermore, if we let $P_u$ denote the set of $\mathbb{C}^*$-fixed points of $Z$ in $\pi^{-1}(e_u)$, we have a cell decomposition

$$\pi^{-1}(X_u^\circ) = \bigsqcup_{p \in P_u} Y_p^\circ,$$

and a decomposition of the fiber $\pi^{-1}(e_u)$ into cells $\pi^{-1}(e_u) \cap Y_p^\circ$ which are respectively of dimensions $\dim(Y_p^\circ) - \dim(X_u^\circ)$.

Therefore, the homology Poincaré polynomial for $\pi^{-1}(e_u)$ is

$$H_{u,\pi}(q) = \sum_{p \in P_u} q^{\dim(Y_p^\circ) - \ell(u)}.$$

(Technically, the degrees should be doubled, but as we have halved the degrees since all cells will be $(\mathbb{R})$-even-dimensional and this will match the usual degrees for Kazhdan-Lusztig polynomials.)
## 2.6 The Decomposition Theorem

From the homology Poincaré polynomials $H_{u,\pi}$ for a resolution $\pi: Z \to X_w$ we can, following Polo [30], use the Decomposition Theorem [2] to calculate Kazhdan-Lusztig polynomials. More specifically, given such a resolution,

$$H_{u,\pi}(q) = P_{u,w}(q) + \sum_{u \le v < w} q^{\ell(w) - \ell(v)} E_v(q) P_{u,v}(q).$$

In this statement, $E_v(q)$ are Laurent polynomials in $q^{\frac{1}{2}}$ to be determined later; the Laurent polynomials $E_v(q)$ depend only on $v$ and $\pi$ and not on $u$, have with positive integer coefficients, and satisfy the identity $E_v(q) = E_v(q^{-1})$.

One case of the Decomposition Theorem is well-known in the theory of Kazhdan-Lusztig polynomials. When $Z$ is the full Bott-Samelson resolution of $X_w$ constructed from a reduced word decomposition $w = s_{i_1} \cdots s_{i_\ell}$, the fixed points of $Z$ are indexed by the $2^{\ell(w)}$ subwords of this reduced word. One method of indexing leads to $\dim(Y_p^\circ) - \dim(X_u^\circ)$ being Deodhar's defect statistic [18], so that $H_{u,\pi}$ is precisely the sum, taken over subwords of our defining reduced word, of $q$ raised to the number of defects in the subword. Rearranged, the formula above is precisely Deodhar's formula, and $E_v(q)$ represents the inadmissible masks.

Unfortunately the full Bott-Samelson resolution and Deodhar's approach is too difficult to analyze in this case. Instead we use a resolution of singularities due to Cortez [16] and calculate $H_{u,\pi}$ for this resolution $\pi$ and certain crucial permutations $u$. This will give us enough information to calculate $E_v$ for those resolutions and determine $P_{id,w}(q)$ when $w$ satisfies the conditions of Theorem 1.1.

# 3 The covexillary case

A permutation $w$ is **covexillary** if it avoids 3412. Generalizing a formula of Lascoux and Schützenberger in the case where $w$ has only one ascent, Lascoux [26] gave a formula for the Kazhdan-Lusztig polynomials $P_{u,w}(q)$ which applies whenever $w$ is covexillary. This formula proceeds by constructing a rooted tree $T_w$ from $w$ with nonnegative integer labels for the leaves of this tree based on how far $u$ and $w$ are from each other. Given an edge labelling $L$ of a tree by nonnegative integers, let $s(L)$ be the sum of the edge labels. Then Lascoux shows that

$$P_{u,w} = \sum_{L} q^{s(L)},$$

where the sum is over all nondecreasing edge labellings of $T_w$ which are bounded by the labels for the leaves.

A Schubert variety $X_w$ for a covexillary permutation $w$ has one component in its singular locus precisely when the labelling of the rooted tree $T_w$ for $id$ has only one leaf $\lambda$ which is not labeled 0. Furthermore, the following lemmas hold.

**Lemma 3.1** Suppose $w$ avoids 632541. Then no single branch of $T_w$ is two edges long by itself. (In other words, every leaf is adjacent to a internal node with at least two children.)

**Lemma 3.2** Suppose $w$ avoids 653421. Then no leaf of $T_w$ has a label greater than 1.

In consequence, when the singular locus of $X_w$ has one component and $w$ avoids 3412, 632541, and 653421, one must label all the edges of $T_w$ by 0, except for the edge above $\lambda$ which can be labelled 0 or 1. Therefore, $P_{id,w}(q) = 1 + q$.
# 4 The 3412 containing case

In this section we treat the case where $w$ contains a 3412 pattern. We use a resolution of singularities defined by Cortez and the machinery mentioned above of a Bialynicki-Birula decomposition followed by an application of the Decomposition Theorem.

## 4.1 Cortez's resolution

We begin with some definitions necessary for defining a variety $Z$ and a $\mathbb{C}^*$-equivariant map $\pi : Z \to X_w$ which we will show is a resolution of singularities. Our notation and terminology generally follows that of Cortez [16]. Given an embedding $i_1 < i_2 < i_3 < i_4$ of 3412 into $w$, we call $w(i_1) - w(i_4)$ its **height** (hauteur), and $w(i_2) - w(i_3)$ its **amplitude**. Among all embeddings of 3412 in $w$, we take the ones with minimum height, and among embeddings of minimum height, we choose one with minimum amplitude. As we will be continually referring this particular embedding, we denote the indices of this embedding by $a < b < c < d$ and entries of $w$ at these indices by $\alpha = w(a)$, $\beta = w(b)$, $\gamma = w(c)$, and $\delta = w(d)$. We let $h = \alpha - \delta$ be the height of this embedding.

Let $\alpha'$ be the largest number such that $w^{-1}(\alpha') < w^{-1}(\alpha' - 1) < \dots < w^{-1}(\alpha + 1) < w^{-1}(\alpha)$ and $\delta'$ the smallest number such that $w^{-1}(\delta) < w^{-1}(\delta - 1) < \dots < w^{-1}(\delta')$. Also let $a' = w^{-1}(\alpha')$ and $d' = w^{-1}(\delta')$. Now let $\kappa = \delta' + \alpha' - \alpha$, let $I$ denote the set of simple transpositions $\{s_{\delta'}, \dots, s_{\alpha'-1}\}$, and let $J$ be $I \setminus \{s_\kappa\}$. Furthermore, let $v = w_0^J w_0^I w$, where $w_0^J$ and $w_0^I$ denote the longest permutations in the parabolic subgroups of $S_n$ generated by $J$ and $I$ respectively.

**Example 4.1** Suppose $w = 817396254 \in S_9$. Then $a = 3$, $b = 5$, $c = 7$, and $d = 8$, while $\alpha = 7$, $\beta = 9$, $\gamma = 2$, and $\delta = 5$. We also have $h = 2$, $\alpha' = 8$ and $\delta' = 4$. Hence $\kappa = 5$ and $v = 514398276$.

Now consider the variety $Z = P_I \times_{P_J} X_v$. By definition, $Z$ is a quotient of $P_I \times X_v$ under the free action of $P_J$ where $q \cdot (p, x) = (pq^{-1}, q \cdot x)$ for any $q \in P_J$, $p \in P_I$, and $x \in X_v$. We have a map $\pi : Z \to X_w$ defined by $\pi(p, x) = p \cdot x$; note this is well-defined. The map $\pi$ is birational and surjective [16, Proposition 4.4]. However, $Z$ is not smooth in general, as $X_v$ need not be smooth. Nevertheless, we show the following for our case.

**Lemma 4.2** Suppose the singular locus of $X_w$ has only one component and $w$ avoids 463152. Then $Z$ is smooth.

Cortez [16] introduced the variety $Z$ along with several other varieties (constructed by defining $\kappa = \delta' + \alpha' - \alpha + i - 1$ for $i = 1, \dots, h$) to help in describing the singular locus of Schubert varieties$^{(ii)}$. A virtually identical proof would follow from analyzing the resolution given by $i = h$ instead of $i = 1$ as we are doing, but the other choices of $i$ will give maps which are harder to analyze as they have more complicated fibers.

## 4.2 Calculations for $H_{\pi,u}$

We now need to identify the fixed points of $Z$ under the $\mathbb{C}^*$ action, calculate the dimensions of the cells associated with them, and classify them according to the fixed point $e_u$ they map to under $\pi$. The fixed points of $Z$ are precisely $\{(\sigma, e_\tau)\}$, where $\sigma$ is in $W_I$, the parabolic subgroup of $S_n$ generated by $s_k$ for

<footnote>$^{(ii)}$ Cortez's choice of 3412 embedding in [16] is slightly different from ours. For technical reasons she chooses one of minimum amplitude among those satisfying a condition she calls "well-filled" (bien remplie). As she notes, 3412 embeddings of minimum height are automatically "well-filled".</footnote>
$k \in I$ (considered as a subgroup of $GL_n$ in the usual way), and $\tau \le v$ in Bruhat order on $S_n$. Several such pairs $(\sigma, \tau)$ will be in the same $P_J$ orbit, so they will represent the same point in $Z$. We can eliminate this duplication by choosing one $\sigma$ from each left $W_J$ coset. For convenience, we will choose the one which is minimal in Bruhat order; each coset has a unique minimal element since $W_J$ is parabolic. Furthermore, $\pi(\sigma, e_\tau) = e_u$ if and only if $\sigma\tau = u$.

When $u$ is minimal in its right $W_I$ coset, then the dimension of the cell associated to $(\sigma, e_\tau) \in \pi^{-1}(e_u)$ is $\ell(u) + \ell(\sigma)$. When $u$ is not minimal in its right $W_I$ coset, then the dimension of the cell is harder to calculate, but since $\pi$ is $P_I$-equivariant, the fiber of $e_u'$ is the same as the fiber of $e_u$ whenever $u'$ and $u$ are in the same right $W_I$ coset. Therefore, given $u \le w$, let $u'$ denote the minimal element of its right $W_I$ coset. Then

$$H_{\pi,u} = \sum_{(\sigma, \tau)} q^{\ell(\sigma)},$$

where $\sigma \in W_I$ is minimal in its left $W_J$ coset, $\tau \le v$, and $\sigma\tau = u'$.

It would be interesting to give a more direct formula for $H_{\pi,u}$ in general; hopefully this formula would mimic that of Deodhar for the full Bott-Samelson resolution by placing some defect-like statistic in the exponent of $q$.

Now we have the following combinatorial lemmas.

**Lemma 4.3** Suppose that the singular locus of $X_w$ has only one component and $w$ avoids 546213. If $\sigma \in P_I$, $\tau \le v$, and $\sigma\tau = id$, then $\{1, \dots, \kappa - 1\} \subseteq \sigma(\{1, \dots, \kappa\})$.

**Lemma 4.4** Suppose that the singular locus of $X_w$ has only one component and $w$ avoids 465132. If $\sigma \in P_I$, $\tau \le v$, and $\sigma\tau = id$, then $\sigma(\{1, \dots, \kappa\}) \subseteq \{1, \dots, \kappa + h\}$.

In the case where $h = 1$, this shows that $H_{id,\pi}(q) = 1 + q$, since the only admissible $\sigma$ are the identity and the adjacent transposition $s_\kappa$. This shows that $P_{id,w}(q) = 1 + q$. Otherwise, $H_{id,\pi}(q) = 1 + q + \dots + q^h$. In this case, let $\xi \in S_n$ be the cycle $(\gamma, \delta + 1, \delta + 2, \dots, \alpha = \delta + h)$, and let $\rho = \xi w$. We then have the following lemma.

**Lemma 4.5** Assume that the singular locus of $X_w$ has only one component, that $h > 1$, and that $w$ avoids 526413. Then $H_{\pi,u}(1) > 1$ only if $u \le \rho$, $\ell(w) - \ell(\rho) = h$, and $H_{\pi,\rho} = 1 + q + \dots + q^{h-1}$.

From these lemmas it follows by a calculation similar to one by Polo [30, Proposition 2.4(b)] that, in the case $h > 1$,

$$E_u(q) = 0 \text{ for } u \neq \rho, \\ E_\rho(q) = q^{1-\frac{h}{2}} + \dots + q^{\frac{h}{2}-1},$$

and therefore

$$P_{id,w} = 1 + q^h.$$

## References

[1] A. Beilinson and J. Bernstein, *Localisation de g-modules*, C. R. Acad. Sci. Paris Sér. I Math. **292** (1981), 15–18.

[2] A. Beilinson, J. Bernstein, and P. Deligne, *Faisceaux pervers*, in *Analyse et topologie sur les espaces singuliers (I)*, Astérisque **100** (1982), 3–171.
[3] A. Białynicki-Birula, Some theorems on actions of algebraic groups, Ann. of Math. (2), **98** (1973), 480–497.

[4] A. Białynicki-Birula, On fixed points of torus actions on projective varieties, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. **22** (1974), 1097–1101.

[5] L. Billera and F. Brenti, Quasisymmetric functions and Kazhdan-Lusztig polynomials, arXiv:0710.3965

[6] S. Billey and T. Braden, Lower bounds for Kazhdan-Lusztig polynomials from patterns, Transform. Groups **8** (2003), 321–332.

[7] S. Billey and G. Warrington, Kazhdan-Lusztig polynomials for 321-hexagon-avoiding permutations, J. Algebraic Combin. **13** (2001), 111–136.

[8] S. Billey and G. Warrington, Maximal singular loci of Schubert varieties on SL(n)/B, Trans. Amer. Math. Soc. **355** (2003), 3915–3945.

[9] A. Björner and F. Brenti, Combinatorics of Coxeter groups, Graduate Texts in Mathematics **231**, Springer-Verlag, New York-Heidelberg, 2005.

[10] F. Brenti, Lattics paths and Kazhdan-Lusztig polynomials, J. Amer. Math. Soc. **11** (1998), 229–259.

[11] R. Bott and H. Samelson, Applications of the theory of Morse to symmetric spaces, Amer. J. Math. **80** (1958), 964–1029.

[12] T. Braden and R. Macpherson, From moment graphs to intersection cohomology, Math. Ann. **321** (2001), 533–551.

[13] J.-L. Brylinski and M. Kashiwara, Kazhdan-Lusztig conjecture and holonomic systems, Invent. Math. **64** (1981), 387–410.

[14] J. Carrell, Torus actions and cohomology, in Algebraic quotients. Torus actions and cohomology. The adjoint representation and the adjoint action, Encyclopaedia Math. Sci. **131**, Springer-Verlag, Berlin (2002), 83–158.

[15] A. Cortez, Singularités génériques des varieétés de Schubert covexillaires, Ann. Inst. Fourier (Grenoble) **51** (2001), 375–393.

[16] A. Cortez, Singularités génériques et quasi-résolutions des variétés de Schubert pour le groupe linéaire, Adv. Math. **178** (2003), 396–445.

[17] V. Deodhar, Local Poincaré duality and nonsingularity of Schubert varieties, Comm. Algebra **13** (1985), 1379–1388.

[18] V. Deodhar, A combinatorial setting for questions in Kazhdan-Lusztig theory, Geom. Dedicata **36** (1990), 95–119.

[19] M. Demazure, Désingularisation des variétés de Schubert généralisées, Ann. Sci. École Norm. Sup. (4), **7** (1974), 53–88.
[20] W. Fulton, *Flags, Schubert polynomials, degeneracy loci, and determinantal formulas*, Duke Math. J. **65** (1992), 381–420.

[21] J. Humphreys, *Reflection groups and Coxeter groups*, Cambridge Studies in Advanced Mathematics **29**, Cambridge University Press, Cambridge, 1990.

[22] R. Irving, *The socle filtration of a Verma module*, Ann. Sci. Ecole Norm. Sup. ser. 4 **21** (1988), 47–65.

[23] C. Kassel, A. Lascoux and C. Reutenauer, *The singular locus of a Schubert variety*, J. Algebra **269** (2003), 74–108.

[24] D. Kazhdan and G. Lusztig, *Representations of Coxeter Groups and Hecke Algebras*, Invent. Math. **53** (1979), 165–184.

[25] D. Kazhdan and G. Lusztig, *Schubert varieties and Poincaré duality*, in *Geometry of the Laplace operator* (Proc. Sympos. Pure Math., Univ. Hawaii, Honolulu, Hawaii, 1979), Proc. Sympos. Pure Math., **36**, Amer. Math. Soc., Providence, RI (1980), 185–203.

[26] A. Lascoux, *Polynômes de Kazhdan-Lusztig pour les variétés de Schubert vexillaires*, C. R. Acad. Sci. Paris, **321** (1995), 667–670.

[27] A. Lascoux and M.P. Schützenberger, *Polynômes de Kazhdan-Lusztig pour les grassmanniennes*, Astérisque, **87–88** (1981), 249–266.

[28] L. Manivel, *Le lieu singulier des variétés de Schubert*, Internat. Math. Res. Notices **16** (2001), 849–871.

[29] L. Manivel, *Generic singularities of Schubert varieties*, math.AG/0105239.

[30] P. Polo, *Construction of arbitrary Kazhdan-Lusztig polynomials in symmetric groups*, Represent. Theory **3** (1999), 90–104 (electronic).

[31] G. Warrington, *KLPOL* (2002), available at http://www.wfu.edu/~warrings/research/klpol/klpol.html

[32] G. Warrington, *A formula for certain inverse Kazhdan-Lusztig polynomials in $S_n$*, J. Combin. Theory Ser. A **104** (2003), 301–316.

[33] A. Woo, with an appendix by S. Billey and J. Weed, *Permutations with Kazhdan-Lusztig polynomial* $P_{id,w}(q) = 1 + q^h$, The Björner Festschrift, Electron. J. Combin. 16 (2009), no. 2, to appear, arXiv:0809.2374

[34] A. Woo and A. Yong, *Governing singularities of Schubert varieties*, J. Algebra **320** (2008), 495–520.