# The parabolic coset structure of Bruhat intervals in Coxeter groups

Suho Oh<EMAIL_ADDRESS>and  Edward Richmond<EMAIL_ADDRESS>
###### Abstract.

In this paper, we study the decomposition of Bruhat intervals in a Coxeter
group with respect to cosets of a parabolic subgroup. Our main result is that
the intersection of a lower Bruhat interval with a parabolic coset contains a
unique maximal element. As an application, we give a decomposition formula for
the Poincaré polynomial of a Coxeter group element. We also show that the
fibers of standard parabolic projection maps on Schubert varieties are
themselves Schubert varieties.

##  1\. Introduction

The Bruhat order on Coxeter groups plays an important role in the
representation theory of Lie groups and the geometry of associated flag
varieties and Schubert varieties. In this paper, we study the decomposition of
lower Bruhat intervals with respect to the cosets of given a parabolic
subgroup. When considering the identity coset (i.e. the parabolic subgroup
itself), it was proved by van den Hombergh in that the intersection of a lower
Bruhat interval with a parabolic subgroup has unique maximal element [15]. In
[2], Billey and Postnikov showed that if the maximal element satisfies a
certain property (now called a Billey-Postinkov decomposition), then the
corresponding Poincaré polynomial of Bruhat interval factors nicely with
respect to the parabolic subgroup. It was later shown by Slofstra and the
second author that Billey-Postinkov decompositions can be characterized
geometrically as a fiber bundle structure on the Schubert variety
corresponding to the interval [12]. Billey-Postinkov decompositions have also
been used the study of hyperplane arrangements, permutation pattern avoidance,
smooth Schubert varieties, and self-dual Bruhat intervals [1, 5, 10, 13].

In contrast to the identity coset, the structure of lower Bruhat intervals
intersected with an arbitrary parabolic coset is much less is understood. In
[12], Slofstra and the second author show that these intersections describe
the fibers of a projection map between partial flag varieties restricted to a
Schubert variety. The main result of this paper is that lower Bruhat intervals
intersected with any coset of a parabolic subgroup still contain a unique
maximal element. As a consequence, the fibers of the projection maps on
Schubert varieties are themselves Schubert varieties. We also give a new
recursive formula for the Poincaré polynomial of a lower Bruhat interval.

##  2\. Main results

Let $W$ denote a Coxeter group with generating set $S$ and identity element
$e$. Let $\leq$ denote the Bruhat partial order on $W$ and let
$\ell:W\rightarrow\mathbb{Z}_{\geq 0}$ denote the length function with respect
to $S$. For basic properties of Coxeter groups, we refer the reader to [4] or
[7]. For any $J\subseteq S$, we can decompose

$W=W^{J}\cdot W_{J}$

where $W_{J}$ is the subgroup generated by $J$ (these are called parabolic
subgroups) and $W^{J}$ denotes the set of minimal length coset representatives
of the right-coset space $W/W_{J}$. We study lower Bruhat intervals with
respect to this decomposition. More precisely, let $w\in W$ and define the
lower interval $[e,w]:=\\{u\in W\ |\ u\leq w\\}$. Consider the decomposition

$[e,w]=\bigsqcup_{x\in W^{J}}[e,w]\cap xW_{J}.$

Observe that $[e,w]\cap xW_{J}$ is nonempty if and only if $x\leq w$.
Moreover, $[e,w]\cap xW_{J}$ is a lower order ideal in $xW_{J}$ with unique
minimal element $x$. Our main result is there is also a unique maximal
element.

######  Theorem 2.1.

Let $w\in W$ and $x\in W^{J}$ such that $x\leq w$. Then $[e,w]\cap xW_{J}$ has
a unique maximal element with respect to Bruhat order.

When $x=e$, Theorem 2.1 was proved van den Hombergh in [15] and then again by
Billey, Fan, and Losonczy in [3]. We remark that the proof for Theorem 2.1,
given in Section 3, is an inductive argument where $\ell(x)=0$ serves as the
base case. The rest of this section is dedicated to consequences and
applications of Theorem 2.1.

###  2.1. Properties of maximal elements

For any $x\in W^{J}$ and $x\leq w$, define

$m_{J}(w,x):=x^{-1}q$

where $q$ denotes the maximal element of $[e,w]\cap xW_{J}$. It is easy to see
that $m_{J}(w,x)\in W_{J}$. For any $w\in W$, we say $w=vu$ is the parabolic
decomposition of $w$ with respect to $J$ if $\ell(w)=\ell(v)+\ell(v)$ and
$v\in W^{J}$ and $u\in W_{J}$. It is a basic fact that any element of $W$ can
be uniquely written in this way. Moreover, if $w=vu$ is the parabolic
decomposition with respect to $J$ and $x\in W^{J}$ with $x\leq w$, then $x\leq
v$. In the following proposition, we state some properties of $m_{J}(w,x)$.

######  Proposition 2.2.

Let $w=vu$ denote the parabolic decomposition with respect to $J$. Then the
following are true:

  1. (1)

As graded posets, $[e,w]\cap xW_{J}\simeq[e,m_{J}(w,x)]$ via $y\mapsto
x^{-1}y.$

  2. (2)

$m_{J}(w,v)=u$.

  3. (3)

If $x<\bar{x}\leq v$, then $m_{J}(w,x)\geq m_{J}(w,\bar{x})$.

  4. (4)

