Coxeter groups and Billey-Postnikov decompositions
Suho Oh Edward Richmond




§ ABSTRACT 
In this chapter, we give an overview of Billey-Postnikov (BP) decompositions which have become an important tool for understanding the geometry and combinatorics of Schubert varieties.  BP decompositions are factorizations of Coxeter group elements with many nice properties in relation to Bruhat partial order.  They have played an important role in the classification and enumeration of smooth Schubert varieties.  They have also been used in the study of inversion hyperplane arrangements and permutation pattern avoidance.  We survey many of these applications.


[
    Lucas A. Polson^1,2, Pedro Esquinas^3, Sara Kurkowska^2,4, Chenguang Li^1,2, Peyman Sheikhzadeh^5 Mehrshad Abbassi^5, Saeed Farzanehfar^5, Seyyede Mirabedian^5, Carlos Uribe^2,3,6, Arman Rahmim^1,2,6
    
School of Physics, Nankai University, Tianjin, 300071, China 

===========================================================================================================================================================================================================








§ INTRODUCTION


    
  * 35 40 pages
    
  * 5 10 pages to intro, BP-decompo
    
  * 10 pages for geometry
    
  * 7 8 pages for hyperplanes
    
  * 4 page self-dual intervals
    
  * Definition of parabolic, decomposition. Polynomial definition then geometric definition. 
    
  * def equiv: prop 4.2 of RS16s
    
    
  * 3 routes of application : root-system pattern avoidance, hyperplanes, geometry
    
    
  * geometry : RS16, then AR17. Follow with subsection? on RS17. 
    
  * subsection for affine BC12, RS18.
    
  * Copy & Paste is not allowed. Statements can be copied.
    
  * Convention for decomp : W^J × W_J
    
  * S ∖ s for deleting a single element
    
  * Prerequisite on Weyl, Coxeter groups, Coxeter group, Root system, flag variety, Schubert variety we can skip.
    
  * 1.5 page overview
    
  * After them 2.8 (TFAE 4) split stellar stuff (move rational smooth stuff there)
    
  * 12321 12 Non BP, 12321 13 BP Example TFAE all 4 check : picture of W^J with corresponding colors







§ INTRODUCTION


Coxeter groups and their combinatorics play a vital role in the study of Lie groups, flag varieties, and Schubert varieties.  Of particular importance are the length function and Bruhat partial order (also called Bruhat-Chevalley order) on a Coxeter group.  Geometrically, the length of an element equals the dimension of the corresponding Schubert variety, and the Bruhat order gives closure relations of Schubert cells in a flag variety.   Let W be a Coxeter group, and for any w∈ W, we define the Poincaré polynomial 

    P_w(q):=∑_u≤ w q^ℓ(w)

where ℓ:W→_≥ 0 denotes the length function and ≤ denotes Bruhat order.  If W is the Weyl group of a complex reductive Lie group, then P_w(q^2) is the topological Poincaré polynomial with respect to singular cohomology of the corresponding Schubert variety X(w).  The central problem we address is to characterize when the polynomial P_w(q) factors in some nice or natural way.  

When W=_n is the permutation group, Gasharov proved in <cit.> that the polynomial P_w(q) is a product of factors of the form (1+q+⋯ +q^r) if and only if w avoids the permutation patterns 3412 and 4231. 
 This is a generalization of the well known result that the Poincaré series on the full permutation group is

    ∑_w∈_n q^ℓ(w)=∏_k=0^n-1(1+q+⋯+q^k).

Chevalley <cit.> and Solomon <cit.> prove that the Poincaré series of any finite Coxeter group has a similar factorization as in Equation (<ref>), so we can ask if there is an analogue of Gasharov's factorization theorem for elements of other groups.  In <cit.>, Lakshmibai and Sandya prove that a permutation w∈_n avoiding the patterns 3412 and 4231 is equivalent to the Schubert variety X(w) being smooth, and hence Gasharov's factorization theorem is a property of “smooth" permutations.  As it turn out, nice Poincaré polynomial factorizations hold for not only smooth permutations, but “smooth" elements of any Coxeter group of finite Lie-type.  We summarize these properties of (rationally) smooth elements in Section <ref>.  Of critical importance to these results is the notion of what is now called a Billey-Postnikov (BP) decomposition.  BP decompositions are certain factorizations of group elements with many nice properties in relation to intervals in Bruhat order.  The name “BP" comes from the paper <cit.> where Billey and Postnikov use these decompositions to give a root-theoretic criterion for the rational smoothness of Schubert varieties.  However, the idea of these decompositions dates back to earlier works such as <cit.> and <cit.>. BP decompositions have had numerous applications and have appeared in the study of fiber bundle structures of Schubert varieties <cit.>, inversion hyperplane arrangements <cit.> and permutation pattern avoidance <cit.>.  The purpose of this chapter is to provide an overview of BP decompositions and their applications.  

We structure this chapter as follows.  In Section <ref>, we review the basic properities of Coxeter groups and define BP decompositions.  In Section <ref> we given an overview of the how BP decompositions are used to study rationally smooth elements of Coxeter groups.  In Section <ref>, we discuss the applications of BP decompositions to inversion hyperplane arrangments.  In Section <ref> we state and prove how BP decomposition correspond to fiber bundle structures on Schubert varieties.  In Section <ref>, we look at iterated BP decompositions and how they are modeled by staircase diagrams.  One application of staircase diagrams is that they can used to enumerate smooth and rationally smooth Schubert varieties.  In Section <ref>, we focus on permutation groups and discuss how BP decompositions are connected to permutation pattern avoidance.  Finally, in Section <ref> we state some open questions and possible future directions for the study of BP decompositions.  

Our hope is that this chapter will provide readers insights on the nature of BP decompositions and how they are applied.  Since this is a survey article, many statements will be given without proof.  If a proof is not provided, then we will either have brief outlines of the proof or have references provided.  Many results and concepts will have illustrating examples.




§ BACKGROUND ON COXETER GROUPS

We review several foundational properties of Coxeter groups.  For more details, we refer readers to <cit.>.  Let W be a Coxeter group with simple generating set S.  In other words, S is a finite set and W is the group generated by S where for any s,t∈ S, we have a relation

    (st)^m_st=e

for some m_st∈_>0∪{∞} where m_st=1 if and only if s=t.  We say an expression of w∈ W in the simple generators

    w=s_1⋯ s_k
 is reduced if w cannot be expressed in fewer generators.  The length of any reduced expression is unqiue, so we define the function ℓ:W→_≥ 0 which maps w∈ W to the length of any reduced expression.  We call the value ℓ(w) the length of w.

Let w=s_1⋯ s_k be a reduced expression.  We say that u≤ w in the Bruhat order if there exists a subsequence (i_1,…, i_j)⊆(1,…, k) such that u=s_i_1⋯ s_i_j is a reduced expression for u.  We remark that this definition is known as the sub-word property as Bruhat order has other equivalent definitions (see <cit.>).

One particularly important family of Coxeter groups are the permutation groups on integers {1,…,n}.  We will use the notation W=_n when focusing on permutations.  As a Coxeter group, _n has a simple generating set S={s_1,…,s_n-1} where s_i corresponds the simple transposition that swaps i and (i+1).  These generators satisfy the Coxeter relations 

    s_i^2=(s_is_j)^2=(s_is_i+1)^3=e  for all |i-j|>1.

The permutation group _n is referred to as the Coxeter group of type A_n-1.

The permutation group _3 is generated by S={s_1, s_2} and the Bruhat order is given by the following Hassé diagram:


    [scale=0.5]
       (max) at (0,4) s_1s_2s_1;
       (a) at (-2,2) s_2s_1;
       (b) at (2,2) s_1s_2;
       (c) at (-2,0) s_1;
       (d) at (2,0) s_2;
       (min) at (0,-2) e;
       (d) – (min) – (c) – (a) – (max) – (b) – (d) – (a);
      [preaction=draw=white, -,line width=6pt] (c) – (b);



Irreducible Coxeter groups of finite type are classified into four infinite families and six additional types.  This classification is commonly given in terms of Coxeter diagrams (or Dynkin-Coxeter diagrams).  The Coxeter diagram of a Coxeter group is a labeled graph with vertex set S and edges (s,t) labeled by the value m_st under the conventions that we draw no edge if m_st=2 and an unlabelled edge if m_st=3.  See Figure <ref> for the complete classification of irreducible finite Coxeter groups and note that Coxeter groups of types H_2 and G_2 are the dihedral groups I_5 and I_6 respectively. 




If W is the Weyl group of finite dimensional Lie group, then we will refer to these Coxeter groups as “finite Lie type" (these groups are also called finite crystalographic Coxeter groups).  In the classification found in Figure <ref>, these are Coxeter groups of types A_n, B_n, C_n, D_n, E_6,7,8, F_4 and G_2=I_6.  









 §.§ Organization
 In Section 2 we start by going over the definition and properties of BP-decomposition purely from a Coxeter theoretic point of view. Then we go over the root-theoretic description of when we can apply the decomposition. After that, we describe when the decomposition can be applied using permutation patterns.

In Section 3 we go over the application of BP-decomposition to the theory of hyperplane arrangements. Starting from the Weyl arrangement, for each element of the Weyl group, we take an associated subarrangement. We study a certain polynomial coming from this subarrangement.

In Section 4 we go over the application of BP-decomposition to Schubert geometry.


Section topics:



  * Hyper plane arrangements

  * Smoothness criteria for Schubert varieties and root systems

  * Fiber bundle structure of Schubert varieties

  * 






§ INTRODUCTION TO BP-DECOMPOSITION

In this section we introduce the Billey-Postnikov decomposition (BP-decomposition) while also reviewing the basic materials that are going to be needed to understand the decomposition and its applications. Throughout the chapter, W always stands for a Weyl group, and S always stands for its set of simple roots.

 (Subword Property)

Let w = s_1s_2… s_q be a reduced expression. Then we have
u ≤ w if and only if there exists a reduced expression u = s_i_1s_i_2… s_i_k,1 ≤ i_1 < … < i_k ≤ q.



In this section, unless otherwise specified, W is an arbitrary Coxeter group with generating set S.  For any u≤ w∈ W, we use the notation 
    [u,w]:={z∈ W | u≤ z≤ w}

to denote intervals in Bruhat order.  For any w∈ W, define the Poincaré polynomial as the rank generating function on the lower order ideal [e,w]:

    P_w(q):=∑_z∈ [e,w] q^ℓ(z).
 
If X(w) denotes the Schubert variety corresponding to w∈ W, then the Poincaré polynomial recovers the Hilbert-Poincaré series on singular cohomology:

    P_w(q^2)=∑_k(H^k(X(w)))  q^k.

For example, if we take w=s_1s_2s_1 as in Example <ref>, then 

    P_w(q) = 1+2q+2q^2+q^3.

In this case, X(s_1s_2s_1) is the full flag variety of type A_2.  See Section <ref> for a more detailed description of Schubert varieties. 


Let W=⟨ s_1,s_2,s_3 | s_i^2=e⟩ be the the free Coxeter group on three generators and w=s_1s_2s_3s_1.
Then the Bruhat interval [e,w] is:

    [scale=0.5]
       (max) at (0,4) s_1s_2s_3s_1;
       (a1) at (-2,2) s_1s_2s_3;
       (a2) at (-6,2) s_1s_2s_1;
       (a3) at (6,2)  s_1s_3s_1;
       (a4) at (2,2)  s_2s_3s_1;
       (b1) at (-8,0) s_1s_2;
       (b2) at (4,0) s_1s_3;
       (b3) at (-4,0)  s_2s_1;
       (b4) at (0,0)  s_2s_3;
       (b5) at (8,0)  s_3s_1;
       (c1) at (-0,-2) s_1;
       (c2) at (-4,-2)  s_2;
       (c3) at (4,-2)  s_3;
       (min) at (0,-4) e;
      (a3)–(b2)–(a1)–(b4)–(a4)–(b3)–(c1)–(b2) –(c3) –(b5) – (a3) – (max) –(a2) –(b3) – (c2) – (min) – (c1) – (b1) – (a1) – (max) – (a4) – (b5) – (c3) – (min);
       (c3)–(b4)–(c2)–(b1)–(a2);
       (c1) – (b5);

and the Poincaré polynomial is

    P_w(q)=1+3q+5q^2+4q^3+q^4.




Observe that the group inverse map w → w^-1 is an automorphism of Bruhat order in the sense that 

    u ≤ w ↔ u^-1≤ w^-1.

One consequence is
 
    P_w(q) = P_w^-1(q)

 for any w∈ W.
Taking w = s_1s_2 from Example <ref>, we see

    P_s_1s_2(q)=P_s_2s_1(q)= 1+2q+q^2.




 §.§ Quotients and parabolic decompositions


In this section, we discuss parabolic quotients of Coxeter groups. 
 First, we say that a product w=xy is a reduced factorization if ℓ(w)=ℓ(x)+ℓ(y).  Let J ⊆ S and let W_J denote the subgroup of W generated by the set J. Subgroups of form W_J are called parabolic subgroups of W. Each left coset wW_J has a unique representative of minimal length. The set of minimal coset representatives can be defined as 
    W^J:={w ∈ W  | ws > w  for all  s ∈ J}.

The next proposition is from <cit.>.




Let J ⊆ S. Then the following hold:

    
  * Every w ∈ W has a unique factorization w = vu such that v ∈ W^J and u ∈ W_J.
    
  * The decomposition w=vu is a reduced factorization.  In other words, 
    ℓ(w)=ℓ(v)+ℓ(u).




We call the decomposition w=vu in Proposition <ref> the parabolic decomposition with respect to J.  We remark that each w∈ W also has a “left-sided" parabolic decomposition w=uv where v denotes a minimal length representative of the right coset W_Jw.  If needed, we denote this set of minimal length representative by ^JW.  However, the convention we take is that parabolic decompositions will be “right-sided" decompositions w=vu where v is the minimal element of wW_J and u∈ W_J.

One consequence of Proposition <ref> is that the coset decomposition of the group

    W=_v∈ W^J vW_J

respects length in the sense that 

    ∑_w∈ W q^ℓ(w)=(∑_v∈ W^J q^ℓ(v))·(∑_u∈ W_J q^ℓ(u)).

It is natural to ask if the analogous coset decomposition of the interval 

    [e,w]=_v∈ W^J[e,w]∩ vW_J
 gives a similar factorization of the Poincaré polynomial P_w(q).  To make this question precise, we define relative Bruhat intervals and relative Poincaré polynomials.   For any J⊂ S and Bruhat interval [u,v], define the Bruhat interval relative to J as 
    [u,v]^J:=[u,v]∩ W^J.
  For any v∈ W^J, we define the Poincaré polynomial relative to J as

    P^J_v(q):=∑_z∈ [e,v]^J q^ℓ(z).


Let J⊆ S.  We say the parabolic decomposition w=vu such that v∈ W^J and u∈ W_J is a Billey-Postinkov (BP) decomposition with respect to J if the Poincaré polynomial factors as

    P_w(q) = P_v^J(q)· P_u(q).


Proposition <ref> implies that w=vu is a BP decomposition  with respect to J if and only if there is a graded poset isomorphism:

    [e,v]^J× [e,u]≃ [e,w]

where (v',u')↦ v'u'.


Let w=s_1s_2s_3s_2s_1∈_3 and Let J={s_1,s_3}.  Then 

    w=vu=(s_1s_3s_2)(s_1s_3)

is a BP decomposition with respect to J. Here we have 

    [e,v]^J={e, s_2, s_1s_2, s_3s_2, s_1s_3s_2}  and   [e,u]={e,s_1,s_3,s_1s_3}
 with 

    P_v^J(q)=1+q+2q^2+q^3  and   P_u(q)=1+2q+q^2.

The Poincaré polynomial 

    P_w(q)=(1+q+2q^2+q^3)(1+2q+q^2)=1+3q+5q^2+6q^3+4q^4+q^5.

In Figure <ref>, we assign each coset a different color and see that the interval 
    [e,v]^J× [e,u]≃ [e,w].




We remark that not all parabolic decompositions are BP decompositions.  In fact, BP decompositions are rather special and should not be expected in general. 


Let w=s_1s_2s_3s_2s_1∈_3 and let J={s_1,s_2}.  Then the parabolic decomposition

    w=vu=(s_1s_2s_3)(s_2s_1)

is not a BP decomposition. Here we have 

    [e,v]^J={e, s_3, s_2s_3, s_1s_2s_3}  and   [e,u]={e,s_1,s_2,s_2s_1}
 with 

    P_v^J(q)=1+q+q^2+q^3  and   P_u(q)=1+2q+q^2.

The Poincaré polynomial 

    P_w(q)≠ (1+q+q^2+q^3)(1+2q+q^2).

In Figure <ref>, we assign each coset in [e,w] a different color and observe [e,v]^J× [e,u] and [e,w] are not poset isomoprhic.



One important observation contrasting Examples <ref> and <ref>, is that the interval cosets [e,w]∩ vW_J all have the same shape as [e,u] in Example <ref> (cosets are distinguished by different colors in Figure <ref>), while they do not in Example <ref>.  In particular, when comparing the identity coset [e,w]∩ W_J with the “top" coset [e,w]∩ vW_J, if w=vu is a BP decomposition, then u must be the maximal element of [e,w]∩ W_J.  In <cit.>, it is shown this maximally condition is also sufficient for the existence of a BP decomposition.  We remark that van den Hombergh proved in <cit.> that the set [e,w]∩ W_J always has a unique maximal element.  This fact was proved separately by Billey, Fan, and Losonczy in <cit.>.  



 §.§ Characterizing BP decompositions


Our next goal is to list a several combinatorial characterizations of a BP decomposition and prove they are equivalent.  For any w∈ W, define the support of w as the set

    S(w):={s∈ S | s≤ w}.

The support of w can be viewed as the set of generators needed to make any reduced expression of w.  We also define the left and right descent sets of w as

    D_L(w):={s∈ S | ℓ(sw)≤ℓ(w)}

and  
    D_R(w):={s∈ S | ℓ(ws)≤ℓ(w)}.

These decent sets can be thought of as the set of generators appearing on the left (respectively right) of some reduced expression of w.  Observe that D_L(w)=D_R(w^-1).  For example, if w=s_1s_2s_1s_3∈_3,
then 
    S(w)={s_1,s_2,s_3},    D_L(w)={s_1,s_2},  and   D_R(w)={s_1, s_3}.

The following characterization theorem appears in <cit.>.














































































Let J⊂ S and let w=vu be a parabolic decomposition with respect to J.  Then the following are equivalent:

    
  * w=vu is a BP decomposition.
    
  * The map [e,v]^J×[e,u]→ [e,w] given by (v',u')↦ v'u' is bijective.
    
  * u is maximal in [e,w]∩ W_J.
    
  * S(v)∩ J ⊆ D_L(u).




We prove the theorem by showing the equivalencies: (1)↔ (2), (2)↔ (3), and (3)↔ (4). 



Proof of (1)↔ (2):  By Proposition <ref>, the multiplication map given in part (2) is length preserving and injective.  Hence, part (2) says the interval [e,w] decomposes as a product of posets [e,v]^J×[e,u].  This implies that part (1) is equivalent to part (2).  



Proof of (2)↔ (3):  We first assume the multiplication map is surjective (and hence bijective).  Then [e,u]=[e,w]∩ W_J and hence u must be the maximal element in [e,w]∩ W_J.  Conversely, assume u is maximal in [e,w]∩ W_J and let x∈ [e,w].  Let x=v'u' denote the parabolic decomposition of x with respect to J.  By <cit.>, since x≤ w, we have v'≤ v.  But u is maximal in [e,w]∩ W_J and hence u'≤ u.  Thus the multiplication map is surjective.  



Proof of (3)↔ (4):  First suppose that u is maximal in [e,w]∩ W_J and s∈ S(v)∩ J.  Then su∈[e,w] ∩ W_J and by the maximality of u, we must have su≤ u.  Hence s∈ D_L(u).  Conversely, suppose that S(v)∩ J⊆ D_L(u) and hence we can write a reduced factorization u=u_0u' where u_0 is the maximal element in W_S(v)∩ J.  Let x∈ [e,w]∩ W_J.  Since x≤ w=vu=(vu_0)u', we can write a reduced factorization x=u_1u_2 where u_1,u_2∈ W_J with u_1≤ vu_0 and u_2≤ u'.  In particular, we have u_1∈ W_S(v)∩ J and hence x=u_1u_2≤ u_0u'=u.  Thus u is maximal in [e,w]∩ W_J.



For example, we start with w = s_1s_2s_3s_2s_1 in type A, with J = {s_1,s_2}, as in Figure <ref>. The parabolic decomposition is v = s_1s_2s_3 and u = s_2s_1. We have P_w(t) = 1+3q+5q^2+4q^3+q^5, which is not equal to (1+q+q^2+q^3)(1+2q+2q^2+q^3). The map {id,s_3,s_2s_3,s_1s_2s_3}× [id,s_2s_1] → [id,s_1s_2s_3s_2s_1] is not a bijection: in the figure, the cosets are colored differently, and the red and blue cosets have six elements each. The element u = s_2s_1 is clearly not the maximal element of W_J, which is the red coset in the figure. Instead, the maximal element of W_J is s_1s_2s_1. Lastly, the set S(v) ∩ J = {s_1,s_2} which is not a subset of D_L(u) = {s_2}. 



This time we again look at w = s_1s_2s_3s_2s_1 in type A, but with J = {1,3}, as in Figure <ref>. The parabolic decomposition is v = s_1s_3s_2 and u = s_1s_3. We have P_w(t) = 1+3q+5q^2+4q^3+q^5 equal to (1+q+2q^2+q^3)(1+2q+q^2). The map {e,s_2,s_3s_2,s3s_1,s_3s_1s_2}×{id,s_1,s_3,s_1s_3}→ [id,w] is a bijection: in the figure, every colored coset has the same poset. The element u=s_3s_1 is clearly the maximal element of W_J, which is the red coset in the figure. Lastly, the set S(v) ∩ J = {s_1,s_3} which is a subset of D_L(u) = {s_1,s_3}.


While parts (3) and (4) of Theorem <ref> seem like less conventional ways to describe a BP decomposition, we will see in the subsequent sections these characterizations are very useful when working with BP decompositions.



§ RATIONALLY SMOOTH ELEMENTS OF COXETER GROUPS
  

In this section, we discuss BP-decompositions and “rationally smooth" elements of Coxeter groups.  


We say w∈ W is rationally smooth if the coefficients of Poincaré polynomial 

    P_w(q)=∑_i=0^ℓ(w) a_i q^i

satisfy a_i=a_ℓ(w)-i for all 0≤ i≤ℓ(w).  In other words, P_w(q) is a palindromic polynomial.

Similarly, we say v∈ W^J is rationally smooth with respect to J if P_v^J(q) is a palindromic polynomial.

For example, w=s_1s_2s_1∈_n as in Example <ref> is rationally smooth, but the w=s_1s_2s_3s_1 in Example <ref> is not rationally smooth.  Note that rational smoothness and rational smoothness with respect to J do not imply each other.  


Let w=s_2s_1s_3s_2∈_4, then w is rationally smooth with respect to J={s_1,s_3}, but is not rationally smooth (See Figure <ref>).
Here we have 

    P_w(q)=1+3q+5q^2+4q^3+q^4  and   P_w^J(q)=1+q+2q^2+q^3+q^4.



We also see that if w=s_1s_3s_2∈_4, then w is rationally smooth, but not rationally smooth with respect to J={s_1,s_3}.  The polynomials

    P_w(q)=1+3q+3q^2+q^3  and   P_w^J(q)=1+q+2q^2+q^3.



The term “rationally smooth" is derived from the corresponding Schubert variety being rationally smooth in the geometric sense.  The geometric notion of rational smoothness was developed by Kazhdan and Lusztig <cit.> where they show that a Schubert variety is rationally smooth if and only if certain Kazhdan-Lusztig polynomials are trivial.   It was proved by Carrell and Peterson in <cit.> that a Schubert variety X(w) is rationally smooth if and only if P_w(q) is a palindromic polynomial (this result also holds in the relative case with X^J(w) and P^J_w(q)).  Note that Definition <ref> well-defined for elements in any Coxeter group, even if there is no corresponding Schubert variety.  Any smooth variety is rationally smooth for topological reasons, however the converse is not true.  If W is a simply-laced Coxeter of finite type (ie. type A, D or E in Figure <ref>), then X(w) is smooth if and only if it is rationally smooth.  This fact was proved by Deodhar in type A <cit.> and then later in all simply-laced types by Carrell and Kuttler using ideas by Peterson in <cit.>.



 §.§ BP decompositions of rationally smooth elements

The next theorem connects BP decompositions to rationally smooth permutations and is a rephrasing of results due to Gasharov in <cit.> and, independently, due to Lascoux in <cit.>.

Let w∈_n.  Then w is smooth if and only if either w or w^-1 has a BP decomposition vu with respect to J=S∖{s_n-1} where

    P_w(q)=(1+q+⋯ + q^ℓ(v))· P_u(q)
 and u∈ W_J≃_n-1 is smooth.

In Theorem <ref>, the relative interval [e,v]^J is a chain and hence relative Poincaré polynomial 

    P^J_v(q)=1+q+⋯ + q^ℓ(v).
 
Hence v is rationally smooth with respect to J.  Polynomials of this form will come up frequently, so we use q-integer notation

    [r]_q:=1+q+⋯ +q^r-1

for r∈_>0.  Since P_w(q)=P_w^-1(q), the reverse implication of Theorem <ref> follows from the fact products of q-integers are palindromic polynomials.  In Section <ref>, we provide a new proof of the forward direction of Theorem <ref> using “split-pattern" avoidance which was developed by Alland and Richmond in <cit.> to describe BP decompositions in _n in one-line notation.

The following is a generalization of Theorem <ref> to Coxeter groups of finite Lie-type.




Let W be a Coxeter group of finite Lie-type and let w∈ W such that |S(w)|≥ 2.  Then w is rationally smooth if and only if there is a leaf s ∈ S(w) of the Coxeter diagram of W_S(w) such that either w or w^-1 has a BP decomposition vu with respect to J= S(w) ∖{ s} where 

    
  * v is rationally smooth with respect to J and 
    
  * u is rationally smooth.
 

Furthermore, s∈ S(w) can be chosen so that v is either the maximal length element in W_S(v)∩ W^J, or one of the following holds:

    
  * W_S(v) is of type B_n or C_n, with either
    
        
  * J = S(w) ∖{s_1}, and v = s_ks_k+2… s_ns_n-1… s_1, for some 1 < k ≤ n.
        
  * J = S(w) ∖{s_n} with n ≥ 2 and v = s_1 … s_n
    
    
  * W_S(v) is of type F_4, with either
    
        
  * J = S(w) ∖{s_1} and v = s_4s_3s_2s_1
        
  * J = S(w) ∖{s_4} and v = s_1s_2s_3s_4
    
    
  * W_S(v) is of type G_2, and v is one of the elements
    
    s_2s_1, s_1s_2s_1, s_2s_1s_2s_1, s_1s_2, s_2s_1s_2, s_1s_2s_1s_2.


We use the standard conventions of Bourbaki <cit.> for the vertex labelling of Coxeter-Dynkin diagrams.


Note that the later part of Theorem <ref> only concerns Coxeter groups that are not simply laced.  For the classical types of B,C and D, Theorem <ref> was proved by Billey in <cit.>.  The exceptional types were later proved in <cit.> by Billey and Postnikov and in <cit.> by Oh and Yoo.  We remark that if w is rationally smooth of type B/C, then P_w(q) factors into a product q-integers as in the type A case <cit.>.  This is not necessarily true for Poincaré polynomials of rationally smooth elements of other types.  We also remark that, while the notion of rational smoothness is equivalent in types B and C, the notion of smoothness is not since the set of smooth Schubert varieties is differs in these types.  We refer the reader to <cit.> and <cit.> for the distinctions between smoothness in types B and C.

We say a BP decomposition w=vu with respect to J is a Grassmannian BP decomposition if J is a maximal proper subset of S(w).  Grassmannian BP decompositions are “optimal" in the sense that they minimize the degree of the factor P_v^J(q). Note that all the BP decompositions in Theorem <ref> are Grassmannian.  Moreover, since J=S∖{s} where s is leaf in the Coxeter diagram, the poset structure of the relative interval [e,v]^J is less complex compared to when s is not a leaf.  For example, in type A, the interval [e,v]^J is always a chain of length ℓ(v) when J=S∖{s} and s is a leaf.  Grassmannian BP decompositions are discussed in more detail in Sections <ref> and <ref>.   

One issue with Theorem <ref> is the condition that “either w or w^-1 has a BP decomposition".  In Section <ref>, we discuss how BP decompositions correspond to fiber bundle structures on Schubert varieties.  Since X(w) is not isomorphic X(w^-1) in general, we would like an analogue of Theorem <ref> without the “w or w^-1" condition.  In <cit.>, Richmond and Slofstra prove the following.



Let W be a Coxeter group of finite Lie-type.  If w∈ W is rationally smooth, then w has a Grassmannian BP-decomposition with respect to J=S(w)∖{s} for some s∈ S(w).


The sacrifice in Theorem <ref> is that we may not necessarily choose s∈ S(w) to be a leaf.  Theorem <ref> relies on Theorem <ref> and we give a brief outline of the proof in Section <ref>.



Let w = s_2s_1s_3∈_4. The support set S(w)={s_1,s_2,s_3} with Coxeter diagram

    [scale=.4]
        [thick] (0,0)–(2,0)–(4,0);
        [thick,fill=white] (0,0) circle (.3cm) node[label=[label distance=.1cm]-90:s_1] ;
        [thick,fill=white] (2,0) circle (.3cm) node[label=[label distance=.1cm]-90:s_2];
        [thick,fill=white] (4,0) circle (.3cm) node[label=[label distance=.1cm]-90:s_3];

The Poincaré polynomial is 
    P_w(q) = 1+3q+3q^2+q^3
 is palindromic and hence w is rationally smooth. 
If J=S(w)∖{s_3}={s_1,s_2}, then the parabolic decomposition with respect to J

    w=vu=(s_2s_3)(s_1)

is not a BP decomposition. 


    [scale=0.5]
      [black!20!green] (a1) at (0,2) s_2s_1s_3;
      [black!20!green] (b2) at (4,0) s_2s_3;
      [black!20!red] (b3) at (-4,0)  s_2s_1;
      [black!20!blue] (b4) at (0,0)  s_1s_3;
      [black!20!red] (c1) at (-0,-2) s_2;
      [black!20!red] (c2) at (-4,-2)  s_1;
      [black!20!blue] (c3) at (4,-2)  s_3;
      [black!20!red] (min) at (0,-4) e;  
      (min)–(c2)–(b3)–(a1)–(b4)–(c2);
       (min)–(c1)–(b3);
       (min)–(c3)–(b4)–(a1)–(b2)–(c3);
       (c1)–(b2);




Likewise w=vu=(s_2s_3)(s_1) is not a BP decomposition with respect to J={s_2,s_3} and hence w has no “leaf removed" BP decomposition. 

If we take J =S(w)∖{s_2}= {s_1,s_3}, then 
    w =vu= (s_2)(s_1s_3)
 is a Grassmannian BP decomposition.  Here we have 

    P_w(q) = P^J_s_2(q) · P_s_1s_3(q)=(1+q)· (1+2q+q^2).
 


    [scale=0.5]
      [black!20!blue] (a1) at (0,2) s_2s_1s_3;
      [black!20!blue] (b2) at (4,0) s_2s_3;
      [black!20!blue] (b3) at (-4,0)  s_2s_1;
      [black!20!red] (b4) at (0,0)  s_1s_3;
      [black!20!blue] (c1) at (-0,-2) s_2;
      [black!20!red] (c2) at (-4,-2)  s_1;
      [black!20!red] (c3) at (4,-2)  s_3;
      [black!20!red] (min) at (0,-4) e;  
      (min)–(c2)–(b3)–(a1)–(b4)–(c2);
       (min)–(c1)–(b3);
       (min)–(c3)–(b4)–(a1)–(b2)–(c3);
       (c1)–(b2);



Observe that the inverse w^-1=s_1s_3s_2 does have a leaf removed BP decomposition with respect to both J={s_1,s_2} and J={s_2,s_3}.























 §.§ Background on Permutations

In this section, we focus on the permutation group _n.  For any n∈_>0, let [n]:={1,2,…, n}.  Each permutation w∈_n corresponds to a bijection w:[n]→ [n] and has a unique presentation in one-line notation w=w(1)w(2)⋯ w(n).  Under the Coxeter presentation of _n, the generators s_i correspond to the simple transpositions swapping i and (i+1).  The right action of s_i on the one-line notation of w is given by swapping the w(i) and w(i+1) where the left action is given by swapping the position of the entries i and (i+1).  The length of a permutation can be calculated by counting inversions:

    ℓ(w)=#{(i,j) | i>j and w(i)<w(j)}.

The Bruhat partial order is generated by the relations w≤ w' where w' is w with two entries swapped and ℓ(w)<ℓ(w').
For example, the Bruhat order on _4 is given in Figure <ref>.


It will be common this chapter to state results for general Coxeter groups and then give more details in the case of permutations.  Sometimes it will be more convenient to use one-line notation over Coxeter theoretic reduced words to represent permutations.  In Section <ref>, we give a detailed overview of how BP-decompositions on permutations can be described using pattern avoidance.  Pattern avoidance has been a remarkable tool used to describe many properties of both permutations and Schubert varieties.  A survey of many of these results can be found in <cit.>.

We conclude this section with a one-line notation version of Theorem <ref> that will be important in Section <ref> on hyperplane arrangements.  Given w ∈_n, we define the operation (w,i) as the permutation in _n-1 obtained by removing the entry w(i) from w and then relabeling the remaining entries with [n-1] while maintaining the relative order.  For example, (635214,3)=54213.



Let w ∈_n be a smooth permutation and assume w(d) = n and w(n) = e. Then at least one of the following two statements is true:

    
  * w(d) > w(d+1) > … > w(n), or
    
  * w^-1(e) > w^-1(e+1) > … > w^-1(n).

In both cases, the Poincaré polynomial factors as 

    P_w(q) = [m+1]_q · P_u(q),

where 

    
  * u = (w,d) and m = n-d in the first case and 
    
  * u = (w,n) and m = n-e in the second case.









Let w=2431 = s_1s_2s_3s_2∈_4. We have d=2 and e=1. Observe that w(2) = 4 > w(3) = 3 > w(4) = 1, so the first statement of Corollary <ref> holds. We have u = (2431,2) = 231 = s_1s_2 and m = 4-2 = 2. The Poincaré polynomial factors

    P_2431(q) = (1+q+q^2)· P_231(q)=(1+q+q^2)(1+2q+q^2).
 
This factorization corresponds to the BP decomposition of 
    w^-1=(s_2s_3)(s_2s_1)
 with respect to J={s_1,s_2}.  In Figure <ref>, we highlight this decomposition in the Bruhat interval [1234,2431].





































§ HYPERPLANE ARRANGEMENTS


In this section, we will give an overview of one of the major applications of the Billey-Postnikov decomposition, focusing on hyperplane arrangements. Let W be a Coxeter group of finite Lie type.  For each w ∈ W, we will compare the Poincaré polynomial P_w(q) with another polynomial, which comes from an associated hyperplane arrangement. 





The poset structure we assign on the chambers of the hyperplane arrangements we study will be motivated from the weak Bruhat order on W.




Let (W,S) be a Coxeter system and let u,w ∈ W.  The right and left weak Bruhat orders ≤_R and ≤_L are generated by the following cover relations.

    
  * We have u ≤_R w if w = us, for some s∉ D_R(u). 
    
  * We have u ≤_L w if w = su, for some s∉ D_L(u).



An example of left weak Bruhat order of _3 is drawn in Figure <ref>. On the right side of the figure is the usual (strong) Bruhat order of _3. Notice that the set of elements is the same, and the rank of each element is the same between the two posets. This is true in general for any Coxeter group <cit.>.







 §.§ Hyperplane arrangement of a Coxeter group

Each finite Coxeter group W is naturally associated with a hyperplane arrangement through a root system.  Let Φ be a finite collection of non-zero vectors in some Euclidean space ^n.  For each α∈Φ, we define the reflection s_α:^n→^n by 

    s_α(x):=x-2(α,x)/(α,α)α.

We say Φ is a root system of W if the following hold:

    
  * Φ∩α={α,-α} for each α∈Φ,
    
  * s_α(Φ)⊆Φ for all α∈Φ, and 
    
  * W≃⟨ s_α | α∈Φ⟩.

The vectors α∈Φ are called roots.  Let S denote the set of simple generators of W.  For each s∈ S, there is a unique root (up to sign) α_s which satisfies the condition that s(α_s)=-α_s.  We define a set of simple roots

    Δ:={α_s |  s∈ S}

by selecting ±α_s that all lie on one side of a suitably generic, but fixed hyperplane in ^n.  It can be shown that each α∈Φ is either a totally positive or totally negative linear combination of simple roots, so we can decompose 

    Φ=Φ^+⊔Φ^-

into collections of positive and negative roots with respect to Δ.  For more on root systems of Coxeter groups, see <cit.> or <cit.>.  

To each α∈Φ, there is the corresponding hyperplane given by 

    H_α:={x∈^n |  (α,x)=0}.

Note that H_α=H_-α and that if x∈ H_α, then s_α(x)=x.  The collection of hyperplanes 
    _W:={H_α | α∈Φ^+}
 is called the Coxeter arrangement of W.  Since each H_α contains the origin in ^n, _W is an example of a central hyperplane arrangement.



For each element w ∈ W, we can take a subset of hyperplanes in _W corresponding to the inversions of w. 
 We define the inversion set of w as the set of positive roots
 
    Φ_w := {α∈Φ^+ | w(α)∈Φ^- }.

and the inversion hyperplane arrangement

    _w:={H_α | α∈Φ_w}.

If w_0 denotes the longest element in W, then _w_0=_W.  For permutations, the root-theoretic inversion set Φ_w corresponds the usual inversion set of pairs:

    {(i,j)∈ [n]^2 | i<j and w(i) > w(j)}.










Consider the permutation group _n and let ^n be a vectors space with coordinate basis {x_1,…,x_n}.  The group _n acts on ^n by the standard permutation action the coordinate basis elements.  The set of vectors 

    Φ={x_i-x_j | i≠ j}

is a root system of _n with positive roots Φ^+={x_i-x_j | i>j} and simple roots Δ={x_i-x_i+1 | 1≤ i<n}.  If α=x_i-x_j, then the hyperplane H_α is defined by the equation x_i=x_j.  The Coxeter arrangement of _n is 
    __n={x_i=x_j |  i≠ j}.

For any w∈_n, we have the inversion arrangement

    _w={x_i=x_j |   i<j and w(i) > w(j) }.

Note that the hyperplane ∑_i x_i=0 is invariant under the action of _n. Hence we can realize __n as a hyperplane arrangement in 
    ^n-1≃^n/(∑_i x_i=0).
  This reduction will help us visualize hyperplane arrangements in examples.

For any inversion arrangement _w, Let r_0 denote the fundamental chamber which is defined as the set of points x∈^n such that  (α,x)>0 for all α∈Φ_w. We define the distance enumerating polynomial on _w as

    R_w(q) :=∑_r q^d(r_0,r)
 where the sum
is over all chambers of the arrangement _w and d(r_0,r) is the minimum number of hyperplanes separating
r_0 and r. 


In Figure <ref>, we have the inversion arrangements _321 and _312. Since 321 is the longest element of _3, we have _321 = __3 which consists of the three hyperplanes

    __3={x_1=x_2, x_1=x_2, x_2=x_3}


Moreover, we can label each region with permutation in _3. The fundamental chamber is labelled with the identity permutation 123. Starting from this, we measure the distance between each chamber and the fundamental chamber by counting the minimal number of hyperplanes needed to cross to reach the fundamental chamber.  We highlight this distance in blue. We can see that 

    R_321(q) = 1+2q+2q^2 + q^3.
 

For _312, we remove the hyperplane x_2 = x_3 from _321. The fundamental chamber is the unique chamber that contains the identity label 123.  Counting in a similar way, we obtain 
    R_312(q) = 1+2q+q^2.




















Our main goal of this section is to prove the following result found in <cit.> and <cit.>:


Let W be a Coxeter group of finite Lie-type. Then w∈ W is rationally smooth if and only if P_w(q) = R_w(q).





Let w=4321 denote the longest permutation in _4.  Then 
    _4321={x_1=x_2, x_1=x_3, x_1=x_4, x_2=x_3, x_2=x_4, x_3=x_4 }.

In Figure <ref>, we label the chambers by the values d(r_0,r).  By the symmetry of the picture, we can see that 
    R_4321=1+3q+5q^2+6q^3+5q^4+3q^5+q^6.


The rank generating function of [1234,4321] in Figure <ref> is the same polynomial, so this verifies the fact that P_4321(q) = R_4321(q).

If w=2431 (See Figure <ref>), then inversion arrangement

    _2431={x_1 = x_4, x_2 = x_3, x_2 = x_4, x_3 = x_4}

and R_2431(q)=1+3q+4q^2+3q^3+q^4.  From Figure <ref>, we see that w is smooth and P_2431(q) = R_2431(q).


If w=4231, then _4231=_4321∖{x_2=x_3}.  
In Figure <ref>, we see 

    R_4231(q)=1+4q+4q^2+4q^3+4q^5+q^5.



In this case w is not smooth (see Example <ref>) and 
    P_4231(q)= 1 + 3^q + 5q^2 + 6q^3 + 4q^4 + q^5.






















 §.§ Inversion arrangements for permutations

In this section, we provide a proof of Theorem <ref> for permutations. The main strategy is to show that R_w(q) follows the exact same decomposition as P_w(q) in Corollary <ref>.

For an undirected graph G on vertex set {1,…,n}, the graphical arrangement, _G is the hyperplane arrangement in ^n with hyperplanes x_i=x_j for all edges (i,j) of G. In the case G is a complete graph on n vertices, we get the Coxeter arrangement __n. 

Given a permutation w ∈_n, we define its inversion graph G_w as an undirected graph on vertices [n]={1,…,n} and edges (i,j) whenever we have i < j and w(i) > w(j). Note that the inversion arrangement _w is the graphical arrangement _G_w. 

An acyclic orientation on G is an assignment of directions to the edges of G so that no directed cycles are formed. It is easy to see that the regions of _G are in bijection with acyclic orientations of G. Indeed, if  is an acyclic orientation of G, then we interpret each directed edge i → j as x_i < x_j. This corresponds to choosing a side of each hyperplane of _G, hence uniquely defining a region in _G.

From this observation, the distance enumerating polynomial R_w(q) can be described in terms of acyclic orientations of the graph G_w. For an acyclic orientation , let () be the number of edges oriented oriented as i → j in  where i>j (so this corresponds to a descent of w). We define 

    R_G(q) := ∑_ q^().

It can be shown that R_G_w(q)=R_w(q).  A clique of G is a subgraph of G such that it is isomorphic to a complete graph. Given a graph G and a vertex k of G, let G∖ k denote the graph obtained by deleting k and its adjacent edges in G.  The following lemma is from <cit.>.



Suppose that a graph G on vertex set [n] has a vertex k that satisfies the following two conditions:

    
  * The neighbors of k form a clique in G.
    
  * Either all neighbors of k are less than k or all neighbors of k are greater than k.

Then R_G(q) = [m+1]_q· R_G ∖ k(q) where m is the degree of the vertex k.




Consider the inversion graph of w=2431

    [scale=0.25]
     (0,0) circle (7pt) node[label=[label distance=.1cm]180:4];
     (0,4) circle (7pt) node[label=[label distance=.1cm]180:1];
     (4,4) circle (7pt) node[label=[label distance=.1cm]0:2];
     (4,0) circle (7pt) node[label=[label distance=.1cm]0:3];
    [thick] (0,0)–(4,4)–(4,0)–(0,0)–(0,4);

corresponding to inversions (1,4),(2,3),(2,4),(3,4). The neighbor of 2 is {3,4}, which is a clique, since (3,4) is an edge.  Moreover all vertices in this clique is bigger than 2.  By Lemma <ref>, we have 
    R_2431(q) = (1+q+q^2)· R_231(q).
   
Comparing this to P_2431(q) in Example <ref>, we see these polynomials decompose in the exact same manner. 




Let w∈_n.  We need to check that the recursion in Lemma <ref> behaves exactly the same way as the recursion in Corollary <ref>.  Using d and e as in Corollary <ref>, we have w(d) > w(d+1) > … > w(n) if and only if the neighbor of n in G_w forms a clique. The other case, w^-1(e) > … > w^-1(n) happens if and only if the neighbor of n in G_w^-1 forms a clique. From this observation that the two recurrences are the same whenever w is a smooth permutation.





 §.§ The general case

We now consider the case when W is a Coxeter group of finite Lie type.  
As with permutations, the main idea is to use BP-decompositions to show that the polynomials P_w(q) and R_w(q) follow the same recursion.  In type A, the analysis was simpler since we could always choose v so it is the maximal length element of W_S(v)∩ W^J, in the context of Theorem <ref>. 



For other types there are more cases of v to consider, so the proof is more technical. Despite already having covered the type A case, the examples we use in this section used to illustrate the ideas will also come from the type A for simplicity.  We will be utilizing Theorem <ref> as our main tool for decomposing the polynomials.  The results in this section are due to Mcalmon, Oh, and Yoo in <cit.> and Oh and Yoo in <cit.>.










Let  be a central hyperplane arrangement with a fixed fundamental chamber r_0 and let Q_ denote the set of chambers of .  We define a poset structure on Q_ generated by the covering relations r_1<r_2 if chamber r_1 is adjacent to chamber r_2 and d(r_1,r_0)=d(r_2,r_0)-1.   

If ' is some subarrangement of  and r∈ Q_', we define the induced subposet Q_,',r to be the subposet of Q_ obtained by restricting to the chambers of  contained in r.  We say that  is uniform with respect to ' if for all chambers r of ', the induced subposets Q_,',r are all isomorphic.  In this case, we use Q_,' to denote the poset.


We consider the inversion arrangement of w=4132:

    _4132={x_1 = x_2, x_1 = x_3, x_1 = x_4, x_3 = x_4}


Now consider the hyperplane arrangement _3124 which is a subarrangement of _4132 by removing the hyperplanes x_1 = x_4 and x_3 = x_4.  In Figure <ref>, we highlight _3124 in yellow.  

Let r_0' denote fundamental chamber of _3124.  We see that r_0' contains three chambers from _4132 and the poset Q__4132,_3124,r_0' is a chain of length 3.  The same is true for all other chambers of _4132 and hence _4132 is uniform with respect to _3124.





Recall that if w_0 is the longest element of W, the arrangement _w_0 is the Coxeter arrangement of W. Here each chamber is indexed with a permutation w ∈ W and two chambers u,w are adjacent if and only if w=su for some s∈ S. Hence, the poset Q__w_0 where w_0 is the longest element of W is exactly the (left) weak Bruhat order of W. Recall that the weak Bruhat order of W and the strong Bruhat order of W are different poset structures on the same set of elements with the same rank <cit.>. From this we get the following lemma.



Let w_0 be the longest element of W.  Then P_w_0(q) = R_w_0(q).  Furthermore, for any J⊆ S, if u_0 is the longest element of W_J for some J ⊂ S, then _w_0 is uniform with respect to _u_0. 


Each chamber of _w_0 is indexed by an element w ∈ W and each w ∈ W has a parabolic decomposition vu where u ∈ W_J and v ∈ W^J. The chambers indexed by vu with common u ∈ W_J are contained in the same chamber indexed by u in _u_0. For each chamber u in _u_J, the chambers of _w_0 contained in u are only separated by hyperplanes in _w_0∖_u_0. The poset Q__w_0,_u_0 is the left weak Bruhat order of W^J.


We use BP decompositions to develop some tools needed for the recursion on R_w(q) when w is rationally smooth.  Let J⊆ S and suppose we have a BP decomposition w=vu with respect to J.  By Theorem <ref> part (4), we have that S(v)∩ J⊆ D_L(u).  In particular, we can write a reduced factorization 

    u=u_S(v)∩ J· u'

where u_S(v)∩ J is the longest element of W_S(v)∩ J.  Theorem <ref> implies that if w∈ W is rationally smooth, then either w or w^-1 has Grassmannian BP decomposition with respect to some J of the form 

    v· (u_S(v)∩ J· u')

For notational simplicity, let I:=S(v).  Given such a decomposition, we decompose 

    _w=_0⊔_1⊔_2

where 

    _2:=_w∖_u,   _1:=_u∖_0,  and  _0:= (u')^-1_u_I∩ J




The first step is the following lemma:


Let w∈ W be a rationally smooth element and w=uv be a BP-decomposition. Then every simple reflection in J appearing in the reduced word of v
is a right descent of u.



 If we remove every simple reflection appearing in v but one in J, then the resulting element is in W_J and is below w. Hence by maximality of u, it is below u.


Actually, we can state much more about u in terms of simple reflections of J appearing in v.


Let w=uv be a BP-decomposition with respect to J. Let I be the subset of S that appears in the reduced word of v. Then every reflection formed by simple reflections in I∩ J is a right inversion reflection of u. In fact, there is a minimal length decomposition u=u'u_I ∩ J where u_I ∩ J is the longest element of W_I∩ J.



Take the parabolic decomposition of u under the right quotient by W_I∩ J. Say, u=u'u”. Then u' is the minimal length representative of u in W/W_I∩ J. For any simple reflection s∈ I∩ J, the minimal length representative of us in W/W_I∩ J is still u', hence the parabolic decomposition
of us is us=u'(u”s). Since s is a right descent of u by Lemma <ref>, s is a right descent of u”. Therefore, u” is the longest element in W_I∩ J. The rest follows from this.


The above lemma tells us that for each rationally smooth w ∈ W, we can decompose w or w^-1 to u' u_I ∩ J v where uv is the BP-decomposition with respect to J, with u = u'u_I ∩ J and u_I ∩ J is the longest element of W_I ∩ J. Given such decomposition, we decompose _w into _0 _u_I ∩ J, _1 _u ∖_0 and _2 _w ∖_u.


**TODO : make sure BP notation-wise. left BP do it using inverse.
**TODO : Maximal element for W_J notation? Use u_I instead of u_0
**TODO : J = {s_1,…} not integers
**TODO : Use gothic S_n





Let r be some chamber inside _1 ⊔_0. Let r' be the chamber of _0 that contains r. Then the poset Q__w, _1 ⊔_0, r is isomorphic to Q__0 ⊔_2, _0, r'.



Once a chamber r' of _0 is fixed, we will show that any chamber of _0 ⊔_2 contained in r' intersects every chamber of _1 ⊔_0 contained in r'. In order to show this, we can freely add more hyperplanes to _0, _1 and _2. So we may assume that u = u_I∩ J u' is the longest element of W_J and v is the longest element of W^J. 

From Lemma <ref>, each chamber of _0 is now indexed with a permutation of W_I ∩ J. Fix a chamber r_x labeled with a permutation x ∈ W_I ∩ J. Each chamber of _0 ⊔_2 contained in r_x is labeled with a permutation zx where z ∈ W^J. Each chamber of _1 ⊔_0 contained in r_x is labeled with a permutation xy where y^-1∈ W^I ∩ J∩ W_J. For any such chamber of _0 ⊔_2 and _1 ⊔_0, their intersection will be the chamber of  that is labeled by zxy∈ W. 

Let r_1 and r_2 be two different chambers of  contained in r. They are separated by a hyperplane in _2. For i=1,2, let r_i' be the chamber of _0 ⊔_2 that contains r_i. Then r_1' and r_2' are different chambers, since they are separated by the hyperplane that separates r_1 and r_2. If r_1 and r_2 are adjacent, then r_1' and r_2' are adjacent. If r_1' and r_2' are adjacent but r_1 and r_2 are not, it means there is a hyperplane of _1 that separates r_1 and r_2. But that contradicts the fact that r_1 and r_2 are both contained in the same chamber of _1 ⊔_0. We conclude that r_1 and r_2 are adjacent if and only if r_1' and r_2' are adjacent. 












Let w=4132 and consider the arrangement _4132 from Figure <ref>. The BP-decomposition with respect to J = {s_1,s_2} is 
    w=(s_2s_3)(s_2s_1)
 where v = s_2s_3 = 1342 and u = s_2s_1= 3124. The set I=S(v)={s_2,s_3} and u_I ∩ J = s_2 = 1324. 

Looking at the inversions of w, we get:  
    _w={x_1 = x_2, x_1 = x_3, x_1 = x_4, x_3 = x_4}
 with 

    _u = {x_1 = x_2, x_1 = x_3}, _2= {x_1 = x_4, x_3 = x_4}, and _I ∩ J={x_2 = x_3}.
  The arrangement _0 = (s_1)^-1_I ∩ J={x_1 = x_3} and hence _1 = {x_1=x_2}. From  Proposition <ref>, we have that Q(_4132,_3124) is isomorphic to Q(_3214,_1324) where s_2s_3s_2=3214 and s_2=1324.  This poset is a chain of length 3 by Lemma <ref>.





























From the above property we immediately get the following tool:


Suppose we have a decomposition w=v(u_I∩ Ju') as in Proposition <ref> and assume _vu_I ∩ J is uniform with respect to _u_I ∩ J.  

If R_vu_I ∩ J(q) = P_vu_I ∩ J(q) and R_u(q) = P_u(q), then  R_w(q) = P_w(q).






If _vu_I ∩ J is uniform with respect to _u_I ∩ J, then Proposition <ref> tells us that _w is uniform with respect to _u. Hence R_w(q) is divisible by R_u(q). Moreover, 
    R_w(q)/R_u(q) = R_vu_I ∩ J(q)/R_u_I ∩ J(q).
 From Lemma <ref>, we have R_u_I ∩ J(q) = P_u_I ∩ J(q). Hence R_vu_I ∩ J(q) = P_vu_I ∩ J(q) and R_u(q) = P_u(q) implies R_w(q) = P_w(q).



Corollary  <ref> allows us to consider only the case where u is the longest element of some W_I. 

Let I be the set of simple roots that appear in a reduced word of v. We say that v is a locally-maximal element in W^J if it is the maximal element of W_I^I ∩ J:=W_I∩ W^I ∩ J and I forms a connected subgraph within the Coxeter diagram. Similarly we say that v is in a local chain if W_I^I ∩ J is a chain poset. Notice that in Theorem <ref>, only case when v is not locally-maximal nor a local chain lies in Coxeter groups of type F_4 and B_n.






Suppose we have a decomposition w=v(u_I∩ Ju') as in Proposition <ref>.  

If v is a locally-maximal element or a local chain, then P_u(q)=R_u(q) implies P_w(q) = R_w(q).




From corollary <ref>, it is enough to show _vu_I ∩ J is uniform with respect to _u_I ∩ J and R_vu_I ∩ J(q) = P_vu_I ∩ J(q).

If v is the longest element of W^J, then vu_I ∩ J is the longest element of W_I. In this case, the proposition follows from Lemma <ref>.



When W_I^I ∩ J is a chain, let v' denote the longest element of W_I^I ∩ J. Then w' := v'u_I ∩ J is the longest element of W_I. From Lemma <ref>, we have that R_u_I ∩ J(q) = P_u_I ∩ J(q) and R_v'u_I ∩ J(q) = P_v'u_I ∩ J(q). For each chamber r of _u_I ∩ J, the poset Q(_w',_u_I ∩ J,u) is a chain of length ℓ(v'). In particular, every hyperplane of _w'∖_u_I ∩ J intersects the interior of the chamber r.

When we go from _w'=v'u_I ∩ J to _vu_I ∩ J, we remove some hyperplanes from _w'∖_u_I ∩ J. For each chamber r of _u_I ∩ J, the poset Q(_v'u_I ∩ J,_u_I ∩ J,r) is a chain of length ℓ(v') minus the number of hyperplanes removed. Hence _vu_I ∩ J is uniform with respect to _u_I ∩ J. Moreover, we have 
    R_vu_I ∩ J(q) = (1+⋯+q^ℓ(v))· R_u_I ∩ J(q).
 The proposition now follows from Lemma <ref>.
 


Lastly we analyze two special examples each coming from Coxeter groups of type F_4 and B_n which will be needed for our main result. These examples correspond to parts (1b) and (2b) in Theorem <ref>.  We start with type F_4:



Let W be a Coxeter group of type F_4. Let w=vu where u is the longest element of W_{s_1,s_2,s_3} and v = s_1s_2s_3s_4. Then w=vu is a BP decomposition and 
    P_w(q) =(1+q+q^2+q^3)· P_u(q).
  
The root system of type F_4 lies in ^4 and the hyperplane arrangement _w is the union of

    _u={x_1=0,    x_2=0, x_3=0, x_2-x_1=0, x_3-x_2=0,
       x_3-x_1=0, x_1+x_2=0, x_1+x_3=0, x_2+x_3=0}

and the hyperplanes 

    {x_1+x_2+x_3=x_4, -x_1-x_2+x_3=x_4, 
    -x_1+x_2-x_3=x_4, x_1-x_2-x_3=x_4}.

Pick any chamber c of _u and an arbitrary interior point z = (z_1,z_2,z_3,z_4)∈ c. Consider the line l_z obtained from z by changing the z_4 value from -∞ to +∞. This line is still contained in chamber c. Imagine moving through the line l_z by changing the z_4 value from -∞ to +∞. The difference between any pair of equations of hyperplanes in _w ∖_u is of form 2x_i + 2x_j = 0. For each pair i ≠ j ≤ 3 whether x_i+x_j is positive or negative is determined by the choice of c since x_i+x_j=0 is a hyperplane of _u. Therefore, the order we cross the hyperplanes of _w ∖_u is completely determined by c.


From this we can conclude that _w is uniform with respect to _u. Moreover, the poset Q_w is obtained from Q_u by a poset product with a chain of length 4. We get 

    R_w(q) = (1+q+q^2+q^3 + q^4)· R_u(q).
 
Since R_u(q) = P_u(q) from Lemma <ref> and P_v^W^J(q) = (1+ ⋯ + q^ℓ(v)), we obtain the desired result.


Now we consider the case of B_n with the leaf s_n in its Coxeter diagram.



Let W be a type B_n Coxeter group and simple generating set S={s_1,…, s_n} and let J = S ∖{s_n}. Let w = v u where u is the longest element of W_J and v =  s_1 ⋯ s_n-1 s_n.  Then _w is uniform with respect to _u and P_w(q) = R_w(q).


The root system of type B_n lies in ^n and the hyperplane arrangement _u consists of hyperplanes defined by the following equations:

    
  * x_i = 0 for 1 ≤ i ≤ n-1,
    
  * x_i - x_j = 0 for 1 ≤ i < j ≤ n-1, and
    
  * x_i + x_j = 0 for 1 ≤ i < j ≤ n-1.

The hyperplane arrangement _w is obtained from _u with the additional the hyperplanes x_n=0 and x_n + x_i = 0 for 1 ≤ i ≤ n-1. 

Pick any chamber c of _u and arbitrary interior point z = (z_1,…,z_n)∈ c. The chamber c determines a total order on z_1,…,z_n-1 and 0 that does not depend on the choice of z. Consider the line l_z obtained from z by changing the value of z_n from -∞ to +∞ and that l_z is contained in the chamber c. As the value of z_n moves from -∞ to +∞ along l_z, the order in which we cross the hyperplanes of _w ∖_u is determined by the total order on z_1,…,z_n-1 and 0.

Hence _w is uniform with respect to _u. Moreover, the poset Q_w is obtained from Q_u by a poset product with a chain of length n. We get R_w(q) = (1+ ⋯ + q^ℓ(v))· R_u(q). Since R_u(q) = P_u(q) from Lemma <ref> and P_v^W^J(q) = (1+ ⋯ + q^ℓ(v)), we obtain the desired result.


We are now ready to prove Theorem <ref>.  First note that R_w(q) is always palindromic by definition.  So if w∈ W is not rationally smooth, P_w(q)≠ R_w(q).  From the above Proposition <ref> and Theorem <ref> we can obtain the following result which completes the proof.


Let W be a Coxeter group of finite Lie-type and let w∈ W be rationally smooth. Then R_w(q) = P_w(q). 

 
We use induction on |S(w)|. First, if w=s∈ S, then R_w(q)=P_w(q)=1+q. By Theorem <ref>, either w or w^-1 has a Grassmannian BP decomposition vu. Furthermore, v is a locally-maximal element or is in a local chain or is in special cases of types F_4 or B_n. In the first two cases, that is, when v is a locally-maximal element or is in a local chain, then Proposition <ref> allows us to replace w with rationally smooth u where |S(u)|<|S(w)|. If we are in the special cases, using Example <ref> and Lemma <ref> combined with Corollary <ref> allows us the same replacement.


When w∈ W is rationally smooth, it is common for the polynomials P_w(q) = R_w(q) to factor as a product of q-integers. If P_w(q) factors into q-integers along Grassmannian BP decompositions, we say that w has a chain BP decomposition (this name comes from the fact that each poset [e,v]^J is a chain).   By Corollary <ref> (<cit.>), all smooth permutations have chain BP decompositions.  If w∈ W has a chain BP decomposition, then the degrees of the q-integer factors of P_w(q)=R_w(q) are strongly related to the structure of the corresponding inversion arrangement and are called exponents of w.  In <cit.>, Slofstra gives an explicit description of these exponents.  For other interesting results in inversion arrangements, we recommend that the reader take a look at <cit.>, <cit.>, <cit.>, <cit.>, <cit.>.






§ CONNECTIONS WITH THE GEOMETRY OF SCHUBERT VARIETIES

In this section, we present results from <cit.> which connects BP decompositions to the geometry of Schubert varieties.  Let G be a connected simple Lie group over  and fix a Borel subgroup B.  Let W denote the Weyl group of G with generating set S.  Since G is a finite dimensional Lie group, the Weyl group W is a Coxeter group of finite Lie type (See Figure <ref>).  For any subset J⊆ S, let W_J the parabolic subgroup of W generated by J and let P_J:=BW_JB denote the corresponding parabolic subgroup of G.  The coset space G/P_J is called a partial flag variety of G and it is a smooth complex protective homogeneous space.  If J=∅, then P_∅= B and G/B is called the complete or full flag variety of G.  

Consider the natural projection between flag varieties

    π:G/B→ G/P_J

given by π(gB)=gP_J.  It is not hard to see that the fibers of the this map are 
    π^-1(gP_J)=gP_J/B
 and that the map π gives a (P_J/B)-fiber bundle structure on the flag variety G/B with base G/P_J.   For any w∈ W^J, we define the Schubert variety as the closure of the B-orbit (i.e. Schubert cell)

    X^J(w):=BwP_J/P_J.

If J=∅, then P_∅=B and we will denote X(w):=X^∅(w).  
It is well known that if w∈ W^J, then  

    _(X^J(w))=ℓ(w)

and Bruhat order describes the closure relations on Schubert cells

    X^J(w)=_w'∈[e,w]^J Bw'P_J/P_J.

In this section, we consider all Schubert varieties and do not restrict to the cases of smooth or rationally smooth.  If w=vu is a parabolic decomposition with respect to J, then u∈ P_J and hence π restricts to a projection between Schubert varieties

    π:X(w)→ X^J(v).

The question we address is when does the map π induce a fiber bundle structure on X(w)?  As we will see, the generic fibers of this map are isomorphic to the Schubert variety X(u), however, unlike for G/B, the map π restricted to a Schubert variety may not fiber bundle.  The following theorem is a geometric realization of BP-decompositions and is proved by Richmond and Slofstra in <cit.>.


Let w=vu be a parabolic decomposition with respect to J.  Then the following are equivalent:

    
  * The decomposition w=vu is a BP decomposition with respect to J.
    
  * The projection π:X(w)→ X^J(v) is a Zarisky-locally trivial with fiber X(u).




Our goal is to give a detailed proof Theorem <ref> following <cit.>.  First, we need several important lemmas about Schubert varieties.  One key property needed in the proof of these results is the following well-known relation for double B-orbits for BN-pairs (or Tits systems).


Given s∈ S and u∈ W, we have

    BsB· BuB=
    BsuB    if s∉ D_L(u)
    
    BuB∪ BsuB    if s ∈ D_L(u)


If xP_J∈ X^J(v), then we can write xP_J=b_0v_0P_J for some b_0∈ B and v_0∈[e,v]^J.  The next lemma (<cit.>) describes the fibers of the map π.


Let w=vu be the parabolic decomposition with respect to J and π:X(w)→ X^J(v).  Let xP_J∈ X^J(v) and write x=b_0v_0 for some b_0∈ B and v_0∈[e,v]^J.  Then

    π^-1(xP_J)=x⋃ Bu'B/B

where the union is over all u'∈ W_J such that v_0u'≤ w.



We first look at the fiber over xP_J of the map π:G/B→ G/P_J. Note that 
    P_J=B W_J B=⋃_u'∈ W_J BuB
 and hence the fiber of xP_J in the full flag variety G/B is

    π^-1(xP_J)=b_0v_0⋃_u'∈ W_J BuB/B.

Restricting the map π to the Schubert variety X(w) gives

    π^-1(xP_J)=(b_0v_0⋃_u'∈ W_J Bu'B/B) ∩(⋃_w'≤ wBw'B/B).

Since v_0∈ W^J and u'∈ W_J, Lemma <ref> implies b_0v_0Bu'B⊆ Bv_0u'B.  Hence

    π^-1(xP_J)=b_0v_0⋃ Bu'B/B
 where the union is over all u'∈ W_J such that v_0u'≤ w.


The next lemma is from <cit.>.


Let w=vu be a parabolic decomposition with respect to J.  Then the following are equivalent:



  * The decomposition w=vu is a BP decomposition.

  * The fibers of the map π:X(w)→ X^J(v) are isomorphic to X(u).

  * The fibers of the map π:X(w)→ X^J(v) are equidimensional.



Clearly part (2) implies part (3), so we focus on showing part (1) implies part (2) and part (3) implies part (1).  Let xP_J∈ X^J(v) and write x=b_0v_0 for some b_0∈ B and v_0∈[e,v]^J.  If w=vu is a BP decomposition, then Theorem <ref> part (3) implies that v_0u'≤ w if and only if u'≤ u.  Lemma <ref> implies that the fiber

    π^-1(xP_J)=b_0v_0⋃_u'≤ uBu'B/B=b_0v_0X(u)

and hence all fibers of π are isomorphic to X(u).

Now suppose all the fibers of π are the same dimension.  Then Lemma <ref> implies the fiber over the identity is π^-1(eP_J)=X^J(u') where u' denotes the maximal element of [e,w]∩ W_J.  Similarly, we have the fiber over vP_J is π^-1(vP_J)=vX^J(u).  Since the fibers are equidimensional, we have ℓ(u')=ℓ(u).  But u≤ u' and hence u=u'.  Thus w=vu is a BP decomposition.


What remains to be proved is that when w=vu is a BP-decomposition, then the map π:X(w)→ X^J(v) is locally trivial and hence a X(u)-fiber bundle.  We first need the following lemma which is proved in <cit.>.


Let v∈ W^J and let I=S(v) denote the support set of v.  Let G_I⊆ G denote the Levi subgroup of P_I.  Let P_I,J:=G_I∩ P_J and B_I:=G_I∩ B denote the corresponding Borel and parabolic subgroups of G_I.

Then the inclusion i:G_I/P_I,J↪ G/P_J induces an isomorphism

    i:X_I^I∩ J(v)→ X^J(v)

where the Schubert variety 
    X_I^I∩ J(v):=B_IvP_I,J/P_I,J⊆ G_I/P_I,J.



We can now prove the main theorem of the section.


First observe that if π:X(w)→ X^J(v) is a locally-trivial fiber bundle, then the fibers are equidimensional and hence w=vu is a BP-decomposition by Lemma <ref>.

Now suppose that w=vu is a BP-decomposition and let I=S(v).  Lemma <ref> implies the fibers of the map π are all isomorphic to X(u) and hence we only need to show local triviality.  Lemma <ref> states that the inclusion i:G_I/P_I,J↪ G/P_J restricts to an isomorphism i:X_I^I∩ J(v)→ X^J(v).  The map G_I→ G_I/P_I,J is locally trivial and thus has local sections.  Hence for any x∈ X^J(v), there exists a Zariski open neighborhood U_x⊆ X^J(v) with a local section s:U_x→ G_I⊆ G.  Define the multiplication map

    m:U_x× X(u)→ G/B

by m(x',y):=s(x')· y.  We claim that the image of m lies in the Schubert variety X(w).  Let x'∈ U_x⊆ X^J(v) and hence x'∈ Bv_0P_J for some v_0≤ v.  Thus we can write s(x')=b_0v_0p_0 for some b_0∈ B_I:=G_I∩ B and p_0∈ P_I,J.  Since w=vu is a BP-decomposition, Theorem <ref> implies that I∩ J⊆ D_L(u).  Since P_I,J⊆ P_I∩ J=BW_I∩ JB, Lemma <ref> implies p_0X(u)=X(u).  Hence

    m(x',X(u))=b_0v_0p_0X(u)=b_0v_0X(u)⊆ X(v_0u)⊆ X(w).

Consider the commuting diagram:
    
    U_x × X(u) [r]^m[d]     X(w) [d]^π
    
                        U_x   @^(->[r]     X^J(v)

and note that the map m identifies (x',X(u)) with the fiber π^-1(x').  For any z∈π^-1(U_x), let g_z:=s(π(z))∈ G_I.  Then z↦ (π(z), g_z^-1z) maps π^-1(U_x) to U_x× X(u) and is, in fact, the inverse of m.   This implies the map m is an algebraic isomorphism and hence π is locally trivial.



One consequence of Theorem <ref>, is the following cohomological interpretation of BP decompositions.  For any variety X, let H^*(X) denote its singular cohomology with complex coefficients.


The decomposition w=vu is a BP decomposition with respect to J if and only if

    H^*(X(w)≃ H^*(X^J(v))⊗ H^*(X^*(u))

as H^*(X^J(v))-modules.



If w=vu is a BP decomposition, then Equation (<ref>) follows from Theorem <ref> and the Leray-Hirsch theorem.  Conversely, recall that 
    P_w(q^2)=∑_i^2ℓ(w)(H^i(X(w))  q^i  and  
    P^J_v(q^2)=∑_i^2ℓ(v)(H^i(X^J(v))  q^i.

If Equation (<ref>) holds, then w=vu is a BP decomposition since P_w(q)=P^J_v(q)· P_u(q).


We give some remarks about the fibers if π when w=vu is not necessarily a BP decomposition.  The union describing general fibers in Lemma <ref> is taken over all u' such that v_0u'∈ [e,w]∩ v_0W_J.  It is not difficult to see that this collection forms a lower order ideal in W_J.  In <cit.>, it is independently shown that these lower order ideals have unique maximal elements and hence are intervals in W_J.  This leads to the following corollary.


Let w=vu be a parabolic decomposition with respect to J and π:X(w)→ X^J(v).  Let xP_J∈ X^J(v) and write x=b_0v_0 for some b_0∈ B and v_0∈[e,v]^J.  Then

    π^-1(xP_J)=b_0v_0X(u_0)

where u_0 is the unique maximal element of the set v_0^-1([e,w]∩ v_0W_J).

Moreover, if u' denotes the maximal element of the set [e,w]∩ W_J, then u≤ u_0≤ u'.  If w=vu is a BP decomposition, then u=u_0=u'.



    Let G=_4().  Geometrically,  we have
    
    G/B={V_∙=(V_1⊂ V_2⊂ V_3⊂^4) |  V_i=i}.

    Let E_∙ denote the flag corresponding to eB and  w=s_1s_2s_3s_2s_1.  Then
    
    X(w) = {V_∙ | (V_2∩ E_2)≥ 1}.

    We consider the geometric analogues of Examples <ref> and <ref>.
    
    First, if J={s_1,s_3}, then π(V_∙)=V_2 and 
    
    w=vu=(s_1s_3s_2)(s_3s_1)

    is a BP decomposition with respect to J as in Example <ref>.  In particular, the Schubert variety
    
    X^J(v)= {V_2 | (V_2∩ E_2)≥ 1}

    and the fibre over V_2 in the projection π:X^∅(w)→ X^J(v) is
    
    π^-1(V_2)={(V_1,V_3) | V_1⊂ V_2⊂ V_3} X(u)ℂℙ^1×ℂℙ^1.

    
    If J={s_1,s_2}, then π(V_∙)=V_3 and 
    w=vu=(s_1s_2s_3)(s_2s_1)
 is not a BP decomposition as in Example <ref>.  The fiber over V_3 is given by
    
    π^-1(V_3)   ={(V_1,V_2) | V_1⊂ V_2⊂ V_3
             and (V_2∩ E_2)≥ 1}
        X(s_2s_1)    if  (V_3∩ E_2)=1
    
                                 X(s_1s_2s_1)    if   E_2 ⊂ V_3

    Note that the fibres are not equidimensional.


    

Combinatorially, Corollary <ref> says that if w=vu is a parabolic decomposition with respect to J and u' denotes the maximal element of [e,w]∩ W_J, then for every v_0∈ [e,v]^J, the coset interval 

    [e,w]∩ v_0W_J≃ [e,u_0]

for some u≤ u_0≤ u'.  At the extremes, we have

    [e,w]∩ W_J≃ [e,u']  and   [e,w]∩ vW_J≃ [e,u].




 §.§ Relative BP decompositions

We finish this section by stating a relative version of Theorem <ref>.  In this case, we have two parabolic subgroups P_J⊆ P_K⊆ G corresponding to subsets J⊆ K⊆ S.  Consider the projection 
    π:G/P_J→ G/P_K
 and we can ask the question: when does the map π induced a fiber bundle structure when restricted to the Schubert variety X^J(w)?  To answer to this equation, we define the relative version of a BP decomposition.  


Let J⊆ K⊆ S and w∈ W^J.  Let w=vu denote the parabolic decomposition with respect to K.  We say w=vu is a BP decomposition with respect to (J,K) if the Poincare polynomial factors 
    P_w^J(q)=P_v^K(q)· P_u^J(q).



Note that if J=∅, then this is the usual BP decomposition of w with respect to K.  We remark that relative BP decompositions are characterized by a similar list of conditions to those given in Theorem <ref>.  See <cit.> for a precise statement.


Let w∈ W^J and let w=vu be a parabolic decomposition with respect to (J,K).  Then the following are equivalent:

    
  * The decomposition w=vu is a BP decomposition with respect to (J,K).
    
  * The projection π:X^J(w)→ X^K(v) is a Zarisky-locally trivial with fiber X^J(u).


 

Theorem <ref> is proved in <cit.> and the proof is very similar to that of Theorem <ref>.


    Theorems <ref> and <ref> hold for the much larger class of Kac-Moody Schubert varieties.  Kac-Moody groups are infinite dimensional generalizations of Lie groups and include the family of affine Lie groups.  Their Weyl groups are (not necessarily finite) crystalographic Coxeter groups.  While the flag varieties of Kac-Moody groups are also infinite dimensional, their Schubert varieties are finite dimensional.  For more on Kac-Moody flag varieties and their Schubert varieties see <cit.>.




§ ITERATED BP DECOMPOSITIONS AND STAIRCASE DIAGRAMS


In this section, we discuss iterations of BP decompositions for Coxeter groups of finite type.  In particular, if (W,S) is a Coxeter system and J⊆ S, then each subgroup W_J has a unique longest element we denote by u_J.  We begin with the following definition.


We say a factorization 
    w=v_nv_n-1⋯ v_1
 is an iterated BP decomposition if (v_i+1)(v_i⋯ v_1) is a BP decomposition for each 1<i<n.


By Theorem <ref>, iterated BP decompositions correspond to iterated fiber bundle structures on Schubert varieties.  



 §.§ Staircase diagrams

In this section we combinatorially characterize iterated BP decompositions by objects called labelled staircase diagrams.  Staircase diagrams are certain partially ordered sets over a given graph and were introduced by Richmond and Slofstra in <cit.> with the goal of developing a combinatorial framework to study iterated BP decompositions.  We focus on staircase diagrams over the Coxeter graph of a Coxeter group.  The Coxeter graph is simply the Coxeter diagram of W without the edge labels and we denote this graph by Γ_W (See Figure <ref>). In other words, Γ_W is a graph with vertex set S and edge set {(s,t)∈ S^2  | m_st≥ 3}.  Note that the Coxeter groups of types A_n and B_n/C_n all have the same underlying Coxeter graph.  

Before stating the definition of a staircase diagram, we need some terminology.  Given s,t∈ S, we say s is adjacent to t if (s,t) is an edge in Γ_W.  We say a subset B⊂ S is connected if the induced subgraph of B in Γ_W is connected.  If  is a collection of subsets of S and s∈ S, we define

    _s:={B∈ | s∈ B}.

In other words, _s are the elements in  that contain s∈ S.


Let (W,S) denote a Coxeter system and let  be a collection of subsets of S.  We say a partially ordered set (,≺) is a staircase diagram if the following hold:


  * Every B∈ is connected, and if B covers B', then B∪ B' is connected.

  * The subset _s is a chain for every s∈ S.

  * If s is adjacent to t, then _s∪_t is a chain, and _s and _t are saturated subchains of _s∪_t.

  * For every B∈, there exists s∈ S (resp. s'∈ S) such that B is the minimum in _s (resp. maximum in _s').



If the generating set S={s_1,…, s_n}, then we use interval notation 
    [s_i,s_j]:={s_i,s_i+1,…,s_j}
 for i≤ j.  In type A_n, we have the Coxeter graph
  
    [scale=.4]
        [thick] (0,0)–(2,0)–(4.25,0)–(6.5,0);
        [thick,fill=white] (0,0) circle (.3cm) node[label=[label distance=.1cm]-90:s_1] ;
        [thick,fill=white] (2,0) circle (.3cm) node[label=[label distance=.1cm]-90:s_2];
        [white, fill=white] (4.25,0) circle (.75cm);
         (4.25,0) node ⋯;
        [thick,fill=white] (6.5,0) circle (.3cm) node[label=[label distance=.1cm]-90:s_n];

An example of staircase diagram in this type is

    ={[s_1,s_3]≺ [s_2,s_4]≺ [s_3,s_5]≻ [s_6]≻ [s_7,s_9]≺ [s_9,s_10]≺[s_10,s_11]}.

In this example, the set _s_3={[s_1,s_3], [s_2,s_4], [s_3,s_5]}.   In Figure <ref>, we represent this staircase diagram with a picture of uneven steps where “higher steps" are greater in the partial order:



Since elements of a staircase diagram are connected, we will refer to them as “blocks".  Note the blocks may not necessarily be ordered intervals.  In type D_5, we have Coxeter graph

    [scale=.4]
        [thick] (0,0)–(2,0)–(4,0)–(6,0);
        [thick] (2,0)–(2,2);
        [thick,fill=white] (0,0) circle (.3cm) node[label=[label distance=.1cm]-90:s_2] ;
        [thick,fill=white] (2,0) circle (.3cm) node[label=[label distance=.1cm]-90:s_3];
        [thick,fill=white] (4,0) circle (.3cm) node[label=[label distance=.1cm]-90:s_4];
        [thick,fill=white] (6,0) circle (.3cm) node[label=[label distance=.1cm]-90:s_5];
        [thick,fill=white] (2,2) circle (.3cm) node[label=[label distance=.1cm]0:s_1];

with examples of staircase diagrams in Figure <ref>.



In Figure <ref>, we give some non-examples of staircase diagrams.  The first diagram is of type A_6 violates parts (3) and (4) of Definition <ref>.  The second diagram is of type D_5 and violates part (2) of Definition <ref>.  



It is not hard to check that Definition <ref> is symmetric with respect to the partial order.  Given a staircase diagram , we can define the dual staircase diagram () to be the set  with the reverse partial order.  Pictorially this corresponds to “flipping" the staircase from top to bottom:




If ' is a saturated subset of , then the induced partial order on ' makes it a staircase diagram.  In this case, we say ' is a subdiagram of .
For any J⊆ S, define

    _J:={B∈ |  J⊆ B}.

The following lemma describes some combinatorial properties of staircase diagrams.

Let  be a staircase diagram of a Coxeter system (W,S).  Then:


  * For any J⊆ S, the set _J is a chain in .

  * If B,B'∈, then B⊈ B'.

  * If B,B'∈ and B∪ B' is connected, then B and B' are comparable.




Part (1) follows from the fact that _J is the intersection of _s where s∈ J and each _s is a chain. 

For part (2), select s, s'∈ S such that B is the maximal and minimal block of _s and _s' respectively.  Then _{s,s'} consists only of B.  If B⊆ B', then B'∈_{s,s'} and hence B=B'.  

For part (3), if B∪ B' is connected, then there exist s∈ B and t∈ B' such that s is adjacent to t.  Thus B,B' belong to the chain _s∪_t and hence B,B' are comparable.





 §.§ Labellings of staircase diagrams


Staircase diagrams provide the framework for building iterated BP decompositions.  Let  be a staircase diagram.  For any B∈, define the sets


    J_R(B):=B∩(⋃_B'≺ B B')  and   J_L(B):=B∩(⋃_B'≻ B B').


Pictorially, we can think of the set J_R(B) as the elements of B that are “covered below" by other blocks in  and J_L(B) as the elements of B that are “covered above".  For example, if 
    ={[s_1,s_3]≺ [s_2,s_6]≻ [s_6,s_7]}

then 
    J_R([s_2,s_6])={s_2,s_3,s_6}

which we highlight in Figure <ref>.



We define a labelling of a staircase diagram which assigns a Coxeter group element to each block in .  For any J⊆ S, we let u_J denote the longest element of W_J.


Let  be a staircase diagram on a Coxeter system (W,S).  We say a function

    λ:→ W

is a labelling of  if for every B∈, we have


  * J_R(B)⊆ D_R(λ(B)),

  * J_L(B)⊆ D_L(λ(B)), and

  * S(λ(B)u_J_R(B))=B=S(u_J_L(B)λ(B)).

We denote a labeled staircase diagram by the pair (,λ).




The function λ:→ W given by λ(B)=u_B is a labelling of .  This labelling is called the maximal labelling of .


Note that while staircase diagrams of type A_n and B_n/C_n are the same, labelled staircase diagrams are different since they depend on the group W and not just the underlying graph Γ_W.
The definition of a labelling is compatible with the dual of staircase diagram.  For any labeled staircase diagram (,λ), define the inverse labelling

    λ^-1:()→ W

by λ^-1(B):=λ(B)^-1.  It is easy to check that ((),λ^-1) is also a labelled staircase diagram.  The condition J_R(B)⊆ D_R(λ(B)) implies that λ(B)u_J_R(B) is the minimal right coset representative of λ(B) in W^J_R(B).   Similarly, we have that u_J_L(B)λ(B) is a minimal left coset representative of λ(B).  These coset representatives play an important role in the next definition, so for any labelled staircase diagram (,Λ) and B∈, we define

    λ(B):=λ(B)u_J_R(B).


Given a labeled staircase diagram (,λ) define

    Λ(,λ):=λ(B_n)λ(B_n-1)⋯λ(B_1)

where B_1,…,B_n is some linear extension of the poset .  If the labelling λ is clear from the context, then we will denote Λ()=Λ(,λ).


By part (3) of Lemma <ref>, if B_i and B_j are not comparable, then λ(B_i) and λ(B_j) have commuting supports and hence commute as elements of W.  This implies that Λ() is independent of choice of linear extension and is well defined.


Let ={[s_1,s_3],[s_5,s_6],[s_2,s_5]} in type A_6.

    [scale=0.4]
        80,3,3,0,1,1,1,0,
            0,0,2,2,2,2,0,0,

Then

    λ([s_1,s_3])=s_1s_2s_3s_1s_2s_1,  λ([s_5,s_6])=s_5s_6s_5,


    λ([s_2,s_5])=(s_3s_2s_4s_3s_5s_4s_5s_2s_3s_2)(s_2s_3s_2s_5)=s_3s_2s_4s_3s_5s_4

and

    Λ()=(s_3s_2s_4s_3s_5s_4)(s_5s_6s_5)(s_1s_2s_3s_1s_2s_1).

Highlighted in red is the element u_{s_2,s_3,s_5} since J_R([s_2,s_5])={s_2,s_3,s_5}.

Note that if λ:→ W is a maximal labelling, then λ(B) is the maximal element W_B∩ W^J_R(B)
We define the support of  to be the set 
    S():=⋃_B∈ B.
  Note that if λ:→ W is a labeling, then S()=S(Λ()).
Furthermore, since the support set

    S(λ(B_i-1)⋯λ(B_1))=B_1∪⋯∪ B_i-1

is disjoint with  B∖ J_R(B_i), the product

    λ(B_i)·(λ(B_i-1)⋯λ(B_1))

is a parabolic decomposition with respect to B_1∪⋯∪ B_i-1.
We will show that this decomposition is in fact a BP decomposition and thus the factorization of Λ() in Definition <ref> corresponds to an iterated BP decomposition.  The next lemma gives several properties on how the Coxeter theoretic data of the element Λ() is extracted from the combinatorial data of the staircase diagram .


Let (,λ) be a labeled staircase diagram.  Then the following are true:



  * Λ()^-1=Λ((), λ^-1).




  * The right descents of Λ() consist of all s∈ S() that satisfy:


  * min(_s)≼min(_t) for all t adjacent to s and

  * s is a right descent of λ(min(_s)).





  * The left descents of Λ() consists of all s∈ S() that satisfy:


  * max(_s)≽max(_t) for all t adjacent to s and

  * s is a left descent of λ(max(_s)).





  * Let ' be a lower order ideal in  and let ”:=∖.  Then

    Λ()=(Λ(”)u_K)·Λ(')

is a parabolic decomposition with respect to S(') where 
    K={s∈ S | min(”_s)≠min(_s)}.




The proof of Lemma <ref> is technical, so we refer the reader to <cit.> for more details.  Observe that part (3) follows from parts (1) and (2).


Let  be a staircase diagram with a linear extension B_1,…,B_n.  For i≥ 2, let ^i denote the subdiagram

    ^i:={B_1,…,B_i-1}.

If λ is a labelling of , then

    Λ(^i+1)=λ(B_i)·Λ(^i)

is a BP decomposition with respect to S(^i).




Lemma <ref> part (4) implies λ(B_i)·Λ(^i) is a parabolic decomposition, so it suffices to show that the decomposition satisfies the BP condition in Theorem <ref> part (4).  First observe that

    S(λ(B_i))∩ S(^i)=B_i∩ S(^i)=J_R(B_i).

Thus λ(B_i)·Λ(^i) is a BP decomposition if and only if J_R(B_i)⊆ D_L(Λ(^i)).  Let s∈ J_R(B_i).  We use the characterization given in Lemma <ref> part (3) to show that s∈ D_L(Λ(^i)) .   Suppose that t∈ S(^i) is adjacent to s.   Observe that if B_j the predecessor of B_i in the chain _s, then B_j=max(^i_s).  By definition of staircase diagram, _s is a saturated subchain of the chain _s∪_t.  Since B≼ B_i for all B∈^i, it follows that max(^i_t)≼ B_j.  By Lemma <ref>, it remains to show that s∈ D_L(λ(B_j)).  Since s∈ B_i∩ B_j, we have s∈ J_L(B_j) and, by the definition of a labelling, J_L(B_j)⊆λ(B_j).  Thus s∈ D_L(Λ(^i)) which completes the proof.




 §.§ Complete BP decompositions


In this section we discuss a special class of decompositions called complete BP decompositions.  We start with the following definition which was introduced in Section <ref>.


A BP composition w=vu with respect to J is a Grassmannian BP decomposition if |J|=|S(w)|-1.  In other words, J is maximal proper subset of S(w).


Geometrically, Grassmannian BP decompositions correspond to projections π: G/B→ G/P where P is taken to be a maximal parabolic.  In the classical type A setting this partial flag variety G/P corresponds to a Grassmannian variety.  If w=vu is a Grassmannian BP decomposition, then Theorem <ref> implies the Schubert variety X(w) is an X(u)-fiber bundle over the Grassmannian Schubert variety X^J(v).  Note that the decompositions that arise in Theorems <ref> and <ref> are Grassmannian BP decompositions.


Let n=|S(w)|.  We say 
    w=v_nv_n-1⋯ v_1
 is a complete BP decomposition if (v_i+1)(v_i⋯ v_1) is a Grassmannian BP decomposition for each 1≤ i<n.


Complete BP decompositions are iterated BP decompositions where the number of non-trivial factors is maximized in the sense that each iteration adds exactly one additional generator to the support set of w.  For example, in type A_3, we have that 
    w=(s_1s_2s_3)(s_1s_2)(s_1)
 is a complete BP decomposition of the longest element.  Note that these decompositions are not unique.  For w above, the decomposition

    w=(s_2s_1s_3s_2)(s_1)(s_3)

is also a complete BP decomposition.  The goal of this section is to classify which elements w∈ W that have complete BP decompositions.  The key to this classification is the notion of nearly-maximal elements.


We say an element w∈ W is nearly-maximal if there is a Grassmannian BP decomposition w=vu such that S(u)⊂ S(v).

Furthermore, we say a labelled staircase diagram (,λ) is nearly-maximal if each B∈, λ(B) is nearly-maximal.


If w=vu is nearly-maximal, then 
    S(u)⊆ S(v)∩ J⊆ D_L(u)
 
and hence S(u)=D_L(u).  This implies that u is the maximal element of W_J.  Geometrically, this corresponds to the fiber X(u) being isomorphic to the flag variety P_J/B.  Not all Grassmannian BP decompositions satisfy the nearly-maximal condition.  For example, in type A_4, 
    w=(s_1s_2)(s_1s_3s_4)

is Grassmannian BP decomposition with respect to J={s_1,s_3,s_4}, but w is not nearly maximal.  Note that the maximal labelling of a staircase diagram is nearly-maximal.  The importance of nearly-maximal labelings is that they can used to construct complete BP decompositions.  In fact, this construction will yield the following bijection:


Let W be a Coxeter group.  Then the map (,λ)↦Λ() defines a bijection between staircase diagrams over W with a nearly-maximal labelling λ, and elements of W with a complete BP decomposition.



First note by Theorem <ref> and Definition <ref>, if λ is a nearly maximal labelling of , then Λ() has a complete BP-decomposition and thus the map (,λ)↦Λ() is well defined.

To show that the map is injective, suppose we have two nearly-maximal labelled staircase diagrams (_1,λ_1) and (_2,λ_2) such that Λ(_1)=Λ(_2).  Choose s∈ S such that Λ(_i)=vu is a BP decomposition with respect to J=S∖{s}.  It can be shown that B:=S(v) is a maximal block of _i and hence, by induction on the number of blocks, _1=_2.  To show that λ_1=λ_2, note that, by Lemma <ref> part (1), the parabolic decomposition of Λ(_i)^-1 with respect to B is given by
 
    Λ(_i)^-1=v'·λ_i(B)^-1

 for some v' and thus λ_1(B)=λ_2(B).  We also have
 
    J_R(B,_i)=B∩ S(_i∖{ B})=B∩ S(λ_i(B)·Λ(_i))

 and hence J_R(B,_1)=J_R(B,_2).
This implies λ_1(B)=λ_2(B).  Since Λ(_1)=Λ(_2) and λ_1(B)=λ_2(B), we have that the induced labelling on lower order ideals satisfies Λ(_1∖{B})=Λ(_2∖{B}).  By induction on |_i|, we have that the labellings λ_1=λ_2.

To show that the map is surjective, suppose x∈ W has a complete BP decomposition x=v_n⋯ v_1.  By induction, suppose that (,λ) is a nearly-maximal labelled staircase diagram such that Λ()=v_n-1⋯ v_1.  Define the staircase diagram

    :=^0∪{S(v_n)}  where  ^0:={B∈ | B⊈ S(v_n)}

with the added covering relations max(^0_s)≺ S(v_n) for every s∈ S(^0) contained in, or adjacent to S(v_n).  It can be shown that  satisfies Definition <ref> of staircase diagram.  Finally, define the labelling λ̃:→ W by

    λ̃(B):=λ(B)    if B∈^0
      v_n· u_S(v_n)∩ S()   if B=S(v_n).

Again, it can shown that λ̃ is a nearly maximal labelling of  such that Λ(,λ̃)=x.  This completes the proof.


Next we apply Theorem <ref> to rationally smooth elements of Coxeter groups of finte Lie-type.  The following rephrasing of Theorem <ref>.


Let w∈ W be rationally smooth with |S(w)|≥ 2.  Then either w or w^-1 has a Grassmannain BP decomposition vu with respect to J=S(w)∖{s} such that s is a leaf in the Coxeter diagram of W_S(w) and vu_S(v)∩ J is nearly maximal.


The proof of Theorem <ref> follows from checking that the list of elements given in Theorem <ref> all satisfy the definition of nearly maximal given in Definition <ref>.  We remark that there exist nearly maximal elements that are not rationally smooth.  Hence Theorem <ref> is slightly weaker statement than Theorem <ref>.  In <cit.>, Richmond and Slofstra define the stronger condition of “almost-maximal" to make these theorems equivalent.  Our next goal is to give an outline of a proof of Theorem <ref> which states that rationally smooth elements always have Grassmannian BP decompositions.


Let w∈ W be (rationally) smooth.  Then there exists a Grassmannian BP decomposition w=vu with respect to some maximal proper subset J=S(w)∖{s}.

Moreover, u is (rationally) smooth and v is (rationally) smooth with respect to J.



First note that if w=vu is a BP decomposition, then Theorem <ref> implies that if X(w) is (rationally) smooth, then both X(u) and X^J(v) are also (rationally) smooth.  

Recall that Theorem <ref> states that if w is rationally smooth, then either w or w^-1 has a Grassmannian BP decomposition with respect to J=S(w)∖{s} for some leaf s∈ S(w) in the Coxeter diagram of W_S(w).  If w has such a BP decomposition, then the theorem is proved.  Now suppose w^-1 has such a BP decomposition and hence we can write w=uv where u∈ W_J and v^-1∈ W^J and w^-1=v^-1u^-1 is a Grassmannian BP decomposition with respect to J=S(w)∖{s}.  Since w is (rationally) smooth, we have that w^-1 is (rationally) smooth and hence u, u^-1 are also (rationally) smooth.  Since |S(u)|<|S(w)|, we can inductively assume that there exists a Grassmannian BP decomposition u=v'u' with respect to some maximal proper set J'=J∖{s'}.  It can shown that s'∈ J can be selected appropriately so that

    w=v'(u'u)
 is a Grassmannian BP decomposition with respect to S(w)∖{s'}.



If w∈ W is (rationally) smooth, then w has a complete BP-decomposition.  In particular, there exists a staircase diagram  over W and nearly-maximal labelling λ such that Λ()=w.


We say a nearly maximal labelling λ:→ W is (rationally) smooth if Λ() is (rationally) smooth.  In fact, if λ is rationally smooth, then for each B∈, the element λ(B) must correspond to one of the elements in the list found in Theorem <ref>.  In particular, if W is simply laced, then λ must be the maximal labelling.  This implies the following corollary.


Let W be a simply laced of finite type.  Then there is a bijection between staircase diagrams over Γ_W and smooth elements of W.



Let  be a staircase diagram and let λ:→ W denote the maximal labeling.  Then the Schubert variety X(Λ()) is an iterated fiber bundle of smooth Schubert varieties and hence smooth.  Conversely, if X(w) is smooth, then Theorem <ref> and Corollary <ref> imply there is a unique smoothly labelled staircase diagram (,λ) such that Λ()=w.  Since W is simply laced, Theorem <ref> implies λ is the maximal labelling.




 §.§ Enumerating smooth Schubert varieties

An application of Theorem <ref> and Corollary <ref> is that we can enumerate smooth Schubert varieties by counting staircase diagrams.  We give an overview of this enumeration in type A.  Recall that the Coxeter graph of type A_n is a path on n vertices:

    [scale=.4]
        [thick] (0,0)–(2,0)–(4.25,0)–(6.5,0);
        [thick,fill=white] (0,0) circle (.3cm) node[label=[label distance=.1cm]-90:s_1] ;
        [thick,fill=white] (2,0) circle (.3cm) node[label=[label distance=.1cm]-90:s_2];
        [white, fill=white] (4.25,0) circle (.75cm);
         (4.25,0) node ⋯;
        [thick,fill=white] (6.5,0) circle (.3cm) node[label=[label distance=.1cm]-90:s_n];

We will denote this graph by Γ_n.


Let a_n denote the number of staircase diagrams over Γ_n (equivalently, the number of smooth permutations in _n+1) and define the generating function

    A(x):=∑_n=0^∞ a_n  t^n.

Then

    A(x)=1-5t+4t^2+t√(1-4t)/1-6t+8t^2-4t^3.


A proof of Theorem <ref> first appeared in an unpublished paper by Haiman <cit.>.  The first published proof of Theorem <ref> is due to Bousquet-Mélou and Butler in <cit.>.  In this section, we provide an alternate proof using staircase diagrams from <cit.> and <cit.>.
We first focus on diagrams that are chains.  

We say a staircase diagram  is increasing over Γ_n if  is fully supported (i.e. S()={s_1,…,s_n}) and if for every B,B'∈ such that s_i∈ B and s_j∈ B' with i<j, we have B≼ B'.   Pictorially, increasing staircase diagrams are represented by a sequence of blocks that are “going up" from left to right with no gaps.  For example, ={[s_1,s_2]≺ [s_2,s_5]≺ [s_4,s_6]} is increasing over Γ_6 as in Figure <ref>.   We say that  is decreasing over Γ_n if () is increasing over Γ_n.




The number of increasing staircase diagrams over Γ_n is the n-th Catalan number.



We show that increasing staircase diagrams over Γ_n are in bijection with Dyck paths.  Let 
    ={B_1≺ B_1≺⋯≺ B_m}
 be such a diagram.  For each B_i∈ define

    r(B_i):=#{s∈ B_i∖ B_i-1}    and    
        u(B_i):=#{s∈ B_i∖ B_i+1}

where we set B_0=B_m+1=∅.  Let P() denote the lattice path in ^2 from (0,0) to (n,n) which takes r(B_1) steps to the right, then u(B_1) steps going up, followed by r(B_2) steps to the right, then u(B_2) steps going up and so forth (See Example <ref>).  It is easy to check that P() is a Dyck path that stays below the diagonal in ^2.  One can also check that the map P is invertible and hence a bijection.



    Consider the staircase diagram =(s_1≺[s_2,s_5]≺[s_4,s_6]) on Γ_6.  The sequence of pairs (r(B_i),u(B_i)) is ((1,1),(4,2),(1,3)) and corresponding Dyck path P() is given in Figure <ref>.



We use the enumeration of increasing staircase diagrams as the starting point to enumerate general staircase diagrams of type A.  The next step is to decompose staircase diagram with connected support into a smaller staircase diagram and an increasing/decreasing “diagram" as follows:



Note that second part of the decomposition in Figure <ref> may not be a valid staircase diagram which leads to the following definition.  First, we set Γ_n⊆Γ_n+1 as a subgraph by removing the vertex s_1 (See Figure <ref>).


We say a  is an increasing (decreasing) broken staircase diagram over Γ_n if we can write 
    ={B∩ [s_2,s_n]  | B∈'}

where ' is some increasing (decreasing) staircase diagram over Γ_n+1.  




Let b_n denote the number of increasing (equivalently decreasing) broken staircase diagrams over Γ_n.  Then b_n=c_n+1-c_n where c_n denotes the n-th Catalan number.



Let ={B_1≺ B_2≺⋯≺ B_k} be an increasing staircase diagram over Γ_n+1 and let

    ():={B∩[s_2,s_n] | B∈}

denote the corresponding broken staircase diagram over Γ_n.  By Lemma <ref>, the number of increasing staircase diagrams over Γ_n+1 is c_n+1.  We prove the lemma by determining the pre-images of the map .  First note that since  is increasing, we have that s_1∈ B_i if and only if i=1.  Hence B_i∩[s_2,s_n]=B_i unless i=1 and the pre-image of B is determined by the changes on B_1.  Now if B_1∩[s_2,s_n]⊂ B_2∩ [s_2,s_n], then () is uniquely determined by  as in Figure <ref>.


Otherwise, () has two pre-images as in Figure <ref>.

Broken staircase diagrams over Γ_n with two pre-images under the map  can be identified with increasing staircase diagrams over Γ_n via the second pre-image in Figure <ref>.  The Lemma now follows from Lemma <ref>.



We first note that the generating function for Catalan numbers is given by

    (t):=∑_n=0^∞ c_n  t^n=1-√(1-4t)/2t

and by Lemma <ref>, the Catalan number c_n denotes the number of increasing staircase diagrams over Γ_n.  Recall the b_n denotes the number of increasing broken staircase diagrams over Γ_n and let 
    (t):=∑_n=0^∞ b_n  t^n.

Lemma <ref> implies that

    t+t(t)=(t)-t(t).

Now suppose  is a fully supported staircase diagram over Γ_n.  Then either  is increasing on Γ_n or  decomposes, as in Figure <ref>, into a smaller fully supported staircase diagram and a broken staircase diagram (note that this second case includes decreasing diagrams).
Let a̅_n denote number of fully supported staircase diagrams over Γ_n and define

    A(t):=∑_n=0^∞a̅_n  t^n.
  We now have

    A(t)=(t)+A(t)·(t).

Finally, any staircase diagram is a disjoint union of fully supported staircase diagrams and hence

    A(t)=1+A(t)/1-t-tA(t).

The theorem follows from combining Equations (<ref>), (<ref>), (<ref>), and (<ref>).


One advantage of using staircase diagrams to enumerate smooth elements is that the techniques can extended to calculate generating functions for smooth and rationally smooth elements of other families of Coxeter groups.  Define the generating series

    B(t):=∑_n=0 b_n t^n,  C(t):=∑_n=0 c_n t^n, D(t):=∑_n=3 d_n t^n, and BC(t):=∑_n=0 bc_n t^n

where b_n,c_n,d_n denote number of smooth elements of type B_n, C_n, D_n respectively and bc_n denotes the number of rationally smooth elements of type B_n/C_n.   The following theorem is one of the main results of <cit.>.


    Let W(t) := ∑_n w_n  t^n denote one of the above generating series,
    where W = A, B, C, D or BC.  Then
    
    W(t)=P_W(t)+Q_W(t)√(1-4t)/(1-t)^2(1-6t+8t^2-4t^3)

    where P_W(t) and Q_W(t) are polynomials given in Table <ref>.




The proof of Theorem <ref> involves enumerating staircase diagrams similar fashion to the proof of Theorem <ref>.  For type D, we can apply Corollary <ref>.  Since types B and C are not simply-laced, we need to consider (rationally) smooth labellings of staircase diagrams that are not the maximal labelling.  These additional labellings are characterized by Theorem <ref> parts (1a) and (1b).






§ BP DECOMPOSITIONS AND PATTERN AVOIDANCE


In this section we give an overview of how permutation pattern avoidance is related to BP decompositions.  Here we will only consider permutation groups (type A).  Recall that _n is permutation group on [n]={1,…, n}.  The permutation group _n is generated by the set of simple transpositions S={s_1,…, s_n-1} where s_i denotes the transposition swapping i and (i+1) and with the relations

    s_i^2=(s_is_j)^2=(s_is_i+1)^3=e  for all |i-j|>1.

Any w∈_n has a unique expression in one-line notation w=w(1)⋯ w(n).  We use matrices to represent permutations with nodes marking the points (w(i),i) using the convention that (1,1) marks the upper left corner.  For example, w=3241 corresponds to the matrix:


    [scale=0.4]
    [step=1.0,black] (0,0) grid (3,3);
     (0,1) circle (7pt);
     (1,2) circle (7pt);
     (2,0) circle (7pt);
     (3,3) circle (7pt);


Let u∈_k and w∈_n.  We say w contains the pattern u if there exists a subsequence (i_1<⋯<i_k) such that w(i_1)⋯ w(i_k) has the same relative order as u(1)⋯ u(k).  If no such sequence exists, we say that w avoids the pattern u.  For example, in Figure <ref>, we see that w=416253 contains the pattern 3412, but avoids the pattern 1234.



Permutation pattern avoidance has been used to characterize many geometric properties of Schubert varieties of type A.  A survey of these results can be found at <cit.>.  Most notably, Lakshmibai and Sandhya prove that a Schubert variety X(w) is smooth if and only if w avoids the patterns 3412 and 4231 in <cit.>.  Combining this result with Corollary <ref>, we have the following theorem:


  If the permutation w avoids the patterns 3412 and 4231, then w has a complete BP decomposition.


    [scale=0.4]
    [step=1.0,black] (0,0) grid (3,3);
     (0,1) circle (7pt);
     (1,0) circle (7pt);
     (2,3) circle (7pt);
     (3,2) circle (7pt);
     (1.5,-2) node 3412;
    [scale=0.4]
    [step=1.0,black] (0,0) grid (3,3);
     (0,0) circle (7pt);
     (1,2) circle (7pt);
     (2,1) circle (7pt);
     (3,3) circle (7pt);
     (1.5,-2) node 4231;




The geometric version of Theorem <ref> states that smooth Schubert varieties of type A are iterated fiber bundles of Grassmannian varieties.  This geometric result was proved by Ryan in <cit.>.  Wolper gives an analogous result for Schubert varieties over algebraically closed fields in characteristic zero in <cit.>.   Note that it is not necessary for w to avoid 3412 and 4231 for w to have a complete BP decomposition.  In fact, if w=4231, then

    w=(s_1s_3s_2)(s_3)(s_1)

is a complete BP decomposition of w.  The following theorem from <cit.> is a precise pattern avoidance characterization of permutations that have complete BP decompositions.


  The permutation w avoids the patterns 3412, 52341, and 635241 if and only if w has a complete BP decomposition.

    [scale=0.4]
    [step=1.0,black] (0,0) grid (3,3);
     (0,1) circle (7pt);
     (1,0) circle (7pt);
     (2,3) circle (7pt);
     (3,2) circle (7pt);
    [scale=0.4]
    [step=1.0,black] (0,0) grid (4,4);
     (0,0) circle (7pt);
     (1,3) circle (7pt);
     (2,2) circle (7pt);
     (3,1) circle (7pt);
     (4,4) circle (7pt);
    [scale=0.4]
    [step=1.0,black] (0,0) grid (5,5);
     (0,0) circle (7pt);
     (1,3) circle (7pt);
     (2,1) circle (7pt);
     (3,4) circle (7pt);
     (4,2) circle (7pt);
     (5,5) circle (7pt);


    3412 52341 635241





 §.§ Split pattern avoidance


The proof of Theorem <ref> relies on the idea of split pattern avoidance which is used to characterize Grassmannian BP decompositions of permutations with respect to J=S∖{s_r} for any s_r∈ S. 

A split pattern w=w_1|w_2∈_n is a divided permutation with 
    w_1=w(1)⋯ w(j)  and   w_2=w(j+1)⋯ w(n)
 for some 1≤ j<n.


Let k≤ n and r<n.  Let w∈_n and let 
    u=u(1)⋯ u(j)|u(j+1)⋯ u(k)
 denote a split pattern.  We say w contains the split pattern u with respect to position r if there exists a sequence (i_1<⋯<i_k) such that



  * w(i_1)⋯ w(i_k) has the same relative order as u.

  * i_j≤ r<i_j+1.

Otherwise, we say the permutation w avoids the split pattern u with respect to position r.

In other words, w contains u=u_1|u_2 if it contains u in the usual sense of pattern containment, but with the extra condition that u_1 appears to the right of the r-th position and u_2 to the left of the r-th position in the one-line notation of w.  For example w=416253 contains the split pattern 3|412 with respect to positions r=1,2 but avoids 3|412 with respect to r=3,4,5 (See Figure <ref>).



The next theorem is from <cit.> and completely characterizes Grassmannian BP decompositions in terms of split pattern avoidance.


  Let r<n and w∈_n.  Then w has a Grassmannian BP decomposition with respect to J=S∖{s_r} if and only if w avoids the split patterns 3|12 and 23|1 with respect to position r.

    [scale=0.4]
    [step=1.0,black] (0,0) grid (2,2);
     (0,0) circle (7pt);
     (1,2) circle (7pt);
     (2,1) circle (7pt);
    [dashed,thick, red] (0.5,-1)–(0.5,3);
     (1,-2) node 3|12;[scale=0.4]
    [step=1.0,black] (0,0) grid (2,2);
     (0,1) circle (7pt);
     (1,0) circle (7pt);
     (2,2) circle (7pt);
    [dashed,thick, red] (1.5,-1)–(1.5,3);
     (1,-2) node 23|1;




We use Theorem <ref> part (4) which states that a parabolic decomposition w=vu with respect to J is a BP decomposition if and only if S(v)∩ J⊆ D_L(u).  The next lemma gives an explicit description of these ideas in terms of the one-line notation of permutations.  We leave the proof as an exercise.  


Let w∈_n and r<n and write

    w=w_1|w_2=w(1)⋯ w(r)|w(r+1)⋯ w(n).


Let w=vu denote the parabolic decomposition with respect to J=S∖{s_r}.  Then the following are true:



  * v=v_1|v_2 where v_1 and v_2 respectively consist the entries in w_1 and w_2 arranged in increasing order and

    S(v)={s_k∈ S  | v(r+1)≤ k<v(r)}.


  * u=u_1|u_2 where u_1 and u_2 are respectively the unique permutations on {1,…,r} and {r+1,…,n} with relative orders of w_1 and w_2 and 
    D_L(u)={s_k∈ S  | u^-1(k+1)<u^-1(k)}.




The description of the decent set in part (2) of Lemma <ref> is equivalent to saying that s_k is a left descent of u if and only if the node in the k-th row is to the right of the node in the (k+1)-th row in the permutation matrix of u.  The proof of Theorem <ref> follows from showing that avoiding the split patterns 3|12 and 23|1 with respect to position r is equivalent to S(v)∖{s_r}⊆ D_L(u) using Lemma <ref>.  We illustrate this connection with the following examples:

Let w=17264|5938 and note that w avoids 3|12 and 23|1 with respect to position r=5.  If w=vu is the parabolic decomposition with respect to J=S∖{s_5}, then v=12467|3589 and u=15243|7968 as seen in Figure <ref>.  Lemma <ref> says that 

    S(v)∖{s_5}={s_3,s_4,s_6}  and   D_L(u)={s_3,s_4,s_6,s_7}

and hence S(v)∖{s_5}⊆ D_L(u).



If we take the parabolic decomposition of w=1726|45938 with respect to J=S∖{s_4}, then w contains 3|12 with respect to r=4. In this case v=1267|34589 and u=1423|57968 (See Figure <ref>).  Lemma <ref> says that 

    S(v)∖{s_4}={s_3,s_5,s_6}  and   D_L(u)={s_3,s_5,s_7}

and hence S(v)∖{s_5}⊈ D_L(u).





We remark the an explicit formula for the number of permutations w∈_n which avoid 3|12 and 23|1 with respect to a given position r is calculated by Grigsby and Richmond in <cit.>.   The connection between Theorem <ref> and <ref> is the following proposition.


If w∈_n avoids the patterns 3412, 52341, and 635241, then there exists s_r∈ S(w) where w avoids the split patterns 3|12 and 23|1 with respect to position r.


One can prove Proposition <ref> by contradiction and we refer the reader to <cit.> for more details.


Proposition <ref> implies that if w∈_n avoids the patterns 3412, 52341, and 635241, then w has a Grassmannian BP decomposition w=vu with respect to some r<n. It can be shown that u also avoid these patterns and hence we can iterate this process yielding a complete BP decomposition of w.  For more details, see <cit.>.


If w avoids 3412, 52341, and 635241, then we can we construct complete BP decompositions of w by finding positions such that w avoids 3|12 and 23|1 and then iterating the process on factor u.


Observe that w=513462 avoids 3412, 52341, and 635241 and hence w has a complete BP decomposition.  Complete BP decompositions of w correspond to sequences of “splittings" along lines that avoid 3|12 and 23|1.  For example, we can split w along the sequence of positions (3,2,4,1,5) as in Figure <ref>.




Next we use Theorem <ref> to give a new proof of Gasharov's Theorem that Poincaré polynomials of smooth permutations are products of q-integers.  The following proposition is the “forward" direction of Theorem <ref>.


Let w∈_n.  If w avoids 3412 and 4231, then either w or w^-1 has a BP decomposition vu with respect to J=S∖{s_n-1} where

    P_w(q)=[ℓ(v)+1]_q· P_u(q)
 and u∈ W_J≃_n-1 also avoids 3412 and 4231.



We prove the proposition by contradiction.  Let w∈_n and assume w avoids 3412 and 4231.  For the sake of contradiction, suppose that both w and w^-1 do not have BP decompositions with respect to J=S∖{s_n-1}.  Theorem <ref> implies that both w and w^-1 contain the split pattern 23|1 with respect to position r=n-1.

Since w^-1 corresponds to the transpose of w, we consider a “horizontal" analogue of split pattern containment in Figure <ref>.  Note that it is not possible for either w or w^-1 to contain the other split pattern, 3|12, with respect to position r=n-1.  Let w(d)=n and w(n)=e and consider the matrix diagram of w where we mark the nodes (d,n) and (n,e) as in Figure <ref>.  These nodes divide the matrix into four regions of which we label three of them A,B, and C.


We have two cases to consider when containing the split pattern 23|1 both vertically and horizontally with respect to position r=n-1.  First, if either region A or B contain no nodes, then region C must contain 2 increasing nodes which implies that w contains 4231.  Otherwise, each of regions A and B must contain at least one node which implies w contains 3412 (See Figure <ref>).



In either case, we have a contradiction and hence at least one of w or w^-1 has a BP decomposition vu with respect to J.  The fact that u is smooth follows from Lemma <ref> part (2).  Since s_n-1 is a leaf in the Coxeter diagram of _n, the interval [e,v]^J is chain and hence P_v^J(v)=[ℓ(v)+1]_q.  This completes the proof.




 §.§ Related results on pattern avoidance

In this section by state two analogues of the following theorem which summarizes various characterizations of smooth permutations.


Let w∈_n.  Then the following are equivalent.


  * w avoids 3412 and 4231.

  * X(w) is an iterated fiber-bundle of Grassmannian varieties.

  * The interval [e,w] is rank symmetric.



Theorem <ref> follows from the combined works of Lakshmibai-Sandhya <cit.>, Ryan <cit.>, and Carrell <cit.>.   Note that Theorem <ref> can be viewed as analogue of the equivalence of parts (1) and part (2) in Theorem <ref> where we replace part (2) with an iterated fiber-bundle of Grassmannian Schubert varieties.  Each Grassmannian has a co-dimension one Schubert variety which is unique in the sense that, as a Weil divisor, it generates the Picard group of the Grassmannian.   We call this variety a Grassmannian Schubert divisor.  The following theorem is another analogue of the equivalence of parts (1) and (2) and is proved by Azam in <cit.>.


Let w∈_n.  Then the following are equivalent.

    
  * w avoids 3412, 52341, 52431, and 53241.
    
  * X(w) is an iterated fiber bundle of Grassmannian varieties or Grassmannian Schubert divisors.



The class of permutations in Theorem <ref> is larger than the smooth class of permutations, but within the class of permutations that have complete BP decompositions.  Note that Grassmannian Schubert divisors are almost always singular varieties.  One consequence of Theorem <ref> is that the generating function for permutations that avoid 3412, 52341, 52431, and 53241 can be calculated using labelled staircase diagrams.  This calculation uses “Catalan type" objects similar to those used to prove Theorem <ref>.  For more details see <cit.>.

The next theorem is a analogue of the equivalence of parts (1) and (3) in Theorem <ref>.  Given a poset P, the dual poset P^* is obtained by reversing the partial order.  We say P is self-dual if P≃ P^* as posets.  It is easy to check that any graded self-dual poset is rank symmetric.  However the converse may not be true. The next theorem is proved by Gaetz and Gao in <cit.>.


Let w∈_n.  Then the following are equivalent.


  * w avoids 3412, 4231, 34521, 45321, 54123, and 54312.  

  * The interval [e,w] is self-dual (as a poset).



The authors refer to permutations characterized in Theorem <ref> as “polished" permutations since the condition of self-duality on the interval [e,w] is sufficient for smoothness, but not necessary.



 §.§ Affine permutations

In this section we discuss applications of BP decompositions to the group of affine permutations denoted _n.  An affine permutation is a bijection w:→ such that 

    
  * w(i+n)=w(i)+n for all i∈ and 
    
  * ∑_i=1^n w(i)=n(n+1)/2.

Note that a regular permutation extends to an affine permutation by applying part (1) above to the one-line notation sequence w(1)⋯ w(n). 
 Similarly, any affine permutation is uniquely determined by the “window" of values 

    ⋯ w(-1), w(0),[w(1),w(2),⋯, w(n)],w(n+1),w(n+2),⋯

by the same extension.  For example [4,2,3,1], [8,1,-2,3], and [-7, 7,6,4] are all examples of affine permutations in _4.

The group of affine permutations is an infinite Coxeter group with generating set S={s_0,s_1,…,s_n-1} and Coxeter graph:

    [scale=.5]
        [thick] (0,0)–(2,0)–(4.25,0)–(6.5,0)–(3.25,1.5)–(0,0);
        [thick,fill=white] (0,0) circle (.3cm) node[label=[label distance=.1cm]-90:s_1] ;
        [thick,fill=white] (2,0) circle (.3cm) node[label=[label distance=.1cm]-90:s_2];
        [white, fill=white] (4.25,0) circle (.65cm);
         (4.25,0) node ⋯;
        [thick,fill=white] (6.5,0) circle (.3cm) node[label=[label distance=.1cm]-90:s_n-1];
        [thick,fill=white] (3.25,1.5) circle (.3cm) node[label=[label distance=.1cm]90:s_0];

Affine permutations are referred to as Coxeter groups of affine type A.  Note that all maximal parabolic subgroups of _n are isomorphic to the finite permutation group _n.

As with finite permutations, (rational) smoothness is closely tied to pattern avoidance and was studied by Billey and Crites in <cit.>.  We say an affine permutation w contains the (finite) pattern u∈_k if there is a sequence (i_1<⋯ <i_k) such that w(i_1)⋯ w(i_k) has the same relative order as u.   Note that the sequence  (i_1<⋯ <i_k) does not necessarily have to be contained in the integers [n]={1,…,n}.  If w does not contain u, we say it avoids the pattern u.  The following thoerem if proved by Billey and Crites in <cit.>


    The affine permutation w∈_n is rationally smooth if and only if one of the following hold:
    
        
  * w avoids the patterns 3412 and 4231 or 
        
  * w is a twisted spiral permutation (see <cit.>).
    

It is shown by Mitchell in <cit.>, that if w is a twisted spiral permutation, then the Schubert variety X(w) is not smooth.  Hence smooth is not equivalent to rationally smooth for affine permutations.  One technical result used to prove Theorem <ref> is the following analogue of Theorem <ref>.

    If w ∈_n avoids 3412 and 4231, then either w or w^-1 has a Grassmannian BP decomposition vu where both v and u belong to proper parabolic subgroups of _n.

Billey and Crites show that, for the BP decomposition vu found in Proposition <ref>, the Poincaré polynomial P_v^J(q) is a q-binomial and hence palindromic.  They also show that u is a smooth (finite) permutation.  So Theorem <ref> implies P_w(q) is palindromic.  
The next theorem was partially conjectured in <cit.> and proved by Richmond and Slofstra in <cit.>.

  Let w∈_n.  Then the following are equivalent:
    
        
  * X(w) is smooth.
        
  * w avoids the patterns 3412 and 4231.
        
  * w has a Grassmannian BP decomposition vu with respect to some J where both v and u belong to proper parabolic subgroups of _n.  
        Furthermore v is the maximal element of W_S(v)∩ W^J and u is a smooth permutation in the W_S(u).
      


The proof of Theorem <ref> is similar to the proof of Theorem <ref>.  We remark that part (3) of Theorem <ref> implies that for an affine permutation w∈_n, the affine Schubert variety X(w) is smooth if and only if it is an iterated fiber bundle of Grassmannian varieties. 

Theorem <ref> also implies an analogue of Corollary <ref> on staircase diagrams of affine type A which we state below.  Since _n is an infinite Coxeter groups, we say a staircase diagram is spherical if for each B∈, the parabolic subgroup W_B is a finite Coxeter group.  The next statement is from <cit.>.

    The maximal labelling gives a bijection between spherical staircase diagrams over the Coxeter graph of _n and smooth affine permutations in _n.

One immediate consequence of Corollary <ref> is that the number of affine permutations that avoid 3412 and 4231 in _n is finite.  This fact also follows directly from results in <cit.>.  For single patterns, Crites proved in <cit.> that the number affine permutations in _n avoiding a pattern u is finite if and only if u contains 321.  

Staircase diagrams of affine type A can be thought of as staircase diagrams of finite type A that “loop" back on themselves since the Coxeter graph is a cycle.  Figure <ref> gives an example of an affine staircase diagram.  For more details see <cit.>.

As with Theorems <ref> and <ref> we can use staircase diagrams to enumerate smooth affine permutations.  The following is proved in <cit.>.

    Let A(t):=∑ã_n t^n where ã_n denotes the number of smooth affine permutations in _n.  Then 
    
    A(t) = P(t) - Q(t) √(1-4t)/(1-t)(1-4t)(1-6t+8t^2-4t^3)

    where
    
    P(t) = (1-4t)(2-11t+18t^2-16t^3+10t^4-4t^5)

    and
    
    Q(t) = (1-t)(2-t)(1-6t+6t^2).







§ FUTURE DIRECTIONS


We state some open questions and possible future directions for the study of Coxeter groups in relation to BP-decompositions.


    While rational smoothness for Coxeter groups of finite Lie type have been extensively studied.  Characterizations of rationally smooth elements for arbitrary Coxeter groups are relatively unknown.  For example, if w is rationally smooth, does w have a Grassmannian BP decomposition?  Does Theorem <ref> hold for inversion hyperplane arrangements of rationally smooth elements in arbitrary Coxeter groups?  We remark that Richmond and Slofstra study rationally smooth elements in Coxeter groups that avoid certain rank 3 parabolic subgroups in <cit.>.



Let W be a Coxeter group and for u≤ v∈ W, define the Poincaré polynomial of the interval

    P_u,w(q):=∑_z∈[u,w] q^ℓ(z)-ℓ(u).

If u=e, then this is the usual Poincaré polynomial P_w(q).  For example, if u=s_2 and v=s_2s_1s_3s_2, then Figure <ref> shows the interval [u,v] and  

    P_u,v(q)=1+4q+4q^2+q^3.


We ask is under what conditions does the polynomial P_u,v(q) factor nicely?  and if so, does the interval [u,v] also decompose as a poset?  Is there a generalization of the characterization Theorem <ref> for arbitrary intervals [u,v]?  We remark that the poset structure of the interval [u,v] has connections to Kazhdan-Lustig theory and Richardson varieties <cit.>.





Let w=vu be a parabolic decomposition with respect to J.  In Remark <ref> we describe the coset intervals [e,w]∩ v_0W^J for v_0 ∈ [e,v]^J and show they are poset isomorphic to [e,u_0] for some u≤ u_0≤ u' where u' is the maximal element of [e,w]∩ W_J.  

We ask if there is nice description of the set of all u_0∈[u,u'] that appear for some v_0∈[e,v]^J.  If u=u', then w=vu is a BP decomposition by Theorem <ref>.  Note that not every element of [u,u'] may appear in this set.




    In Sections <ref> and <ref>, we see several cases of BP-decompositions and staircase diagrams used to enumerate classes of (rationally) smooth elements.  To what extend can these structures help with enumerating other classes of Coxeter group elements.  For example, can we use BP decompositions to calculate the generating series for the number of permutations that avoid 3412, 52341, and 635241 from Theorem <ref>?


plain