If $x\leq v$, then $m_{J}(w,x)\in[m_{J}(w,v),m_{J}(w,e)]$

###### Proof.

Part (1) follows from the fact that the map $xW_{J}\rightarrow W_{J}$ given by
$y\mapsto x^{-1}y$ is a graded poset isomorphism and that $[e,w]\cap xW_{J}$
is a lower order ideal in $xW^{J}$. Part (2) follows from the fact that $w=vu$
is a parabolic decomposition. For part (3), suppose that $\bar{x}$ covers $x$
and hence there exists a reflection $t$ (not necessarily in $S$) such that
$x=t\bar{x}$. Let $y\in[e,w]\cap\bar{x}W_{J}$ and let $q$ denote the maximal
element of $[e,w]\cap xW_{J}$. It suffices to show that $\bar{x}^{-1}y\leq
x^{-1}q$. Since $y\in\bar{x}W_{J}$ and $ty\leq y\leq w$, we have that
$ty\in[e,w]\cap xW_{J}$ and thus $ty\leq q$. Since $q$ is also in $xW_{J}$, we
have $x^{-1}ty\leq x^{-1}q$. But $(x^{-1}t)y=\bar{x}^{-1}y$ which proves part
(3). Finally, part (4) follows from part (3). ∎

For any $w\in W$, define the Poincaré polynomial (i.e. the rank generating
function of the poset interval $[e,w]$ with respect to length):

$P_{w}(t):=\sum_{w^{\prime}\leq w}t^{\ell(w^{\prime})}.$

As an immediate corollary of Theorem 2.1 and Proposition 2.2 part (1), we get
the following formula:

######  Corollary 2.3.

Let $w\in W$ and $J\subseteq S$. Then

$P_{w}(t)=\sum_{x\in[e,w]\cap W^{J}}t^{\ell(x)}\cdot P_{m_{J}(w,x)}(t).$

We now explain how the (shifted) maximal elements $m_{J}(w,x)$ are related to
Billey-Postnikov decompositions. First note that Proposition 2.2 part (4) says
that $m_{J}(w,x)$ takes on a values in the interval $[m_{J}(w,v),m_{J}(w,e)]$.
Fix $J\subseteq S$ and define $u_{\text{max}}:=m_{J}(w,e)$. We say that a
parabolic decomposition $w=vu$ is a Billey-Postnikov decomposition (or BP
decomposition) if $u=u_{\text{max}}$ (i.e. $m_{J}(w,v)=m_{J}(w,e)$). Hence, if
$w=vu$ is a BP-decomposition, then Proposition 2.2 part (4) implies that
$m_{J}(w,x)=u$ for all $x\in[e,w]\cap W^{J}$. By Corollary 2.3, the Poincaré
polynomial factors as

$P_{w}(t)=P^{J}_{v}(t)\cdot P_{u}(t)$

where

$P^{J}_{v}(t):=\sum_{x\in[e,v]\cap W^{J}}t^{\ell(x)}.$

This recovers [2, Theorem 6.1] which states that BP decompositions correspond
to parabolic factorizations of the Poincaré polynomial. When $w=vu$ is not a
BP decomposition, then $m_{J}(w,x)$ can take on different values for $x\in
W^{J}$. We remark that not every $u^{\prime}\in[u,u_{\text{max}}]$ is equal to
$m_{J}(w,x)$ for some $x\in W^{J}.$ It is an interesting problem to
characterize the set of shifted maximal elements

$M_{J}(w):=\\{m_{J}(w,x)\ |\ x\in W^{J}\\}.$

Proposition 2.2 part (3) implies that the induced Bruhat order on $M_{J}(w)$
is a subposet of $[e,v]\cap W^{J}$ equipped with the reverse Bruhat ordering.

###  2.2. Example in the permutation group

Consider the permutation group $S_{4}$ which is the Coxeter group of type
$A_{3}$. This group is generated by $S=\\{s_{1},s_{2},s_{3}\\}$ subject to the
relations

$s_{i}^{2}=e,\quad(s_{1}s_{2})^{3}=(s_{2}s_{3})^{3}=(s_{1}s_{3})^{2}=e.$

If $J=\\{s_{1},s_{2}\\}$, then the minimal length coset representatives are

$W^{J}=\\{e,s_{3},s_{2}s_{3},s_{1}s_{2}s_{3}\\}.$

The Bruhat decomposition of $S_{4}$ with respect to the corresponding cosets
is given in Figure 1. Here we respectively color the cosets
$W_{J},s_{3}W_{J},s_{2}s_{3}W_{J}$ and $s_{1}s_{2}s_{3}W_{J}$ with black, red,
blue and green.

$s_{1}s_{2}s_{3}s_{1}s_{2}s_{1}$$s_{2}s_{3}s_{2}s_{1}s_{2}$$s_{1}s_{2}s_{3}s_{2}s_{1}$$s_{1}s_{2}s_{3}s_{1}s_{2}$$s_{2}s_{3}s_{2}s_{1}$$s_{3}s_{1}s_{2}s_{1}$$s_{2}s_{3}s_{1}s_{2}$$s_{1}s_{2}s_{3}s_{2}$$s_{1}s_{2}s_{3}s_{1}$$s_{2}s_{3}s_{2}$$s_{3}s_{2}s_{1}$$s_{3}s_{1}s_{2}$$s_{2}s_{3}s_{1}$$s_{1}s_{2}s_{1}$$s_{1}s_{2}s_{3}$$s_{3}s_{2}$$s_{2}s_{3}$$s_{3}s_{1}$$s_{2}s_{1}$$s_{1}s_{2}$$s_{3}$$s_{2}$$s_{1}$$\emptyset$
Figure 1. The Bruhat order of $S_{4}$ and the cosets with respect to
$J=\\{s_{1},s_{2}\\}$ presented in different colors.

Let $w=s_{1}s_{2}s_{3}s_{2}s_{1}$ and consider the Bruhat lower interval
$[e,w]$. In one-line notation, this permutation is $w=4231$. Note that
$w=vu=(s_{1}s_{2}s_{3})(s_{2}s_{1})$ is the parabolic decomposition with
respect to $J$. We see in Figure 2 that each coset of $W_{J}$ intersected with
$[e,w]$ has a unique maximal element (here the cosets retain the same color as
in Figure 1). For example, $[e,w]\cap s_{2}s_{3}W_{J}$ (the blue elements) has
maximal element $s_{2}s_{3}s_{2}s_{1}$ and $m_{J}(s_{2}s_{3},w)=s_{2}s_{1}$.
We record the value of $m_{J}(w,x)$ of each $x\in W^{J}$ in the following
table:

$x$ | $e$ | $s_{3}$ | $s_{2}s_{3}$ | $s_{1}s_{2}s_{3}$
---|---|---|---|---
$m_{J}(w,x)$ | $s_{1}s_{2}s_{1}$ | $s_{1}s_{2}s_{1}$ | $s_{2}s_{1}$ | $s_{2}s_{1}$

$s_{1}s_{2}s_{3}s_{2}s_{1}$$s_{2}s_{3}s_{2}s_{1}$$s_{3}s_{1}s_{2}s_{1}$$s_{1}s_{2}s_{3}s_{2}$$s_{1}s_{2}s_{3}s_{1}$$s_{2}s_{3}s_{2}$$s_{3}s_{2}s_{1}$$s_{3}s_{1}s_{2}$$s_{2}s_{3}s_{1}$$s_{1}s_{2}s_{1}$$s_{1}s_{2}s_{3}$$s_{3}s_{2}$$s_{2}s_{3}$$s_{3}s_{1}$$s_{2}s_{1}$$s_{1}s_{2}$$s_{3}$$s_{2}$$s_{1}$$\emptyset$
Figure 2. The lower interval of $w=s_{1}s_{2}s_{3}s_{2}s_{1}$, again with
different colors representing the intersection with the cosets with respect to
$J=\\{s_{1},s_{2}\\}$.

By Corollary 2.3, the Poincaré polynomial of $w=s_{1}s_{2}s_{3}s_{2}s_{1}$
decomposes as:

$\displaystyle P_{w}(t)$ $\displaystyle=(1+t)\cdot
P_{s_{1}s_{2}s_{1}}(t)+(t^{2}+t^{3})\cdot P_{s_{1}s_{2}}(t)$
$\displaystyle=(1+t)(1+2t+2t^{2}+t^{3})+(t^{2}+t^{3})(1+2t+t^{2}).$

In this example, $u=s_{2}s_{1}$ whereas $u_{\text{max}}=s_{1}s_{2}s_{1}$. Thus
the parabolic decomposition $w=vu$ with respect to $J=\\{s_{1},s_{2}\\}$ is
not a BP-decomposition.

###  2.3. Relative Bruhat intervals

In this section, we show that Theorem 2.1 extends to lower Bruhat intervals in
$W^{J}$. For any $J\subseteq S$ and $w\in W^{J}$ we define the relative lower
Bruhat interval of $w$ with respect to $J$ as

$[e,w]^{J}:=[e,w]\cap W^{J}.$

Relative Bruhat intervals correspond to Schubert varieties in partial flag
varieties in the same way the usual Bruhat intervals correspond to Schubert
varieties in the full flag variety (see Section 2.4). Let $J\subseteq
K\subseteq S$ and define

$W^{J}_{K}:=W^{J}\cap W_{K}.$

Observe that $W^{K}\subseteq W^{J}$ and that we can decompose

$W^{J}=W^{K}\cdot W^{J}_{K}.$

Analogous to non-relative case, for any $w\in W^{J}$, consider the
decomposition

$[e,w]^{J}=\bigsqcup_{x\in W^{K}}[e,w]^{J}\cap xW^{J}_{K}.$

Note that $[e,w]^{J}\cap xW^{J}_{K}\neq\emptyset$ if and only if $x\leq w$. If
$J=\emptyset$, then $W^{J}=W$ and $[e,w]^{J}=[e,w]$.

######  Corollary 2.4.

Let $J\subseteq K\subseteq S$ with $w\in W^{J}$ and $x\in W^{K}$. If $x\leq
w$, then $[e,w]^{J}\cap xW^{J}_{K}$ has a unique maximal element with respect
to Bruhat order.

In particular, if $q^{K}$ denotes the maximal element of $[e,w]\cap xW^{K}$
and $q\in W^{J}$ indexes the coset for which $q^{K}\in qW_{J}$, then $q$ is
unique maximal element of $[e,w]^{J}\cap xW^{J}_{K}$.

###### Proof.

If $J=\emptyset$, then the corollary follows from Theorem 2.1. Now suppose $J$
is some subset of $K$ and consider $m_{K}(w,x)\in W_{K}$ and let
$m_{K}(w,x)=vu$ denote the parabolic decomposition with respect to $J$. In
particular, $v\in W^{J}_{K}$ and $u\in W_{J}$. Set $q:=xv$ and note that
$q\in[e,w]^{J}\cap xW^{J}_{K}$. Now suppose that $y\in[e,w]^{J}\cap
xW^{J}_{K}$. Then $y\in[e,w]\cap xW_{K}$ and $y\leq x\cdot m_{K}(w,x)=(xv)u$.
Since $y\in xW^{J}_{K}$, we must have $y\leq xv=q$. ∎

We remark that Corollary 2.4 was proved for $x=e$ in [12, Lemma 4.1] following
a similar argument. For any $w\in W^{J}$ and $x\in W^{K}$ for which $x\leq w$,
define

$m_{K}^{J}(x,w):=x^{-1}q$

where $q$ denotes the maximal element of $[e,w]^{J}\cap xW^{J}_{K}$. The
following proposition contains results analogous to Proposition 2.2 and
Corollary 2.3. The proof follows the same argument, so we leave it as an
exercise for the reader.

######  Proposition 2.5.

Let $J\subseteq K\subseteq S$ with $w\in W^{J}$. Let $w=vu$ denote the
parabolic decomposition with respect to $K$. Then the following are true:

  1. (1)

As graded posets, $[e,w]^{J}\cap xW^{J}_{K}\simeq[e,m^{J}_{K}(w,x)]^{J}$ via
$y\mapsto x^{-1}y.$

  2. (2)

$m^{J}_{K}(w,v)=u$.

  3. (3)

If $x<\bar{x}\leq v$, then $m^{J}_{K}(w,x)\geq m^{J}_{K}(w,\bar{x})$.

  4. (4)

If $x\leq v$, then $m^{J}_{K}(w,x)\in[m^{J}_{K}(w,v),m^{J}_{K}(w,e)]$

  5. (5)

The Poincaré polynomial

$P^{J}_{w}(t)=\sum_{x\in[e,w]^{K}}t^{\ell(x)}\cdot P^{J}_{m^{J}_{K}(w,x)}(t).$

In particular, if $m^{J}_{K}(w,v)=m^{J}_{K}(w,e)$, then

$P^{J}_{w}(t)=P^{K}_{v}(t)\cdot P^{J}_{u}(t).$

The second portion of Proposition part (5) corresponds to an analogue of BP-
decompositions for relative Bruhat intervals. For more information on this, we
refer the reader to [12].

###  2.4. Applications to Schubert varieties

Let $G$ denote a Kac-Moody (or semi-simple Lie group) over $\mathbb{C}$ and
let $T\subseteq B\subseteq G$ denote a choice of maximal torus and Borel
subgroup. Let $W:=N(T)/T$ denote the Weyl group of $G$ with simple generating
set $S$. The group $W$ is a crystallographic Coxeter group. For any subset
$J\subseteq S$, define the parabolic subgroup $P_{J}:=BW_{J}B$ and consider
the partial flag variety $G/P_{J}$. If $J=\emptyset$, then $G/P_{J}=G/B$ is
the full flag variety of $G$. For any $w\in W^{J}$, define the Schubert
variety to be the closure of the $B$-orbit indexed by $w$ in $G/P_{J}$:

$X^{J}(w):=\overline{BwP_{J}}/P_{J}=\bigsqcup_{w^{\prime}\in[e,w]^{J}}Bw^{\prime}P_{J}/P_{J}.$

The Schubert variety $X^{J}(w)$ is a projective variety of complex dimension
$\ell(w)$. Schubert varieties from a stratification of the flag variety
$G/P_{J}$ and play an important role in the representation theory of $G$. For
more on Kac-Moody groups and their flag varieties and Schubert varieties see
[9]. Let $J\subseteq K\subseteq S$ and consider the $G$-equivariant projection
map

$\pi:G/P_{J}\twoheadrightarrow G/P_{K}$

given by $\pi(gP_{J}):=gP_{K}$. If $w\in W^{J}$ and $w=vu$ denotes the
parabolic decomposition with respect to $K$, then restricting the map $\pi$ to
$X^{J}(w)$ yields a projection

$\pi:X^{J}(w)\twoheadrightarrow X^{K}(v).$

If $gP_{K}\in X^{K}(v)$, then we can choose $b_{0}\in B$ and
$x\in[e,v]^{K}=[e,w]\cap W^{K}$ such that $gP_{K}=b_{0}xP_{K}$. The following
proposition is proved in [12, Lemma 4.6].

######  Proposition 2.6.

[12] Let $w=vu\in W^{J}$ denote the parabolic decomposition with respect to
$K$ and consider the projection $\pi:X^{J}(w)\twoheadrightarrow X^{K}(v).$ Let
$b_{0}\in B$ and $x\in[e,v]^{K}$. Then $b_{0}xP_{K}\in X^{K}(v)$ and the fiber

$\pi^{-1}(b_{0}xP_{K})=\bigsqcup_{y\in[e,w]^{J}\cap
xW^{J}_{K}}b_{0}xBx^{-1}yP_{J}/P_{J}.$

Corollary 2.4 and Proposition 2.5 part (1) imply the following:

######  Corollary 2.7.

With the notation in Proposition 2.6, we have that the fiber

$\pi^{-1}(b_{0}xP_{K})=b_{0}x\cdot X^{J}(m^{J}_{K}(w,x)).$

In particular, each fiber of the map $\pi$ restricted to $X^{J}(w)$ is
isomorphic to a Schubert variety.

If $w=vu$ is a BP decomposition with respect to $K$, then $m^{J}_{K}(w,x)=u$
for all $x\leq v$. In this case, Corollary 2.7 implies each fiber of the
projection $\pi:X^{J}(w)\twoheadrightarrow X^{K}(v)$ is isomorphic to
$X^{J}(u)$. It is shown in [12, Theorem 3.3] that this projection gives a
$X^{J}(u)$-fiber bundle structure on the Schubert variety $X^{J}(w)$.

##  3\. Proof of Theorem 2.1

We begin with some important definitions. For any $w\in W$, define the sets

$\displaystyle S(w)$ $\displaystyle:=\\{s\in S\ |\ s\leq w\\}$ $\displaystyle
D_{R}(w)$ $\displaystyle:=\\{s\in S\ |\ \ell(ws)\leq\ell(w)\\}$ $\displaystyle
D_{L}(w)$ $\displaystyle:=\\{s\in S\ |\ \ell(sw)\leq\ell(w)\\}.$

The set $S(w)$ is called the support of $w$ and can be thought of as the set
of generators appearing in some (or any) reduced word of $w$. The sets
$D_{R}(w)$ and $D_{L}(w)$ are respectively called the right and left descents
of $w$. For any $w\in W$ and $J\subseteq S$, we say that $w=uv$ is a left-
sided parabolic decomposition with respect to $J$ if
$\ell(w)=\ell(u)+\ell(v)$, where $u\in W_{J}$ and $v$ is a minimal length
coset representative of the left-coset space $W_{J}\backslash W$. The usual
parabolic decomposition $w=vu$ is sometimes called a right-sided parabolic
decomposition with respect to $J$. We say $w=w_{1}\cdot w_{2}$ is a reduced
factorization if $\ell(w)=\ell(w_{1})+\ell(w_{2})$. Note the all left and
right parabolic decompositions are reduced factorizations.

The proof of Theorem 2.1 relies on the 0-Iwahari-Hecke monoid or Coxeter
monoid structure of $W$. This structure can be viewed as the monoid generated
by $S$ with a product $\star$ satisfying the Coxeter braid relations and along
with the relation $s\star s=s$ for all $s\in S$. This monoid structure was
first studied by Norton in [11] in the context of Hecke algebras. It is well
known that, as sets, $W=\langle S,\star\rangle$. The next lemma records some
basic facts about the Coxeter monoid.

######  Lemma 3.1.

Let $W$ be a Coxeter group. Then the following are true:

  1. (1)

Let $(s_{1},\ldots,s_{k})$ be a sequence of generators in $S$. Then

$s_{1}\cdots s_{k}\leq s_{1}\star\cdots\star s_{k}$

with equality if and only if $(s_{1},\ldots,s_{k})$ is a reduced expression.

  2. (2)

For any $s\in S$ and $w\in W$,

$s\star w=\begin{cases}w&\text{if}\quad\ell(sw)<\ell(w)\\\
sw&\text{if}\quad\ell(sw)>\ell(w).\end{cases}.$

The next proposition is a key property about the monoid structure of $W$ in
relation to Bruhat intervals. It is proved by He in [6, Lemma 1] and later by
Kenny in [8, Proposition 8].

######  Proposition 3.2.

[6, 8] For any $w,u\in W$, we have that

$[e,w\star u]=\\{ab\ |\ a\in[e,w],b\in[e,u]\\}.$

We give an example of this phenomenon. The poset in Figure 1 is the Bruhat
order of $S_{4}$. The elements in the lower interval of
$s_{1}s_{2}s_{3}s_{2}s_{1}$ is colored in red. We set $J=\\{s_{1},s_{2}\\}$
and $s=s_{3}$. All the elements in the lower interval
$[e,s_{1}s_{2}s_{3}s_{2}s_{1}]$ can be written as $a\star b$ where $a\leq
s_{1}s_{2}s_{3}$ and $b\leq s_{2}s_{1}$. For example, $s_{2}s_{3}s_{1}$ can be
written as $s_{2}s_{3}\star s_{1}$.

The following proposition establishes Theorem 2.1 in the case that $\ell(x)=0$
and is proved in [15, Lemma 7] and later in [3, Theorem 2.2].

######  Proposition 3.3.

[3, 15] For any $w\in W$ and $J\subseteq S$, the set $[e,w]\cap W_{J}$ has a
unique maximal element.

Observe that the maximal element of $[e,w]\cap W_{J}$ can be constructed using
the Coxeter moniod product. Let $w=s_{1}\cdots s_{k}$ be a reduced word and
let $(s_{i_{1}},\ldots,s_{i_{j}})$ denote the subsequence of generators that
belong to $J$. It follows from Lemma 3.1 that

$s_{i_{1}}\star\cdots\star s_{i_{j}}$

is the unique maximal element of $[e,w]\cap W_{J}$. We remark that this
construction of the maximal element was described in [3, Section 2].

Before we prove the Theorem 2.1, we briefly outline how the inductive argument
works in the case that $\ell(x)=1$. Let $w\in W$ with $x\leq w$. Suppose
$x=s\in S\setminus J$ (otherwise $x\notin W^{J}$). Let $w=u\cdot v$ be the
left-sided parabolic decomposition with respect to $S\setminus\\{s\\}$. In
particular, $u\in W_{S\setminus\\{s\\}}$ and $D_{L}(v)=\\{s\\}$. Define

$J^{\prime}:=\\{t\in J\ |\text{$t$ commutes with $s$}\\}$

and consider the following elements which are well defined by Proposition 3.3:

  1. (1)

Let $q^{\prime}$ denote the unique maximal element of $[e,u]\cap
W_{J^{\prime}}$

  2. (2)

Let $q^{\prime\prime}$ denote the unique maximal element of $[e,v]\cap W_{J}$

We show that

$q:=q^{\prime}\star(sq^{\prime\prime})$

is the unique maximal element $[e,w]\cap sW_{J}$. Now let $y\in[e,w]\cap
sW_{J}$ and write a reduced factorization

$y=y_{u}\cdot y_{v}$

where $y_{u}\leq u$ and $y_{v}\leq v.$ To prove that $q$ is maximal, we claim
the following:

  1. (1)

$q\in[e,w]\cap sW_{J}$

  2. (2)

$y_{v}\in sW_{J}$ and hence $sy_{v}\in W_{J}$

  3. (3)

$y_{u}\in W_{J^{\prime}}$.

These claims are proved below in Lemmas 3.5 and 3.6. Under these assumptions,
we have $sy_{v}\in[e,v]\cap W_{J}$ and hence $sy_{v}\leq q^{\prime\prime}$.
Since $q^{\prime\prime}<sq^{\prime\prime}$, we must have $y_{v}\leq
sq^{\prime\prime}$. By definition, $y_{u}\leq u$ and hence $y_{u}\leq
q^{\prime}$. Proposition 3.2 implies $y=y_{u}y_{v}\leq
q^{\prime}\star(sq^{\prime\prime})=q.$

###### Proof of Theorem 2.1.

We now give the proof of Theorem 2.1 for general $x\in W^{J}$. Let $w\in W$
and $x\in W^{J}$ with $x\leq w$. For the sake of induction, assume
$[e,w^{\prime}]\cap x^{\prime}W_{J}$ has a unique maximal element for all
$w^{\prime}\in W$ and all $x^{\prime}\in W^{J}$ such that $x^{\prime}<x$. We
also assume that $[e,w^{\prime}]\cap W_{J^{\prime}}$ has a unique maximal
element for all $w^{\prime}\in W$ and $J^{\prime}\subseteq S$. The following
is a short technical result needed for the proof. We remark that this lemma
also appears in [14, Lemma 4.1].

######  Lemma 3.4.

If $x\in W^{J}$ and $s\in S$ such that $x<sx$, then either $sx\in W^{J}$ or
$sx\in xW_{J}$.

###### Proof.

Since $x<sx$, we must have that $sx\in vW_{J}$ for some $v\in W^{J}$ where
$x\leq v\leq sx$. But $sx$ covers $x$, so either $v=x$ or $v=sx$. ∎

Let $w=u\cdot v$ denote the left-sided parabolic decomposition with respect to
$S\setminus D_{L}(x)$. Observe that $S(u)\cap D_{L}(x)=\emptyset$ and
$D_{L}(v)\subseteq D_{L}(x)$. Define

$J^{\prime}:=\\{t\in J\cup S(x)\ |\ tx\in xW_{J}\\}.$

Fix $s\in D_{L}(v)$ and consider the following elements which are well defined
by induction:

  1. (1)

Let $q^{\prime}$ denote the unique maximal element of $[e,u]\cap
W_{J^{\prime}}$

  2. (2)

Let $q^{\prime\prime}$ denote the unique maximal element of $[e,v]\cap
sxW_{J}$

We claim that

$q:=q^{\prime}\star(sq^{\prime\prime})$

is the unique maximal element $[e,w]\cap xW_{J}$. Observe that the definition
of $q^{\prime\prime}$ depends on the choice of $s\in D_{L}(v)$ and that each
$s$ will yield a different element $q^{\prime\prime}$. However, the maximality
of $q=q^{\prime}\star(sq^{\prime\prime})$ will ultimately imply that $q$
itself does not depend on this choice.

######  Lemma 3.5.

The element $q\in[e,w]\cap xW_{J}$.

###### Proof.

We show that $q\leq w$ and $q\in xW_{J}$. First note that $q^{\prime}\leq u$
and $q^{\prime\prime}\leq v$. Since $s\in D_{L}(v)$ and $s\notin
D_{L}(q^{\prime\prime})$, we also have that $sq^{\prime\prime}\leq v$. By
Lemma 3.1, we have

$q=q^{\prime}\star(sq^{\prime\prime})\leq u\star v=uv=w.$

To show that $q\in xW_{J}$, note that since $q^{\prime\prime}\in sxW_{J}$, we
have that $sq^{\prime\prime}\in xW_{J}$. Write $sq^{\prime\prime}=xu_{0}$ for
some $u_{0}\in W_{J}$. Let $q^{\prime}=t_{1}\cdots t_{k}$ be a reduced word
for $q^{\prime}$. Lemma 3.1 implies

$q^{\prime}\star(sq^{\prime\prime})=t_{1}\star t_{2}\star\cdots\star
t_{k}\star(xu_{0}).$

Since $t_{k}\in J^{\prime}$, we have $t_{k}\notin D_{L}(x)$ and hence
$t_{k}\star x=t_{k}x\in xW_{J}$. Thus $t_{k}\star xu_{0}=xu_{1}$ for some
$u_{1}\in W_{J}$. Applying this process inductively to $t_{k-1},\ldots,t_{1}$
yields that $q=q^{\prime}\star(sq^{\prime\prime})\in xW_{J}$. ∎

Let $y\in[e,w]\cap xW_{J}$ and consider a reduced factorization

$y=y_{u}\cdot y_{v}$

where $y_{u}\leq u$ and $y_{v}\leq v$. In particular, $y_{u}\in W_{S\setminus
D_{L}(x)}$

######  Lemma 3.6.

Let $y=y_{u}\cdot y_{v}$ as above. The following are true:

  1. (1)

$y_{v}\in xW_{J}$ and hence $sy_{v}\in sxW_{J}$

  2. (2)

$y_{u}\in W_{J^{\prime}}$.

###### Proof.

To prove part (1), suppose that $y\in\tilde{x}W_{J}$ for some $\tilde{x}\in
W^{J}$. We will show that $\tilde{x}=x$. Since $y\in xW_{J}$ and $y_{v}\leq
y$, we must have $\tilde{x}\leq x$. Let $y_{u}=s_{1}\cdots s_{k}$ and
$y_{v}=t_{1}\cdots t_{k^{\prime}}$ be reduced decompositions. Then

$y=(s_{1}\cdots s_{k})(t_{1}\cdots t_{k^{\prime}})$

is also a reduced decomposition. Since $x\leq y$, there exists a subword of
$s_{1}\cdots s_{k}t_{1}\cdots t_{k^{\prime}}$ which corresponds to a reduced
word of $x$. Since $s_{i}\notin D_{L}(x)$ for all $i\leq k$, we must have that
$x\leq y_{v}$ and thus $x\leq\tilde{x}$. Hence $x=\tilde{x}$.

For part (2), since $y_{u}\leq y$ and $S(y)\subseteq J\cup S(x)$, we have that
$y_{u}\in W_{J\cup S(x)}$. We also have that $y_{u}\leq u\in W_{S\setminus
D_{L}(x)}$ and hence $S(y_{u})\subseteq(J\cup S(x))\setminus D_{L}(x)$. Let
$t\in S(y_{u})$. Since $x\leq y_{v}$, we have that $tx\leq y$. In particular,
since $y\in xW_{J}$, we must have that $tx\in x^{\prime}W_{J}$ for some
$x^{\prime}\in W^{J}$ with $x^{\prime}\leq x$. Now $t\notin D_{L}(x)$ which
implies $tx>x$. By Lemma 3.4, either $tx\in xW_{J}$ or $tx\in W^{J}$. If the
latter holds, then there is a contradiction since $x^{\prime}=tx$ and $tx>x$.
Thus we must have that $tx\in xW_{J}$ and $t\in J^{\prime}$. This implies
$S(y_{u})\subseteq J^{\prime}$. ∎

Lemma 3.6 implies that $sy_{v}\leq q^{\prime\prime}$ and thus $y_{v}\leq
sq^{\prime\prime}$ since $q^{\prime\prime}<sq^{\prime\prime}$. It also implies
$y_{u}\leq q^{\prime}$. By Proposition 3.2, we have

$y=y_{u}y_{v}\leq q^{\prime}\star(sq^{\prime\prime})=q.$

Theorem 2.1 now follows from Lemma 3.5.

∎

We provide examples of the above construction of maximal elements $q$ in
$[e,w]\cap xW_{J}$ for $w=s_{1}s_{2}s_{3}s_{2}s_{1}$ and $J=\\{s_{1},s_{2}\\}$
given in Section 2.2. First note that

$q=s_{1}\star s_{2}\star s_{2}\star s_{1}=s_{1}s_{2}s_{1}$

is the maximal element of $[e,w]\cap W_{J}$ (i.e when $x=e$). This element is
constructed using the Coxeter monoid product on the subsequence of the reduced
word $(s_{1},s_{2},s_{3},s_{2},s_{1})$ belonging to $J$. For the other $x\in
W^{J}$, the table below gives of choices of
$u,v,J^{\prime},q,q^{\prime\prime}$.

$x$ | $D_{L}(x)$ | $w=u\cdot v$ | $J^{\prime}$ | $q=q^{\prime}\star(s\cdot q^{\prime\prime})$
---|---|---|---|---
$s_{3}$ | $\\{s_{3}\\}$ | $(s_{1}s_{2})\cdot(s_{3}s_{2}s_{1})$ | $\\{s_{1}\\}$ | $s_{1}\star(s_{3}\cdot s_{2}s_{1})$
$s_{2}s_{3}$ | $\\{s_{2}\\}$ | $(s_{1}s_{3})\cdot(s_{2}s_{3}s_{1})$ | $\\{s_{3}\\}$ | $s_{3}\star(s_{2}\cdot s_{3}s_{1})$
$s_{1}s_{2}s_{3}$ | $\\{s_{1}\\}$ | $(s_{3}s_{2})\cdot(s_{1}s_{2}s_{3})$ | $\\{s_{2},s_{3}\\}$ | $s_{3}s_{2}\star(s_{1}\cdot s_{2}s_{3})$

We can verify that for $w=s_{1}s_{2}s_{3}s_{2}s_{1}$ our construction of $q$
indeed gives the unique maximal of $[e,w]\cap xW_{J}$ by checking the maximal
elements within each coset in Figure 2. For instance, when $x=s_{2}s_{3}$ we
get $q=s_{3}\star s_{2}s_{3}s_{1}=s_{3}s_{2}s_{3}s_{1}=s_{2}s_{3}s_{2}s_{1}$,
which is indeed the maximal element within the blue elements.

For another example, consider $w=s_{3}s_{1}s_{2}s_{4}s_{3}s_{2}s_{1}\in S_{5}$
with $J=S\setminus\\{s_{3}\\}=\\{s_{1},s_{2},s_{4}\\}$ and $x=s_{4}s_{3}$.
Here we see that $D_{L}(x)=\\{s_{4}\\}$ and the left-sided parabolic
composition of $w$ with respect to $S\setminus\\{s_{4}\\}$ is

$w=uv=(s_{3}s_{1}s_{2})(s_{4}s_{3}s_{2}s_{1}).$

Here we have $J^{\prime}=\\{s_{1},s_{3}\\}$ and we pick $s=s_{4}$ (this is the
only choice in this case). The maximal element of $[e,w]\cap xW_{J}$ is

$q=q^{\prime}\star(s\cdot q^{\prime\prime})=(s_{3}s_{1})\star(s_{4}\cdot
s_{3}s_{2}s_{1})=s_{3}s_{1}s_{4}s_{3}s_{2}s_{1}=(s_{4}s_{3})(s_{4}s_{1}s_{2}s_{1}).$

## References

  * [1] T. Alland and E. Richmond, Pattern avoidance and fiber bundle structures on Schubert varieties, J. Combin. Theory Ser. A, 154 (2018), pp. 533–550.
  * [2] S. Billey and A. Postnikov, Smoothness of Schubert varieties via patterns in root subsystems, Adv. in Appl. Math., 34 (2005), pp. 447–466.
  * [3] S. C. Billey, C. K. Fan, and J. Losonczy, The parabolic map, J. Algebra, 214 (1999), pp. 1–7.
  * [4] A. Björner and F. Brenti, Combinatorics of Coxeter groups, vol. 231 of Graduate Texts in Mathematics, Springer, New York, 2005.
  * [5] C. Gaetz and Y. Gao, Self-dual intervals in the Bruhat order, Selecta Math. (N.S.), 26 (2020), pp. Paper No. 77, 23.
  * [6] X. He, A subalgebra of 0-Hecke algebra, J. Algebra, 322 (2009), pp. 4030–4039.
  * [7] J. E. Humphreys, Reflection groups and Coxeter groups, vol. 29 of Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 1990.
  * [8] T. Kenney, Coxeter groups, Coxeter monoids and the Bruhat order, J. Algebraic Combin., 39 (2014), pp. 719–731.
  * [9] S. Kumar, Kac-Moody groups, their flag varieties and representation theory, vol. 204 of Progress in Mathematics, Birkhäuser Boston, Inc., Boston, MA, 2002.
  * [10] R. Mcalmon, S. Oh, and H. Yoo, Palindromic intervals in bruhat order and hyperplane arrangements, preprint, arXiv:1904.1104, (2019).
  * [11] P. N. Norton, $0$-Hecke algebras, J. Austral. Math. Soc. Ser. A, 27 (1979), pp. 337–357.
  * [12] E. Richmond and W. Slofstra, Billey-Postnikov decompositions and the fibre bundle structure of Schubert varieties, Math. Ann., 366 (2016), pp. 31–55.
  * [13] , Staircase diagrams and enumeration of smooth Schubert varieties, J. Combin. Theory Ser. A, 150 (2017), pp. 328–376.
  * [14] J. R. Stembridge, A short derivation of the Möbius function for the Bruhat order, J. Algebraic Combin., 25 (2007), pp. 141–148.
  * [15] A. van den Hombergh, About the automorphisms of the Bruhat-ordering in a Coxeter group, Nederl. Akad. Wetensch. Proc. Ser. A 77 Indag. Math., 36 (1974), pp. 125–131.


* [31] (nLab) Effect algebra https://ncatlab.org/nlab/show/effect+algebra.
  * [32] O. Ore, Number theory and its history, Dover, 1976.
  * [33] K. Ravindran, On a structure theory of effect algebras, PhD thesis, Kansas State University, 1996. https://www.proquest.com/pqdtglobal/results/8F18B6F1ECA44544PQ/1?accountid=14701.
  * [34] M. Rørdam, F. Larsen, N. J. Laustsen, An introduction to $K$-theory for $C^{\ast}$algebras, CUP, 2000.
  * [35] M. H. Stone, Postulates for Boolean algebras and generalized Boolean algebras, Am. J. Math. 57 (1935), 703-732.
  * [36] B. A. Ventura, A characterization of UHF $C^{\ast}$-algebras, J. Oper. Theory 24 (1990), 117–128.
  * [37] F. Wehrung, The dimension monoid of a lattice, arXiv:0501437.
  * [38] F. Wehrung, Refinement monoids, equidecomposability types, and Boolean inverse semigroups, LNM 2188, 2017.