# Kazhdan-Lusztig polynomials for $\widetilde{B}_{2}$

Karina Batistelli Universidad de Chile  Aram Bingham Tulane University of
Louisiana  and David Plaza Universidad de Talca

###### Abstract

In their seminal paper [KL79] Kazhdan and Lusztig define, for an arbitrary
Coxeter system $(W,S)$, a family of polynomials indexed by pairs of elements
of $W$. Despite their relevance and elementary definition, the explicit
computation of these polynomials is still one of the hardest open problems in
algebraic combinatorics. In this paper we explicitly compute Kazhdan-Lusztig
polynomials for a Coxeter system of type $\widetilde{B}_{2}$.

##  1 Introduction

Kazhdan-Lusztig polynomials lie at the intersection of representation theory,
geometry and algebraic combinatorics. Their relevance derives from the fact
that they elegantly express the answers to many difficult problems in the
aforementioned areas. Despite their straightforward definition (through a
recursive algorithm involving only elementary operations) and enormous efforts
made by several authors over the past forty years, in general the explicit
computation of Kazhdan-Lusztig polynomials remains elusive.

In this paper we compute Kazhdan-Lusztig polynomials in type
$\widetilde{B}_{2}$; for relevant background and related theory we refer the
reader to [EMTW20]. In order to present our results we introduce some
notation. The main protagonist in this paper is the affine Weyl group of type
$\widetilde{B}_{2}$, which we denote by $W$. It is a Coxeter group generated
by involutions $S=\\{s_{1},s_{2},s_{0}\\}$ with relations
$(s_{1}s_{2})^{4}=(s_{2}s_{0})^{4}=(s_{1}s_{0})^{2}=1$. As usual, we denote by
$\ell(\cdot)$ and $\leq$ the length and Bruhat order on $W$, respectively. It
is convenient to recall the realization of $W$ as the group of isometric
transformations of the plane generated by reflections in the lines that
support the sides of an isosceles right triangle as is illustrated in Figure
1. In this figure the triangle marked with a dot represents the identity of
$W$. The colors on the edges of the triangles represent the following simple
reflections: red is $s_{1}$, blue is $s_{2}$ and green is $s_{0}$. Given an
element $w\in W$ and an expression $s_{i_{1}}s_{i_{2}}\ldots s_{i_{k}}$ (not
necessarily reduced) of $w$ we define a sequence of triangles
$(\triangle_{0},\triangle_{1},\ldots\triangle_{k})$ as follows:
$\triangle_{0}$ is the identity triangle. Then $\triangle_{j+1}$ is obtained
from $\triangle_{j}$ by reflecting it through the side colored with
$s_{i_{j}}$. We identify $w$ with $\triangle_{k}$. Of course, this
identification does not depend on the choice of an expression for $w$.
Henceforth, we do not distinguish between elements of $W$ and triangles.

We split $W-\\{1\\}$ into three regions: The _big region_ (the region colored
using the lightest gray), the _thick region_ (the region colored by the
darkest gray) and the _thin region_ (the region colored with the intermediate
gray). The reader familiar with cells in Kazhdan-Lusztig theory might have
noticed the small discrepancy between Figure 1 and [Lus85, Figure 2]. The
big/thick/thin regions coincide very nearly with two-sided cells, though we
will prefer our description in order to keep this paper self-contained.

1.0 1.0 [unit=1.414213562373,gridcolor=cb-burgundy,gridwidth=1pt,
subgridcolor=cb-green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(6,6)
[unit=1.414213562373,gridcolor=cb-burgundy,gridwidth=1pt, subgridcolor=cb-
green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(4,8)
[unit=1.414213562373,gridcolor=cb-burgundy,gridwidth=1pt, subgridcolor=cb-
green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(2,10)
[unit=1.414213562373,gridcolor=cb-burgundy,gridwidth=1pt, subgridcolor=cb-
green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(0,12)
[unit=1.414213562373,gridcolor=cb-burgundy, gridwidth=1pt, subgridcolor=cb-
green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(8,4)
[unit=1.414213562373,gridcolor=cb-burgundy, gridwidth=1pt, subgridcolor=cb-
green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(10,2)
[unit=1.414213562373,gridcolor=cb-burgundy, gridwidth=1pt, subgridcolor=cb-
green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(12,0) [unit=1,gridcolor=cb-
blue, gridwidth=1pt, gridcolor=cb-blue,subgriddiv=1,
subgridwidth=1pt,subgriddots=15, gridlabels=0](4,5)(16,17) $\bullet$

Figure 1: Geometric realization of $W$.

Let $\mathcal{H}$ be the Hecke algebra of $W$ with standard basis
$\\{\mathbf{H}_{w}\\}_{w\in W}$ and Kazhdan-Lusztig basis (canonical basis)
$\\{{\underline{\mathbf{H}}}_{w}\\}_{w\in W}$. Kazhdan-Lusztig polynomials
$\\{h_{x,w}(v)\mid x,w\in W\\}$ are defined by the equality

${\underline{\mathbf{H}}}_{w}=\sum_{x\in W}h_{x,w}(v)\mathbf{H}_{x}.$ (1.1)

There is a group automorphism $\varphi:W\rightarrow W$ which interchanges
$s_{0}$ and $s_{1}$ and fixes $s_{2}$. This extends to a Hecke algebra
automorphism which we also denote by $\varphi$. We have
${\underline{\mathbf{H}}}_{\varphi(w)}=\varphi({\underline{\mathbf{H}}}_{w})$
for all $w\in W$. To condense notation we often write
$w^{\prime}:=\varphi(w)$, for $w\in W$.

In this paper we prove an explicit formula for ${\underline{\mathbf{H}}}_{w}$
for all $w\in W$ located in either the big region or the thick region, and we
conjecture explicit formulas for the thin region. The remainder of this
introduction is devoted to explaining these formulas.

We begin by considering elements in the big region. Let $a=s_{1}s_{2}s_{1}$,
$b=s_{0}s_{2}s_{0}$, $c=s_{1}s_{2}s_{0}s_{2}$, and $d=s_{0}s_{2}s_{1}s_{2}$.
Let $\mathbb{N}$ be the set of non-negative integers. For
$(m,n)\in\mathbb{N}^{2}$ we define

$\theta(m,n)=\begin{cases}{(ab)^{k}\,a}\,s_{2}\,d^{n},&\text{ if $m=2k$; }\\\
(ab)^{k+1}\,s_{2}\,c^{n},&\text{ if $m=2k+1$. }\end{cases}$ (1.2)

We define $t_{m}=s_{0}$ for $m$ even and $t_{m}=s_{1}$ for $m$ odd. Then
(modulo $\varphi$) all the elements in the big region are of the form
$x\theta(m,n)y$, where $x\in\\{1,s_{0},s_{2}s_{0},s_{1}s_{2}s_{0}\\}$ and
$y\in\\{1,t_{m},t_{m}s_{2},t_{m}s_{2}t_{m}^{\prime}\\}$.

For $(m,n)\in\mathbb{N}^{2}$ we define

$\operatorname{Supp}(m,n)=\left\\{\begin{array}[]{ll}\\{(m-2i,n-j)\in\mathbb{N}^{2}\,|\,i,j\in\mathbb{N}\\},&\mbox{if
}m\mbox{ is odd;}\\\
\\{(m-2i,n-j)\in\mathbb{N}^{2}\,|\,i,j\in\mathbb{N}\\}-\\{(0,b)\,\
\,|\,b\not\equiv n\bmod 2\\},&\mbox{if }m\mbox{ is even. }\end{array}\right.$
(1.3)

For $w\in W$ we define

$\mathbf{N}_{w}=\sum_{x\leq w}v^{l(w)-l(x)}\mathbf{H}_{x}.$ (1.4)

######  Theorem 1.1.

Let $(m,n)\in\mathbb{N}^{2}$. Then, we have

${\underline{\mathbf{H}}}_{\theta(m,n)}=\sum_{(a,b)\in\operatorname{Supp}(m,n)}v^{(m-a)+2(n-b)}\mathbf{N}_{\theta(a,b)}.$
(1.5)

Furthermore, if $x\in\\{1,s_{0},s_{2}s_{0},s_{1}s_{2}s_{0}\\}$ and
$y\in\\{1,t_{m},t_{m}s_{2},t_{m}s_{2}t_{m}^{\prime}\\}$ then
${\underline{\mathbf{H}}}_{x\theta(m,n)y}=X{\underline{\mathbf{H}}}_{\theta(m,n)}Y$,
where

$X=\left\\{\begin{array}[]{ll}1,&\mbox{if }x=1;\\\
{\underline{\mathbf{H}}}_{s_{0}},&\mbox{if }x=s_{0};\\\
{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{0}}-1,&\mbox{if
}x=s_{2}s_{0};\\\
{\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{0}}-{\underline{\mathbf{H}}}_{s_{1}}-{\underline{\mathbf{H}}}_{s_{0}},&\mbox{if
}x=s_{1}s_{2}s_{0};\\\
\end{array}\right.Y=\left\\{\begin{array}[]{ll}1,&\mbox{if }y=1;\\\
{\underline{\mathbf{H}}}_{t_{m}}&\mbox{if }y=t_{m};\\\
{\underline{\mathbf{H}}}_{t_{m}}{\underline{\mathbf{H}}}_{s_{2}}-1&\mbox{if
}y=t_{m}s_{2};\\\
{\underline{\mathbf{H}}}_{t_{m}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{t_{m}^{\prime}}-{\underline{\mathbf{H}}}_{t_{m}}-{\underline{\mathbf{H}}}_{t_{m}^{\prime}}&\mbox{if
}y=t_{m}s_{2}t_{m}^{\prime}.\end{array}\right.$

We now move to the thick region. We denote by $\mathcal{N}$ (resp.
$\mathcal{S}$, $\mathcal{E}$ and $\mathcal{W}$) the sub-region of the thick
region formed by triangles located to the north (resp. south, east and west)
of the identity triangle. Consider the infinite sequence

$\\{a_{n}\\}_{n=1}^{\infty}=(s_{1},s_{2},s_{1},s_{0},s_{2},s_{0},s_{1},s_{2},s_{1},s_{0},s_{2},s_{0},\ldots).$
(1.6)

We define $x_{n}=a_{1}\cdots a_{n}$ and
$\overline{x}_{n}=s_{1}s_{2}s_{0}x_{n-3}$. Then, $\mathcal{N}=\\{x_{n}\mid
n\geq 1\\}\cup\\{\overline{x}_{3n}\mid n\geq 1\\}$. In what follows we refer
to $\mathcal{N}$ as the north wall. We notice that
$\mathcal{S}=\varphi(\mathcal{N})$. We define $e_{n}=s_{1}x_{n}^{\prime}$.
Then,

$\mathcal{E}=\\{e_{n}\mid n\geq 1\\}\cup\\{e_{3k}^{\prime}\mid k\geq 1\\}.$

Finally, we define $w_{n}=s_{2}e_{n}$. Then, we have

$\mathcal{W}=\\{w_{n}\mid n\geq 1\\}\cup\\{w_{3k}^{\prime}\mid k\geq
1\\}\cup\\{s_{2},s_{2}s_{1},s_{2}s_{0}\\}.$

This completes the description of the elements in the thick region.

The following theorem provides formulas for Kazhdan-Lusztig basis elements
indexed by elements located in $\mathcal{N}$. As we already pointed out
$\mathcal{S}=\varphi(\mathcal{N})$. Therefore, the formulas for elements
located in $\mathcal{S}$ are obtained by applying $\varphi$ to the formulas in
the theorem. For the sake of brevity, in this introduction we omit the
formulas for the elements located in $\mathcal{E}$ and $\mathcal{W}$. These
formulas are presented in §5.2.

######  Theorem 1.2.

For all $k\geq 2$ we have

${\underline{\mathbf{H}}}_{x_{f(k)}}=\mathbf{N}_{x_{f(k)}}+v\mathbf{N}_{x_{f(k-1)}}+\left(\sum_{j=2}^{k-1}v^{j-1}(\mathbf{N}_{e_{f(k-j)}}+\mathbf{N}_{u_{f(k-j)}})\right)+v^{k-1}\mathbf{N}_{s_{1}s_{0}},$
(1.7)

where $f(k):=3k+1$ and $u_{n}=s_{2}x_{n}$. Furthermore, using the convention
of Remark 3.8 we have

$\displaystyle{\underline{\mathbf{H}}}_{x_{3k+1}}{\underline{\mathbf{H}}}_{s_{2}}$
$\displaystyle={\underline{\mathbf{H}}}_{x_{3k+2}},$ (1.8)
$\displaystyle{\underline{\mathbf{H}}}_{x_{3k+2}}{\underline{\mathbf{H}}}_{s_{0}}$
$\displaystyle=\left\\{\begin{array}[]{ll}{\underline{\mathbf{H}}}_{\overline{x}_{3k+3}}+{\underline{\mathbf{H}}}_{x_{3k+1}}+{\underline{\mathbf{H}}}_{\theta(k-1,0)}+{\underline{\mathbf{H}}}_{s_{1}\theta^{\prime}(k-2,0)}+{\underline{\mathbf{H}}}_{\theta(k-3,0)},&\mbox{if
}k\mbox{ is even;}\\\
{\underline{\mathbf{H}}}_{x_{3k+3}}+{\underline{\mathbf{H}}}_{x_{3k+1}}+{\underline{\mathbf{H}}}_{s_{1}s_{2}s_{0}\theta(k-2,0)},&\mbox{if
}k\mbox{ is odd.}\end{array}\right.$ (1.11)
$\displaystyle{\underline{\mathbf{H}}}_{x_{3k+2}}{\underline{\mathbf{H}}}_{s_{1}}$
$\displaystyle=\left\\{\begin{array}[]{ll}{\underline{\mathbf{H}}}_{x_{3k+3}}+{\underline{\mathbf{H}}}_{x_{3k+1}}+{\underline{\mathbf{H}}}_{s_{1}s_{2}s_{0}\theta(k-2,0)},&\mbox{if
}k\mbox{ is even;}\\\
{\underline{\mathbf{H}}}_{\overline{x}_{3k+3}}+{\underline{\mathbf{H}}}_{x_{3k+1}}+{\underline{\mathbf{H}}}_{\theta(k-1,0)}+{\underline{\mathbf{H}}}_{s_{1}\theta^{\prime}(k-2,0)}+{\underline{\mathbf{H}}}_{\theta(k-3,0)},&\mbox{if
}k\mbox{ is odd.}\end{array}\right.$ (1.14)

Conjectural formulas for ${\underline{\mathbf{H}}}_{w}$ for $w$ located in the
thin region are presented in §6. It is likely that they could be proved by the
methods used to obtain formulas in the other regions, though the accounting
becomes more difficult due to the number and type of terms appearing in the
explicit formulas. We leave this task for a future investigation.

The alert reader might have noticed that the results presented in this
introduction provide formulas for Kazhdan-Lusztig basis elements rather than
Kazhdan-Lusztig polynomials. By the nature of our formulas, in order to
compute Kazhdan-Lusztig polynomials we need to understand the elements
$\mathbf{N}_{w}$, or, equivalently, to understand the sets $\lessdot
w:=\\{x\leq w\mid x\in W\\}$. This is exactly the content of §2. We will
finish this introduction with an example that illustrates how our formulas can
be used in order to efficiently compute Kazhdan-Lusztig polynomials.

Suppose we want to compute $h_{\overline{x}_{3n},x_{3m}}(v)$ for integers
$m>n\geq 2$, $m$ odd and $n$ even. We notice that taking the coefficient of
$\mathbf{H}_{\overline{x}_{3n}}$ on both sides of (1.14) and using (3.10) we
obtain

$v^{-1}h_{\overline{x}_{3n},x_{3m-1}}(v)+h_{x_{3n-1},x_{3m-1}}(v)=h_{\overline{x}_{3n},x_{3m}}(v)+h_{\overline{x}_{3n},x_{3m-2}}(v)+h_{\overline{x}_{3n},s_{1}s_{2}s_{0}\theta(m-3,0)}(v).$
(1.15)

On the other hand, (1.8) and (3.10) imply

$\displaystyle h_{\overline{x}_{3n},x_{3m-1}}(v)$
$\displaystyle=vh_{\overline{x}_{3n},x_{3m-2}}(v)+h_{s_{1}s_{2}s_{0}\theta(n-2,0),x_{3m-2}}(v),$
(1.16) $\displaystyle h_{x_{3n-1},x_{3m-1}}(v)$
$\displaystyle=v^{-1}h_{x_{3n-1},x_{3m-2}}(v)+h_{x_{3n-2},x_{3m-2}}(v).$
(1.17)

For an integer $l$ we define $F_{l}(v)=\displaystyle\sum_{i=0}^{l-1}v^{2i}$.

We can use (1.7) and the description of lower intervals in §2 to obtain

$\displaystyle h_{\overline{x}_{3n},x_{3m-2}}(v)$
$\displaystyle=v^{m-n}\left(F_{m-n}(v)+F_{m-n-2}(v)\right),$ (1.18)
$\displaystyle h_{s_{1}s_{2}s_{0}\theta(n-2,0),x_{3m-2}}(v)$
$\displaystyle=v^{m-n+1}\left(F_{m-n-1}(v)+F_{m-n-3}(v)\right),$ (1.19)
$\displaystyle h_{x_{3n-1},x_{3m-2}}(v)$
$\displaystyle=v^{m-n+1}\left(F_{m-n}(v)+F_{m-n-2}(v)\right),$ (1.20)
$\displaystyle h_{x_{3n-2},x_{3m-2}}(v)$
$\displaystyle=v^{m-n}\left(F_{m-n+1}(v)+F_{m-n-1}(v)\right).$ (1.21)

Similarly, using Theorem 1.1 (or Lemma 4.13) we obtain

$h_{\overline{x}_{3n},s_{1}s_{2}s_{0}\theta(m-3,0)}(v)=v^{m-n}\left(F_{m-n}(v)+F_{m-n-2}(v)\right).$
(1.22)

Putting all these together we obtain

$h_{\overline{x}_{3n},x_{3m}}(v)=v^{m-n}(F_{m-n+1}(v)+2F_{m-n-1}(v)+F_{m-n-3}(v)).$
(1.23)

Closed formulas for $h_{x,w}(v)$, such as (1.23), can be obtained using the
results in this paper for all $x\in W$ and for all $w\in W$ located either in
the big region or the thick region. We have chosen this specific example in
order to point out a certain discrepancy between an identity appearing in
[Lus97, 1.(a)] and our results. Concretely, in that paper it is claimed
that111We have slightly modified the original statement in order to match the
conventions in this paper.

$\mu(\overline{x}_{3n},x_{3m})=1,$ (1.24)

for all $m>n>0$, $m$ odd, $n$ even, where $\mu(x,w)$ denotes the coefficient
of $v$ in the Kazhdan-Lusztig polynomial $h_{x,w}(v)$222We remark that
throughout this paper we follow Soergel’s normalization in [Soe97].. However,
it is clear from (1.23) that $\mu(\overline{x}_{3n},x_{3m})=0$ if $m-n>1$.
Equation (1.24) allows the author to conclude that the $W$-graph of an affine
Weyl group of type $\widetilde{B}_{2}$ is not locally finite. This conclusion
was later shown to be true by Wang [Wan11] through a different set of examples
which are consistent with our results.

This paper is organized as follows. In Section 2 we describe geometrically the
lower intervals in the Bruhat order of the elements of the big region and the
thick region. We specify the region corresponding to each lower interval
inductively and obtain closed formulas for their sizes. In Section 3 we
introduce the Hecke algebra of $W$ and prove several technical lemmas
containing identities which will be necessary for the computations that
follow. Our main results lie in Sections 4 and 5, which provide explicit
formulas for the Kazhdan-Lusztig basis elements of elements in the big region
and the thick region respectively. Finally, in Section 6 we conjecture the
explicit formulas of the Kazhdan-Lusztig basis elements corresponding to the
elements of the thin region.

### Acknowledgements

The first author is supported by Fondecyt project 3190144. The third author
was partially supported by Fondecyt project 1200341. The authors would like to
thank Nicolas Libedinsky for useful discussions and all the participants of
the "Soergel bimodules learning seminar", which took place at the Universidad
de Chile during 2020, and from which this project and collaboration was born.
We also wish to acknowledge the contributors and developers of SageMath
[Sag20] of which we have made indispensable use.

##  2 Lower intervals in the Bruhat order

Throughout this paper $W$ denotes the affine Weyl group of type
$\widetilde{B}_{2}$ with generators $S=\\{s_{0},s_{1},s_{2}\\}$. In this
section we provide a geometric description for lower Bruhat intervals and
obtain formulas for their size. Given $w\in W$ we define $\leq w:=\\{x\in
W\mid x\leq w\\}$ and $\left\lvert w\right\rvert:=\left\lvert\leq
w\right\rvert$. We also define $D_{R}(w):=\\{s\in S\mid ws<w\\}$ and
$D_{L}(w)=D_{R}(w^{-1})$.

###  2.1 Lower intervals for the big region

We recall from (1.2) the definition of the elements $\theta(m,n)$. We notice
that $D_{L}(\theta(m,n))=\\{s_{1},s_{2}\\}$ and
$D_{R}(\theta(m,n))=\\{s_{2},t_{m}\\}$. In particular, $D_{R}(\theta(m,n))$
only depends on the parity of $m$. Left and right descent sets characterize
$\theta$-elements in the following sense: If $x\in W$ satisfies
$D_{L}(x)=\\{s_{1},s_{2}\\}$ and $D_{R}(x)=\\{s_{2},t\\}$ for some
$t\in\\{s_{0},s_{1}\\}$, then there exists $(m,n)\in\mathbb{N}^{2}$ such that
$x=\theta(m,n)$.

All these $\theta$-elements belong to the same connected component of the big
region. We denote this connected component by $\mathfrak{C}$. All of the
elements in $\mathfrak{C}$ are of the form $\theta(m,n)x$ for some
$x\in\\{1,t_{m},t_{m}s_{2},t_{m}s_{2}t_{m}^{\prime}\\}$.

######  Lemma 2.1.

The set $\leq\theta(m,0)$ is the square $S(m,0)$ defined as the smallest
square satisfying the following properties:

  * •

$S(m,0)$ contains $\theta(m,0)$.

  * •

The center of $S(m,0)$, say $O$, is the upper vertex of the identity triangle.

  * •

The two diagonals of $S(m,0)$ are the horizontal and vertical lines passing
through $O$.

###### Proof.

We proceed by induction on $m$. For $m=0$ the claim is clear. We now assume
the lemma holds for some $m\geq 0$. Note that
$\theta(m+1,0)=\theta(m,0)t_{m}s_{2}t_{m}$. Let $w\leq\theta(m+1,0)$. Then
$w=xy$ for some $x\leq\theta(m,0)$ and $y\leq t_{m}s_{2}t_{m}$. By our
inductive hypothesis we know that $x\in S(m,0)$. It follows that $w\in
S(m+1,0)$. Therefore, $\leq\theta(m+1,0)\subseteq S(m+1,0)$. Conversely, let
$w\in S(m+1,0)$. If $w\in S(m,0)$ we are done, so we can assume that $w\not\in
S(m,0)$. It is easy to see that $w$ can be obtained from some $x\in S(m,0)$ by
reflecting it along one of the following sequences: $t_{m}$, $t_{m}s_{2}$ or
$t_{m}s_{2}t_{m}$. Once again, our inductive hypothesis guarantees that
$w\leq\theta(m+1,0)$. Thus $S(m+1,0)\subseteq(\leq\theta(m+1,0))$. ∎

Any square obtained from $S(0,0)$ by a translation will be called a
$B_{2}$-square. Let $m,n\in\mathbb{N}$. We recursively define sets $S(m,n)$ as
follows: If $n=0$ then $S(m,0)$ is defined as in Lemma 2.1. Assume that
$S(m,n)$ has been defined. Then $S(m,n+1)$ is defined as the set obtained from
$S(m,n)$ by surrounding its boundary with $B_{2}$-squares. This is illustrated
in Figure 2. Starting from $S(4,0)$ (the black square), we obtain $S(4,1)$ by
adding $20$ $B_{2}$-squares (in dark yellow). Then, we obtain $S(4,2)$ by
adding $24$ $B_{2}$-squares (in light yellow).

1.0 1.0 [unit=1,gridcolor=cb-blue, subgridcolor=cb-blue,subgriddiv=1,
subgridwidth=0.8pt,subgriddots=15, gridlabels=0](2,3)(18,19)
[unit=1.414213562373,gridcolor=cb-burgundy, subgridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(8,8)
[unit=1.414213562373,gridcolor=cb-burgundy, subgridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(6,10)
[unit=1.414213562373,gridcolor=cb-burgundy, subgridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(4,12)
[unit=1.414213562373,gridcolor=cb-burgundy, subgridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(2,14)
[unit=1.414213562373, gridcolor=cb-burgundy, subgridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(0,16)
[unit=1.414213562373,gridcolor=cb-burgundy, subgridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(10,6)
[unit=1.414213562373,gridcolor=cb-burgundy, subgridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(12,4)
[unit=1.414213562373,gridcolor=cb-burgundy, subgridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(14,2)
[unit=1.414213562373,gridcolor=cb-burgundy, subgridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(16,0)
$\bullet$

Figure 2: Lower intervals: From lightest to darkest gray
$\theta(0,0)$–$\theta(4,0)$. Darkest yellow $\theta(4,1)$ and lightest yellow
$\theta(4,2)$.

######  Definition 2.2.

Let $x\in W$. We define $\partial(x)$ to be the set formed by all the elements
$y\leq x$ such that the triangle associated to $y$ has a side belonging to the
boundary of $\leq x$. We partition $\partial(x)$ into three (possibly empty)
sets according to the color of the relevant side. More precisely, we define
$\partial_{s_{k}}(x)$ to be the set of all $y\in\partial(x)$ such that the
side of $y$ belonging to the boundary of $\leq x$ is colored by $s_{k}$.

######  Definition 2.3.

For any $X,Y\subseteq W$ we define $XY:=\\{xy\mid x\in X,\,y\in Y\\}.$ In case
$X=\\{x\\}$, we may also write $x(Y)$ to mean the same.

######  Lemma 2.4.

For all $m,n\in\mathbb{N}$ we have $\leq\theta(m,n)=S(m,n)$.

###### Proof.

We proceed by induction on $n$. The case $n=0$ is covered by Lemma 2.1. Assume
the lemma holds for some fixed $n$. We have
$\theta(m,n+1)=\theta(m,n)t_{m}s_{2}t_{m}^{\prime}s_{2}$ and this implies

$\leq\theta(m,n+1)=(\leq\theta(m,n))(\leq t_{m}s_{2}t_{m}^{\prime}s_{2}).$
(2.1)

From this it is easy to see, using our inductive hypothesis, that
$(\leq\theta(m,n+1))\subseteq S(m,n+1)$.
Conversely, we have

$S(m,n+1)=S(m,n)\cup\bigcup_{x\in X}\partial(\theta(m,n))x,$ (2.2)

where
$X=\\{t_{m},t_{m}s_{2},t_{m}s_{2}t_{m}^{\prime},t_{m}s_{2}t_{m}^{\prime}s_{2}\\}$.
It follows from our inductive hypothesis and (2.1) that
$S(m,n+1)\subseteq(\leq\theta(m,n+1))$. We conclude that
$S(m,n+1)=(\leq\theta(m,n+1))$ as desired. ∎

######  Corollary 2.5.

For all $m,n\in\mathbb{N}$ we have
$\left\lvert\theta(m,n)\right\rvert=8(m^{2}+2m+4mn+2n^{2}+2n+1)$. In
particular, we have $\left\lvert\theta(m,0)\right\rvert=8(m+1)^{2}$.

###### Proof.

The equality follows easily from Lemma 2.1 and Lemma 2.4 by a counting
argument. Indeed, $\leq\theta(m,0)$ is made of $(m+1)^{2}$ (non-intersecting)
$B_{2}$-squares, which leads to
$\left\lvert\leq\theta(m,0)\right\rvert=8(m+1)^{2}$. Furthermore, the number
of $B_{2}$-squares that one needs to add to $\leq\theta(m,0)$ in order to
obtain $\leq\theta(m,n)$ is $4(m+1)n+2n(n-1)$. ∎

1.0 1.0 [unit=1.414213562373,gridcolor=cb-burgundy,gridwidth=1pt,
subgridcolor=cb-green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(6,6)
[unit=1.414213562373,gridcolor=cb-burgundy,gridwidth=1pt, subgridcolor=cb-
green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(4,8)
[unit=1.414213562373,gridcolor=cb-burgundy,gridwidth=1pt, subgridcolor=cb-
green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(2,10)
[unit=1.414213562373,gridcolor=cb-burgundy,gridwidth=1pt, subgridcolor=cb-
green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(0,12)
[unit=1.414213562373,gridcolor=cb-burgundy, gridwidth=1pt, subgridcolor=cb-
green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(8,4)
[unit=1.414213562373,gridcolor=cb-burgundy, gridwidth=1pt, subgridcolor=cb-
green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(10,2)
[unit=1.414213562373,gridcolor=cb-burgundy, gridwidth=1pt, subgridcolor=cb-
green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(12,0) [unit=1,gridcolor=cb-
blue, gridwidth=1pt, gridcolor=cb-blue,subgriddiv=1,
subgridwidth=1pt,subgriddots=15, gridlabels=0](4,5)(16,17) $\bullet$

(a) From lightest to darkest grey: Lower intervals of $\theta(2,1)$,
$\theta(2,1)s_{0}$, $\theta(2,1)s_{0}s_{2}$ and $\theta(2,1)s_{0}s_{2}s_{1}$.

1.0 1.0 [unit=1.414213562373,gridcolor=cb-burgundy,gridwidth=1pt,
subgridcolor=cb-green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(6,6)
[unit=1.414213562373,gridcolor=cb-burgundy,gridwidth=1pt, subgridcolor=cb-
green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(4,8)
[unit=1.414213562373,gridcolor=cb-burgundy,gridwidth=1pt, subgridcolor=cb-
green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(2,10)
[unit=1.414213562373,gridcolor=cb-burgundy,gridwidth=1pt, subgridcolor=cb-
green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(0,12)
[unit=1.414213562373,gridcolor=cb-burgundy, gridwidth=1pt, subgridcolor=cb-
green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(8,4)
[unit=1.414213562373,gridcolor=cb-burgundy, gridwidth=1pt, subgridcolor=cb-
green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(10,2)
[unit=1.414213562373,gridcolor=cb-burgundy, gridwidth=1pt, subgridcolor=cb-
green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(12,0) [unit=1,gridcolor=cb-
blue, gridwidth=1pt, gridcolor=cb-blue,subgriddiv=1,
subgridwidth=1pt,subgriddots=15, gridlabels=0](4,5)(16,17) $\bullet$

(b) From lightest to darkest grey: Lower intervals of $s_{0}\theta(2,1)$,
$s_{0}\theta(2,1)s_{0}$, $s_{0}\theta(2,1)s_{0}s_{2}$ and
$s_{0}\theta(2,1)s_{0}s_{2}s_{1}$.

1.0 1.0 [unit=1.414213562373,gridcolor=cb-burgundy,gridwidth=1pt,
subgridcolor=cb-green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(6,6)
[unit=1.414213562373,gridcolor=cb-burgundy,gridwidth=1pt, subgridcolor=cb-
green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(4,8)
[unit=1.414213562373,gridcolor=cb-burgundy,gridwidth=1pt, subgridcolor=cb-
green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(2,10)
[unit=1.414213562373,gridcolor=cb-burgundy,gridwidth=1pt, subgridcolor=cb-
green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(0,12)
[unit=1.414213562373,gridcolor=cb-burgundy, gridwidth=1pt, subgridcolor=cb-
green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(8,4)
[unit=1.414213562373,gridcolor=cb-burgundy, gridwidth=1pt, subgridcolor=cb-
green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(10,2)
[unit=1.414213562373,gridcolor=cb-burgundy, gridwidth=1pt, subgridcolor=cb-
green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(12,0) [unit=1,gridcolor=cb-
blue, gridwidth=1pt, gridcolor=cb-blue,subgriddiv=1,
subgridwidth=1pt,subgriddots=15, gridlabels=0](4,5)(16,17) $\bullet$

(c) From lightest to darkest grey: Lower intervals of $s_{2}s_{0}\theta(2,1)$,
$s_{2}s_{0}\theta(2,1)s_{0}$, $s_{2}s_{0}\theta(2,1)s_{0}s_{2}$ and
$s_{2}s_{0}\theta(2,1)s_{0}s_{2}s_{1}$.

1.0 1.0 [unit=1.414213562373,gridcolor=cb-burgundy,gridwidth=1pt,
subgridcolor=cb-green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(6,6)
[unit=1.414213562373,gridcolor=cb-burgundy,gridwidth=1pt, subgridcolor=cb-
green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(4,8)
[unit=1.414213562373,gridcolor=cb-burgundy,gridwidth=1pt, subgridcolor=cb-
green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(2,10)
[unit=1.414213562373,gridcolor=cb-burgundy,gridwidth=1pt, subgridcolor=cb-
green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(0,12)
[unit=1.414213562373,gridcolor=cb-burgundy, gridwidth=1pt, subgridcolor=cb-
green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(8,4)
[unit=1.414213562373,gridcolor=cb-burgundy, gridwidth=1pt, subgridcolor=cb-
green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(10,2)
[unit=1.414213562373,gridcolor=cb-burgundy, gridwidth=1pt, subgridcolor=cb-
green-lime,subgriddiv=2,
subgridwidth=1pt,subgriddots=0,gridlabels=0](0,0)(12,0) [unit=1,gridcolor=cb-
blue, gridwidth=1pt, gridcolor=cb-blue,subgriddiv=1,
subgridwidth=1pt,subgriddots=15, gridlabels=0](4,5)(16,17) $\bullet$

(d) From lightest to darkest grey: Lower intervals of
$s_{1}s_{2}s_{0}\theta(2,1)$, $s_{1}s_{2}s_{0}\theta(2,1)s_{0}$,
$s_{1}s_{2}s_{0}\theta(2,1)s_{0}s_{2}$ and
$s_{1}s_{2}s_{0}\theta(2,1)s_{0}s_{2}s_{1}$.

Figure 3: Lower intervals in the big region.

We now continue with the description of the sets $\leq\theta(m,n)t_{m}$,
$\leq\theta(m,n)t_{m}s_{2}$ and $\leq\theta(m,n)t_{m}s_{2}t_{m}^{\prime}$. In
order to obtain $\leq\theta(m,n)t_{m}$, we take as a starting point
$\leq\theta(m,n)=S(m,n)$ and we add to it the triangles that have an adjoining
side matching the color of $t_{m}$. Similarly, we can obtain
$\leq\theta(m,n)t_{m}s_{2}$ from $\leq\theta(m,n)t_{m}$ and
$\leq\theta(m,n)t_{m}s_{2}t^{\prime}_{m}$ from $\leq\theta(m,n)t_{m}s_{2}$. In
formulas we have

$\displaystyle\leq\theta(m,n)t_{m}=$
$\displaystyle\leq\theta(m,n)\,\sqcup\,\partial_{t_{m}}(\theta(m,n))t_{m}.$
(2.3) $\displaystyle\leq\theta(m,n)t_{m}s_{2}=$
$\displaystyle\leq\theta(m,n)t_{m}\,\sqcup\,\partial_{s_{2}}(\theta(m,n)t_{m})s_{2};$
(2.4) $\displaystyle\leq\theta(m,n)t_{m}s_{2}t_{m}^{\prime}=$
$\displaystyle\leq\theta(m,n)t_{m}s_{2}\,\sqcup\,\partial_{t_{m}^{\prime}}(\theta(m,n)t_{m}s_{2})t_{m}^{\prime}.$
(2.5)

This construction is illustrated in Figure 3(a) for $\theta(2,1)$. With this
description in hand we are in position to obtain the sizes of these sets.

######  Lemma 2.6.

Let $m,n\in\mathbb{N}$. Then we have

$\displaystyle\left\lvert\theta(m,n)t_{m}\right\rvert$
$\displaystyle=8(m^{2}+3m+4mn+2n^{2}+4n+2),$ (2.6)
$\displaystyle\left\lvert\theta(m,n)t_{m}s_{2}\right\rvert$
$\displaystyle=8(m^{2}+4m+4mn+2n^{2}+5n+3),$ (2.7)
$\displaystyle\left\lvert\theta(m,n)t_{m}s_{2}t_{m}^{\prime}\right\rvert$
$\displaystyle=8(m^{2}+5m+4mn+2n^{2}+6n+4).$ (2.8)

###### Proof.

It is a straightforward counting exercise to show that
$\left\lvert\partial_{t_{m}}(\theta(m,n))\right\rvert=8(m+2n+1)$. Thus (2.6)
follows from Corollary 2.5 and (2.3). Similarly, we have that
$\left\lvert\partial_{s_{2}}(\theta(m,n)t_{m})\right\rvert=8(2m+3n+2)$. This
gives us (2.7) by combining (2.4) and the already proved identity (2.6).
Finally, we obtain (2.8) by combining (2.5) and the already proved identity
(2.7), together with the equality
$\left\lvert\partial_{t_{m}^{\prime}}(\theta(m,n)t_{m}s_{2})\right\rvert=8(3m+4n+1)$.
∎

We now move on to the description of the remaining components of the big
region. We begin with the region $s_{0}\mathfrak{C}$. Let $w=s_{0}x$ for some
$x\in\mathfrak{C}$. Then $\leq w=\leq x\cup s_{0}(\leq x)$. Geometrically,
this implies that $\leq w$ can be obtained as the union of $\leq x$ with the
image of $\leq x$ under the reflection through the green line that supports a
side of the identity triangle. Since we have already obtained a geometric
description of all the sets $\leq x$ for $x\in\mathfrak{C}$, we now have a
geometric description of all the sets $\leq w$ for $w\in s_{0}\mathfrak{C}$.
Examples are given in Figure 3(b), obtained using those from Figure 3(a).

We now describe lower intervals for elements in $s_{2}s_{0}\mathfrak{C}$. Let
$w\in s_{2}s_{0}\mathfrak{C}$. Then $w=s_{2}x$ for some $x\in
s_{0}\mathfrak{C}$. Arguing as in the previous paragraph, we get that $\leq w$
is the union of $\leq x$ with the image of $\leq x$ under the reflection
through the blue line that supports a side of the identity triangle. This is
illustrated in Figure 3(c) using the examples from Figure 3(b).

Finally, we describe the lower intervals for elements in
$s_{1}s_{2}s_{0}\mathfrak{C}$. Let $w=s_{1}x$ for some $x\in
s_{2}s_{0}\mathfrak{C}$. This time $\leq w$ corresponds to the union of $\leq
x$ with the image of $\leq x$ under the reflection through the red line that
supports a side of the identity triangle. We have illustrated this case in
Figure 3(d) starting from the corresponding pictures in Figure 3(c).

Having described the lower intervals geometrically it is now an easy (though
tedious) task to determine the size of these sets. For space reasons, we omit
the proof and leave the reader with the resulting formulas.

######  Lemma 2.7.

Let $m,n\in\mathbb{N}$. Then,

$\displaystyle\left\lvert s_{0}\theta(m,n)\right\rvert$
$\displaystyle=8(m^{2}+3m+4mn+2n^{2}+4n+2)$ (2.9) $\displaystyle\left\lvert
s_{2}s_{0}\theta(m,n)\right\rvert$ $\displaystyle=8(m^{2}+4m+4mn+2n^{2}+6n+2)$
(2.10) $\displaystyle\left\lvert s_{1}s_{2}s_{0}\theta(m,n)\right\rvert$
$\displaystyle=8(m^{2}+5m+4mn+2n^{2}+8n+2)$ (2.11) $\displaystyle\left\lvert
s_{0}\theta(m,n)t_{m}\right\rvert$
$\displaystyle=8(m^{2}+4m+4mn+2n^{2}+6n+3)+4$ (2.12) $\displaystyle\left\lvert
s_{2}s_{0}\theta(m,n)t_{m}\right\rvert$
$\displaystyle=8(m^{2}+5m+4mn+2n^{2}+8n+5)$ (2.13) $\displaystyle\left\lvert
s_{1}s_{2}s_{0}\theta(m,n)t_{m}\right\rvert$
$\displaystyle=8(m^{2}+6m+4mn+2n^{2}+10n+6)+4$ (2.14)
$\displaystyle\left\lvert s_{0}\theta(m,n)t_{m}s_{2}\right\rvert$
$\displaystyle=8(m^{2}+5m+4mn+2n^{2}+8n+4)$ (2.15) $\displaystyle\left\lvert
s_{2}s_{0}\theta(m,n)t_{m}s_{2}\right\rvert$
$\displaystyle=8(m^{2}+6m+4mn+2n^{2}+9n+5)+6$ (2.16) $\displaystyle\left\lvert
s_{1}s_{2}s_{0}\theta(m,n)t_{m}s_{2}\right\rvert$
$\displaystyle=8(m^{2}+7m+4mn+2n^{2}+10n+7)+4$ (2.17)
$\displaystyle\left\lvert
s_{0}\theta(m,n)t_{m}s_{2}t_{m}^{\prime}\right\rvert$
$\displaystyle=8(m^{2}+6m+4mn+2n^{2}+8n+6)+4$ (2.18) $\displaystyle\left\lvert
s_{2}s_{0}\theta(m,n)t_{m}s_{2}t_{m}^{\prime}\right\rvert$
$\displaystyle=8(m^{2}+7m+4mn+2n^{2}+9n+8)+4$ (2.19) $\displaystyle\left\lvert
s_{1}s_{2}s_{0}\theta(m,n)t_{m}s_{2}t_{m}^{\prime}\right\rvert$
$\displaystyle=8(m^{2}+8m+4mn+2n^{2}+10n+10)+4.$ (2.20)

######  Remark 2.8.

The big region is made of eight sub-regions, namely, its connected components.
In this section we have described just four of them. The remaining four
regions are obtained by applying the automorphism $\varphi$, and therefore,
their description follows from the description of the regions already
considered. In particular, the size formulas in Corollary 2.5, Lemma 2.6 and
Lemma 2.7 are the same for an element and its $\varphi$-counterpart. In
formulas $\left\lvert x\right\rvert=\left\lvert x^{\prime}\right\rvert$.

###  2.2 Lower intervals for the thick region

In this section we describe some lower intervals for elements located in the
thick region. More precisely, we provide a geometric description of the sets
$\leq x_{n}$ and $\leq e_{n}$. We omit description of the lower intervals of
the remaining elements in the thick region as this is not needed in the
sequel.

We begin by considering the elements $x_{n}$. In this case we can see there is
a pattern that appears modulo three: $\leq x_{3k}$, $\leq x_{3k+1}$ and $\leq
x_{3k+2}$ all behave differently. Figure 4 shows some examples.

######  Lemma 2.9.

Let $k\geq 1$. Then $\leq x_{3k}=S(k-1,0)\setminus Z$, where $Z$ is the subset
of $\partial{(S(k-1,0))}$ formed by the triangles with a side on the line that
connects the north and west vertices of $S(k-1,0)$.

###### Proof.

The result follows by induction on $k$ and the identity $\leq x_{3k+3}=(\leq
x_{3k})(\leq t_{k}^{\prime}s_{2}t_{k}^{\prime})$. ∎

Having described the set $\leq x_{3k}$, it is now easy to obtain a geometric
description of set $\leq x_{3k+1}$. Indeed, $\leq x_{3k+1}=\leq
x_{3k}\sqcup(\partial_{t_{k}^{\prime}}(x_{3k}))t_{k}^{\prime}$. Similarly, we
have $\leq x_{3k+2}=\leq x_{3k+1}\sqcup(\partial_{s_{2}}(x_{3k+1}))s_{2}$.
Using these descriptions and a straightforward counting argument we obtain the
following result.

######  Lemma 2.10.

For all $k\geq 1$ we have

$\left\lvert x_{3k}\right\rvert=8k^{2}-2k,\qquad\left\lvert
x_{3k+1}\right\rvert=8k^{2}+4k,\qquad\text{and}\qquad\left\lvert
x_{3k+2}\right\rvert=8k^{2}+12k.$ (2.21)

1.0 1.0 [unit=1,gridcolor=cb-blue, subgridcolor=cb-blue,subgriddiv=1,
subgridwidth=0.8pt,subgriddots=15, gridlabels=0](5,6)(15,16)
[unit=1.414213562373,subgridcolor=cb-burgundy, gridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(5,5)
[unit=1.414213562373,subgridcolor=cb-burgundy, gridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(3,7)
[unit=1.414213562373,subgridcolor=cb-burgundy, gridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(1,9)
[unit=1.414213562373,subgridcolor=cb-burgundy, gridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(7,3)
[unit=1.414213562373,subgridcolor=cb-burgundy, gridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(9,1)
$\bullet$

(a) From lightest to darkest grey: Lower intervals of $x_{3k}$ for $k=1,2,3$
and $4$.

1.0 1.0 [unit=1,gridcolor=cb-blue, subgridcolor=cb-blue,subgriddiv=1,
subgridwidth=0.8pt,subgriddots=15, gridlabels=0](5,6)(15,16)
[unit=1.414213562373,subgridcolor=cb-burgundy, gridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(5,5)
[unit=1.414213562373,subgridcolor=cb-burgundy, gridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(3,7)
[unit=1.414213562373,subgridcolor=cb-burgundy, gridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(1,9)
[unit=1.414213562373,subgridcolor=cb-burgundy, gridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(7,3)
[unit=1.414213562373,subgridcolor=cb-burgundy, gridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(9,1)
$\bullet$

(b) From lightest to darkest grey: Lower intervals of $x_{3k+1}$ for $k=1,2,3$
and $4$.

1.0 1.0 [unit=1,gridcolor=cb-blue, subgridcolor=cb-blue,subgriddiv=1,
subgridwidth=0.8pt,subgriddots=15, gridlabels=0](5,6)(15,16)
[unit=1.414213562373,subgridcolor=cb-burgundy, gridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(5,5)
[unit=1.414213562373,subgridcolor=cb-burgundy, gridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(3,7)
[unit=1.414213562373,subgridcolor=cb-burgundy, gridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(1,9)
[unit=1.414213562373,subgridcolor=cb-burgundy, gridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(7,3)
[unit=1.414213562373,subgridcolor=cb-burgundy, gridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(9,1)
$\bullet$

(c) From lightest to darkest grey: Lower intervals of $x_{3k+2}$ for $k=1,2,3$
and $4$.

Figure 4: Lower intervals for elements $x_{n}$.

We now focus on the elements $e_{n}$. Just as the $x_{n}$, they obey a pattern
that appears modulo $3$. Figure 5 shows the different patterns of the lower
intervals for the elements $e_{n}$. In this case it is easier to first
consider the lower intervals of the elements $e_{3k+2}$.

######  Lemma 2.11.

Let $k\geq 0$. Then the set $\leq e_{3k+2}=S(k)$ where $S(k)$ is the smallest
square containing $e_{3k+2}$ and $x_{3k+2}$.

###### Proof.

The result follows by induction on $k$ and the identity $\leq e_{3k+5}=(\leq
e_{3k+2})(\leq t_{k}t_{k}^{\prime}s_{2})$. ∎

Using Lemma 2.11 as starting point, we can describe the sets $\leq e_{3k+3}$
and $\leq e_{3k+4}$. These are

$\leq e_{3k+3}=(\leq e_{3k+2})\sqcup(\partial_{t_{k}}(\leq
e_{3k+2}))t_{k}\qquad\mbox{and}\qquad\leq e_{3k+4}=(\leq
e_{3k+3})\sqcup(\partial_{t_{k}^{\prime}}(\leq e_{3k+3}))t_{k}^{\prime}.$
(2.22)

An easy counting argument using these descriptions shows the following.

######  Lemma 2.12.

For all $k\geq 0$, we have

$\left\lvert e_{3k}\right\rvert=8k^{2}+4k,\qquad\left\lvert
e_{3k+1}\right\rvert=8k^{2}+8k+4,\qquad\left\lvert
e_{3k+2}\right\rvert=8(k+1)^{2}.$

1.0 1.0 [unit=1,gridcolor=cb-blue, subgridcolor=cb-blue,subgriddiv=1,
subgridwidth=0.8pt,subgriddots=15, gridlabels=0](5,6)(15,16)
[unit=1.414213562373,subgridcolor=cb-burgundy, gridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(5,5)
[unit=1.414213562373,subgridcolor=cb-burgundy, gridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(3,7)
[unit=1.414213562373,subgridcolor=cb-burgundy, gridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(1,9)
[unit=1.414213562373,subgridcolor=cb-burgundy, gridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(7,3)
[unit=1.414213562373,subgridcolor=cb-burgundy, gridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(9,1)
$\bullet$

(a) From lightest to darkest grey: Lower intervals of $e_{3k+2}$ for $k=0,1,2$
and $3$.

1.0 1.0 [unit=1,gridcolor=cb-blue, subgridcolor=cb-blue,subgriddiv=1,
subgridwidth=0.8pt,subgriddots=15, gridlabels=0](5,6)(15,16)
[unit=1.414213562373,subgridcolor=cb-burgundy, gridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(5,5)
[unit=1.414213562373,subgridcolor=cb-burgundy, gridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(3,7)
[unit=1.414213562373,subgridcolor=cb-burgundy, gridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(1,9)
[unit=1.414213562373,subgridcolor=cb-burgundy, gridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(7,3)
[unit=1.414213562373,subgridcolor=cb-burgundy, gridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(9,1)
$\bullet$

(b) From lightest to darkest grey: Lower intervals of $e_{3k+3}$ for $k=0,1,2$
and $3$.

1.0 1.0 [unit=1,gridcolor=cb-blue, subgridcolor=cb-blue,subgriddiv=1,
subgridwidth=0.8pt,subgriddots=15, gridlabels=0](5,6)(15,16)
[unit=1.414213562373,subgridcolor=cb-burgundy, gridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(5,5)
[unit=1.414213562373,subgridcolor=cb-burgundy, gridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(3,7)
[unit=1.414213562373,subgridcolor=cb-burgundy, gridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(1,9)
[unit=1.414213562373,subgridcolor=cb-burgundy, gridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(7,3)
[unit=1.414213562373,subgridcolor=cb-burgundy, gridcolor=cb-green-
lime,subgriddiv=2, subgridwidth=0.8pt,subgriddots=0,gridlabels=0](0,0)(9,1)
$\bullet$

(c) From lightest to darkest grey: Lower intervals of $e_{3k+4}$ for $k=0,1,2$
and $3$.

Figure 5: Lower intervals for elements $e_{n}$.

###  2.3 Coatoms for lower intervals.

We write $y\lessdot w$ to mean that $y\leq w$ and $\ell(y)=\ell(w)-1$, and
$\lessdot w$ to denote the set of all such $y$. If
$\underline{w}=(s_{1},\dots,s_{n})$ is a reduced expression for $w$, then
declare $\underline{w}(\overline{i}):=s_{1}\cdots\hat{s}_{i}\cdots
s_{n}=s_{1}\cdots s_{i-1}s_{i+1}\cdots s_{n}$. Further, let
$\underline{x}_{n}$ be the preferred reduced expression $(a_{1},\cdots,a_{n})$
obtained from the sequence (1.6) and
$\underline{e}_{n}=(s_{1},a_{1},a_{2},\dots,a_{n})$. We also consider coatoms
for elements ${d}_{n}$ defined as the the product of the first $n$ symbols of
the infinite sequence
$\\{b_{i}\\}_{i=1}^{\infty}=(s_{2},s_{1},s_{2},s_{0},s_{2},s_{1},s_{2},s_{0},\dots)$.
These elements admit a unique reduced expression, and they comprise the
“northwest wall” of the thin region; we will return to them in Section 6.

######  Lemma 2.13.

For $k\geq 2$, the sets $\\{y\mid y\lessdot x_{n}\\}$ have the following
description.

$\displaystyle\lessdot x_{3k}$
$\displaystyle=\\{\underline{x}_{3k}(\overline{1}),\
\underline{x}_{3k}(\overline{3}),\ \underline{x}_{3k}(\overline{3k-2}),\
\underline{x}_{3k}(\overline{3k})\\}$ (2.23) $\displaystyle=\\{w_{3k-3},\
s_{1}\theta^{\prime}(k-2,0),\ \theta(k-2,0)t_{k-2},\ x_{3k-1}\\}$ (2.24)
$\displaystyle\lessdot x_{3k+1}$
$\displaystyle=\\{\underline{x}_{3k+1}(\overline{1}),\
\underline{x}_{3k+1}(\overline{3}),\ \underline{x}_{3k+1}(\overline{3k}),\
\underline{x}_{3k+1}(\overline{3k+1})\\}$ (2.25) $\displaystyle=\\{w_{3k-2},\
s_{1}\theta^{\prime}(k-2,0)t^{\prime}_{k-2},\ \overline{x}_{3k},\ x_{3k}\\}$
(2.26) $\displaystyle\lessdot x_{3k+2}$
$\displaystyle=\\{\underline{x}_{3k+2}(\overline{1}),\
\underline{x}_{3k+2}(\overline{3}),\ \underline{x}_{3k+2}(\overline{3k}),\
\underline{x}_{3k+2}(\overline{3k+1}),\
\underline{x}_{3k+2}(\overline{3k+2})\\}$ (2.27) $\displaystyle=\\{w_{3k-1},\
s_{1}\theta(k-2,0)t^{\prime}_{k-2}s_{2},\ s_{1}s_{2}s_{0}\theta(k-2,0),\
\theta(k-1,0),\ x_{3k+1}\\}$ (2.28)

Furthermore, for $k\geq 3$,

$\displaystyle\lessdot\overline{x}_{3k}=\\{w_{3k-3},\
s_{1}\theta^{\prime}(k-3,0)t^{\prime}_{k-3}s_{2}t_{k-3},\
s_{1}s_{2}s_{0}\theta(k-3,0)t_{k-3},\ x_{3k-1}\\}.$ (2.29)

###### Proof.

Recall that all elements $y\leq w$ can be obtained as subexpressions of a
fixed reduced expression for $w$, so all elements of $\lessdot{x}_{n}$ are
obtained by removing a single symbol from $\underline{x}_{n}$. We will argue
for $x_{3k}$, the other cases being similar. We examine which individual
symbols can be removed from $\underline{x}_{3k}$ to obtain a reduced
expression. It is clear that $\underline{x}_{3k}(\overline{1})$ and
$\underline{x}_{3k}(\overline{3k})$ are reduced, and that none of the
$s_{2}$’s in $\underline{x}_{3k}$ can be removed to obtain a reduced
expression. If we remove any $a_{i}=s_{1}$ where $4\leq i\leq 3k-3$, then
there is guaranteed to be a substring $s_{0}s_{2}s_{0}$ immediately to the
right or to the left of $a_{i}$. Assume it is to the right; upon removal we
obtain a substring of the form
$s_{0}s_{1}s_{2}s_{0}s_{2}s_{0}=s_{0}s_{1}s_{0}s_{2}s_{0}s_{2}=s_{1}s_{2}s_{0}s_{2}$
which is not reduced. An identical argument applies if the substring is to
left, or if $a_{i}=s_{0}$. Thus, the only other possibilities are
$\underline{x}_{3k}(\overline{3})$ and $\underline{x}_{3k}(\overline{3k-2})$,
and these are indeed reduced.

The latter description of each set $\lessdot x_{n}$ can be easily observed in
the geometric realization of $W$, and the set $\lessdot\overline{x}_{3k}$ is
obtained by similar arguments. ∎

We will also need the following in Section 5.2.

######  Lemma 2.14.

For $k\geq 2$, the sets $\lessdot e_{n}$ have the following description.

$\displaystyle\lessdot e_{3k}$ $\displaystyle=\\{x^{\prime}_{3k},\
\overline{x}_{3k},\ s_{1}\theta^{\prime}(k-2,0)t^{\prime}_{k-2},\ e_{3k-1}\\}$
(2.30) $\displaystyle\lessdot e_{3k+1}$ $\displaystyle=\\{x^{\prime}_{3k+1},\
{x}_{3k+1},\ e^{\prime}_{3k},\ e_{3k}\\}$ (2.31) $\displaystyle\lessdot
e_{3k+2}$ $\displaystyle=\\{x^{\prime}_{3k+2},\ {x}_{3k+2},\
s_{0}\theta(k-1,0),\ s_{1}\theta^{\prime}(k-1,0),\ e_{3k+1}\\}$ (2.32)

###### Proof.

Multiplying ${x}_{n}$ by $s_{1}$ on the left does not introduce new
possibilities for removal of the symbols from $\underline{x}_{n}$, though it
can rule them out. We see that removing $a_{3}$ from $\underline{e}_{n}$ gives
us a non-reduced substring $s_{1}s_{0}s_{2}s_{1}s_{2}s_{1}$, but now we can
also remove the first symbol $s_{1}$ from $\underline{e}_{n}$ and get $x_{n}$
back, so the size of the coatom set remains the same. The descriptions above
are evident from the geometric realization of $W$. ∎

######  Lemma 2.15.

For $n\geq 7$, the sets $\\{y\mid y\lessdot d_{n}\\}$ have the following
description.

$\lessdot
d_{n}=\begin{cases}\\{\underline{d}_{n}(\overline{1}),\underline{d}_{n}(\overline{3}),\underline{d}_{n}(\overline{n-3}),\underline{d}_{n}(\overline{n-1}),\underline{d}_{n}(\overline{n})\\}&\text{
if }n\text{ is even},\\\
\\{\underline{d}_{n}(\overline{1}),\underline{d}_{n}(\overline{3}),\underline{d}_{n}(\overline{n-2}),\underline{d}_{n}(\overline{n})\\}&\text{
if }n\text{ is odd},\end{cases}$

###### Proof.

No symbol $s_{1}$ or $s_{0}$ can be removed from $\underline{d}_{n}$ and leave
a reduced expression unless it is $b_{n}$. If $b_{i}=s_{2}$ for $5\leq i\leq
n-4$, then removal introduces a substring (possibly swapping $s_{1}$ with
$s_{0}$) of the form

$s_{2}s_{1}s_{2}s_{0}s_{1}s_{2}s_{0}s_{2}=s_{2}s_{1}s_{2}s_{1}s_{0}s_{2}s_{0}s_{2}=s_{1}s_{2}s_{1}s_{0}s_{2}s_{0}$

so $\underline{d}_{n}(\overline{i})$ is not reduced. The remaining options
figure in the lists above. ∎

It is clear from Figure 1 that each element in $\mathfrak{C}$ admits a reduced
decomposition of the form $x_{6k}d_{n}$ or $x_{6k+3}d^{\prime}_{n}$.

######  Lemma 2.16.

For any $w\in\mathfrak{C}$, the set $\lessdot w$ consists of at most five
elements. In particular for $m,n>0$ we have

$\displaystyle\lessdot\theta(m,n)$
$\displaystyle=\\{s_{2}s_{1}\theta^{\prime}(m-1,n),\,\theta(m-1,n)t_{m-1}s_{2},\,s_{1}s_{2}s_{0}\theta(m,n-1),\,\theta(m,n-1)t_{m}s_{2}t_{m}^{\prime}\\}$
(2.33) $\displaystyle\lessdot\theta(m,n)t_{m}$
$\displaystyle=\\{s_{2}s_{1}\theta^{\prime}(m-1,n)t^{\prime}_{m-1},\,\theta(m-1,n)t_{m-1}s_{2}t^{\prime}_{m-1},$
(2.34) $\displaystyle\qquad\qquad\qquad\qquad\qquad
s_{1}s_{2}s_{0}\theta(m,n-1)t_{m},\,\theta(m+1,n-1)t_{m+1},\,\theta(m,n)\\}$
(2.35) $\displaystyle\lessdot\theta(m,n)t_{m}s_{2}$
$\displaystyle=\\{s_{2}s_{1}\theta^{\prime}(m-1,n)t^{\prime}_{m-1}s_{2},\,\theta(m-1,n+1),$
(2.36) $\displaystyle\qquad\qquad\qquad\qquad\qquad
s_{1}s_{2}s_{0}\theta(m,n-1)t_{m}s_{2},\,\theta(m+1,n-1)t_{m+1}s_{2},\,\theta(m,n)t_{m}\\}$
(2.37) $\displaystyle\lessdot\theta(m,n)t_{m}s_{2}t^{\prime}_{m}$
$\displaystyle=\\{s_{2}s_{1}\theta^{\prime}(m-1,n)t^{\prime}_{m-1}s_{2}t_{m-1},\,\theta(m-1,n+1)t_{m-1},$
(2.38) $\displaystyle\qquad\qquad\qquad\qquad\qquad
s_{1}s_{2}s_{0}\theta(m,n-1)t_{m}s_{2}t^{\prime}_{m},\,\theta(m+2,n-1),\,\theta(m,n)t_{m}s_{2}\\}$
(2.39)

###### Proof.

We assume $w=x_{m}d_{n}$ for $m=6k$; the other case is identical. From Lemma
2.13, $x_{m}$ has four removable symbols, but when $d_{n}$ is appended, the
last $a_{n}$ can no longer be removed to obtain a reduced expression. If
$a_{3}=s_{1}$ is removed, then braid relations can be applied to give an
expression for $\underline{x}_{m}(\overline{3})$ ending in $s_{2}$ which
disqualifies this possibility as well. Thus there are only two possibilities
for removal from $x_{m}$: $a_{1}$ and $a_{m-2}$.

By Lemma 2.15, the symbols of $d_{n}$ give four or five more possibilities
depending on the parity of $n$. However, removal of $b_{3}$, leads to a
substring of the form $s_{0}s_{2}s_{0}s_{2}s_{1}s_{0}=s_{2}s_{0}s_{2}s_{1}$.
Further, if $n=4k$ (respectively, $n=4k+2$), removal of $b_{n-1}$
(respectively, $b_{n-3}$) plus the application of braid relations leads to an
expression for $\underline{d}_{n}(\overline{n-1})$ (respectively,
$\underline{d}_{n}(\overline{n-3})$) that begins with $s_{2}s_{0}$. As $x_{m}$
ends with $s_{0}s_{2}s_{0}$, the result is not a reduced expression. Thus,
$d_{m}$ adds three more possibilities for a maximum total of five elements.

The elements $\theta(m,n)$ in particular can be written as
$\theta(m,n)=x_{3(m+1)}d_{4n+1}$ for $m$ odd and
$\theta(m,n)=x_{3(m+1)}d^{\prime}_{4n+1}$ for $m$ even. An argument similar to
the one of the previous paragraph shows that the removal of $b_{4n-1}$ (or
$b^{\prime}_{4n-1}$, as the case may be) from this reduced expression yields
something not reduced, so $\lessdot\theta(m,n)$ consists of four elements when
$m,n>0$. These are (when $m$ is odd)

$\lessdot\theta(m,n)=\\{x_{3(m+1)}(\overline{1})d_{4n+1},\
x_{3(m+1)}(\overline{3m+1})d_{4n+1},\ x_{3(m+1)}d_{4m+1}(\overline{1}),\
x_{3(m+1)}d_{4n+1}(\overline{4n+1})\\}.$ (2.40)

The description of this set given in the statement of the lemma can be
observed in the geometric realization of $W$. The other cases can be reasoned
similarly, with all five possibilities yielding reduced expressions. ∎

######  Remark 2.17.

If $m=0$, the first two elements of (2.40) are the same, and if $n=0$ the last
two are the same, so the set has three elements in case one of $m$ or $n$ is
0. A similar situation occurs for the elements of $\lessdot\theta(m,n)y$
($y\in\\{t_{m},t_{m}s_{2},t_{m}s_{2}t_{m}^{\prime}\\})$ in these cases as
well. We leave the precise description to the reader.

The following descriptions will be necessary for the arguments of Section 4.
They can be deduced by analysis similar to that of Lemma 2.16.

######  Lemma 2.18.

For all $m,n\geq 0$ and $y\in\\{t_{m},t_{m}s_{2},t_{m}s_{2}t_{m}^{\prime}\\}$,

$\displaystyle\lessdot s_{0}\theta(m,n)y$
$\displaystyle=\\{s_{0}\\}(\lessdot\theta(m,n)y)\cup\\{\theta(m,n)y\\}$ (2.41)
$\displaystyle\lessdot s_{2}s_{0}\theta(m,n)y$
$\displaystyle=\\{s_{2}s_{0}\\}(\lessdot\theta(m,n)y)\cup\\{s_{0}\theta(m,n)y\\}$
(2.42) $\displaystyle\lessdot s_{1}s_{2}s_{0}\theta(m,n)y$
$\displaystyle=\\{s_{1}s_{2}s_{0}\\}(\lessdot\theta(m,n)y)\cup\\{s_{2}s_{0}\theta(m,n)y\\}$
(2.43)

######  Remark 2.19.

Observe that while the description of the set $\lessdot\theta(m,n)y$ is
affected when $m$ or $n$ is zero, the relationship between this set and
$\lessdot x\theta(m,n)y$ is the same in all cases for
$x\in\\{s_{0},s_{2}s_{0},s_{1}s_{2}s_{0}\\}$.

##  3 Multiplicative formulas in the Hecke algebra

In this section we introduce the Hecke algebra of the affine Weyl group of
type $\widetilde{B}_{2}$. We also collect several multiplicative identities
that will be key in order to obtain formulas for Kazhdan-Lusztig basis
elements in the forthcoming sections.

###  3.1 The Hecke algebra of type $\widetilde{B}_{2}$

Let $\mathcal{H}$ be the Hecke algebra of $W$. It is the
${\cal{A}}:=\mathbb{Z}[v,v^{-1}]$-algebra with generators
$\mathbf{H}_{s_{0}}$, $\mathbf{H}_{s_{1}}$ and $\mathbf{H}_{s_{2}}$ and
relations $\mathbf{H}_{s_{i}}^{2}=(v^{-1}-v)\mathbf{H}_{s_{i}}+1$,

$\mathbf{H}_{s_{0}}\mathbf{H}_{s_{1}}=\mathbf{H}_{s_{1}}\mathbf{H}_{s_{0}},\qquad\mathbf{H}_{s_{0}}\mathbf{H}_{s_{2}}\mathbf{H}_{s_{0}}\mathbf{H}_{s_{2}}=\mathbf{H}_{s_{2}}\mathbf{H}_{s_{0}}\mathbf{H}_{s_{2}}\mathbf{H}_{s_{0}}\,\mbox{
and
}\,\mathbf{H}_{s_{1}}\mathbf{H}_{s_{2}}\mathbf{H}_{s_{1}}\mathbf{H}_{s_{2}}=\mathbf{H}_{s_{2}}\mathbf{H}_{s_{1}}\mathbf{H}_{s_{2}}\mathbf{H}_{s_{1}}.$
(3.1)

Given a reduced expression $s_{i_{1}}s_{i_{2}}\ldots s_{i_{k}}$ of an element
$w\in W$ we define
$\mathbf{H}_{w}:=\mathbf{H}_{s_{i_{1}}}\mathbf{H}_{s_{i_{2}}}\ldots\mathbf{H}_{s_{i_{k}}}$.
It is well-known that $\mathbf{H}_{w}$ does not depend on the choice of a
reduced expression. The set $\\{\mathbf{H}_{w}\\}_{w\in W}$ forms an
$\cal{A}$-basis of $\mathcal{H}$, which is called the standard basis. It is
easy to see that each generator of $\mathcal{H}$ is invertible and therefore
all the elements of the standard basis are invertible. There is a
$\mathbb{Z}$-linear involution $d:\mathcal{H}\rightarrow\mathcal{H}$ which is
determined by $d(v)=v^{-1}$ and $d(\mathbf{H}_{w})=\mathbf{H}_{w^{-1}}^{-1}$.
An element invariant under $d$ is called _self-dual_.
There is another basis $\\{{\underline{\mathbf{H}}}_{w}\\}_{w\in W}$ called
the Kazhdan-Lusztig basis whose elements are uniquely determined by two
conditions: They are self-dual and

${\underline{\mathbf{H}}}_{w}=\mathbf{H}_{w}+\sum_{x<w}h_{x,w}(v)\mathbf{H}_{x},$
(3.2)

for some polynomials $h_{x,w}(v)\in v\mathbb{Z}[v]$. These polynomials are the
Kazhdan-Lusztig polynomials.

There is a recursive algorithm to compute this basis. Indeed, if $\mu(x,w)$
denotes the coefficient of $v$ in $h_{x,w}(v)$ then

${\underline{\mathbf{H}}}_{w}{\underline{\mathbf{H}}}_{s}={\underline{\mathbf{H}}}_{ws}+\sum_{xs<x<w}\mu(x,w){\underline{\mathbf{H}}}_{x},$
(3.3)

for all pairs $(w,s)\in W\times S$ such that $w<ws$. Also, we have

${\underline{\mathbf{H}}}_{w}{\underline{\mathbf{H}}}_{s}=(v+v^{-1}){\underline{\mathbf{H}}}_{w}$
(3.4)

for all pairs $(w,s)\in W\times S$ such that $w>ws$.

We recall the elements defined in the introduction for any $w\in W$,

$\mathbf{N}_{w}=\sum_{x\leq w}v^{l(w)-l(x)}\mathbf{H}_{x}.$ (3.5)

######  Definition 3.1.

Given $w\in W$ and $X\in\mathcal{H}$ we denote by $G_{w}(X)$ the coefficient
of $\mathbf{H}_{w}$ in $X$ when it is written in terms of the standard basis.
That is,

$X=\sum_{w\in W}G_{w}(X)\mathbf{H}_{w}.$ (3.6)

We also define the _content_ of $X$ by

$c(X):=\sum_{w\in W}G_{w}(X)(1)\in\mathbb{Z}.$ (3.7)

Note that this implies that $c(\mathbf{N}_{w})=\left\lvert w\right\rvert$ and
also that $c(X{\underline{\mathbf{H}}}_{s})=2c(X)$ for any $X\in\mathcal{H}$
and any $s\in S$, since

$\mathbf{H}_{w}{\underline{\mathbf{H}}}_{s}=\begin{cases}\mathbf{H}_{ws}+v\mathbf{H}_{w},&\text{if
}w<ws;\\\ \mathbf{H}_{ws}+v^{-1}\mathbf{H}_{w},&\text{if }w>ws.\end{cases}$
(3.8)

######  Definition 3.2.

Let $w\in W$. An element $H\in\mathcal{H}$ is called _triangular of height_
$w$ if $G_{w}(H)=1$ and $G_{x}(H)=0$ for $x\not\leq w$. Furthermore, a
triangular element $H$ of height $w$ is called _monotonic_ if
$G_{x}(H)\in\mathbb{N}[v,v^{-1}]$ for all $x\in W$ and

$G_{y}(H)-v^{l(x)-l(y)}G_{x}(H)\in\mathbb{N}[v,v^{-1}],$ (3.9)

for all $y\leq x\leq w$.

A trivial example of a monotonic element is any $\mathbf{N}_{w}$. We also know
that ${\underline{\mathbf{H}}}_{w}$ is always monotonic (see [BM01, Pla17]).

######  Lemma 3.3.

Let $H\in\mathcal{H}$ be a monotonic element of height $w$. Suppose that
$ws>w$. Then, $H{\underline{\mathbf{H}}}_{s}$ is monotonic of height $ws$.

###### Proof.

It is clear that $H{\underline{\mathbf{H}}}_{s}$ is triangular of height $ws$.
On the other hand, (3.8) shows that

$G_{x}(H{\underline{\mathbf{H}}}_{s})=\left\\{\begin{array}[]{rl}vG_{x}(H)+G_{xs}(H),&\mbox{if
}xs>x;\\\ v^{-1}G_{x}(H)+G_{xs}(H),&\mbox{if }xs<x.\end{array}\right.$ (3.10)

Using this, a simple case analysis shows that the monotonicity of $H$ implies
the monotonicity of $H{\underline{\mathbf{H}}}_{s}$. ∎

######  Lemma 3.4.

Let $(W,S)$ be an arbitrary Coxeter system. Let $w\in W$ and $s\in S$ such
that $s\in D_{R}(w)$. Then,
$\mathbf{N}_{w}{\underline{\mathbf{H}}}_{s}=(v+v^{-1})\mathbf{N}_{w}$.

###### Proof.

Since $ws<w$ we can use the Lifting Property [BB06, Proposition 2.2.7] to
conclude that multiplication on the right by $s$ induces a permutation of the
lower interval $[e,w]$. Therefore the result follows by (3.10). ∎

######  Definition 3.5.

Let $p$ and $q$ in $\mathcal{A}$. We write $p\geq q$ if
$p-q\in\mathbb{N}[v,v^{-1}]$. Then for $X,Y\in\mathcal{H}$, we write
$X\overset{\mathbf{H}}{\geq}Y$ if $G_{w}(X)\geq G_{w}(Y)$ for all $w\in W$.

Notice that $X\overset{\mathbf{H}}{\geq}Y$ and $c(X)=c(Y)$ implies $X=Y$. We
claim no originality in this observation and refer to [LP20] for its first
application in the context of computation of Kazhdan-Lusztig polynomials. In
general, it is not an easy task to prove an inequality of the form
$X\overset{\mathbf{H}}{\geq}Y$. However, there are certain situations where we
can make some simplifications. For instance, let us suppose that

$Y=\sum_{w\in Z}p_{w}(v)\mathbf{N}_{w}$ (3.11)

where $Z$ is a finite subset of $W$ and
$p_{z}(v)=\sum_{i\in\mathbb{Z}}p_{z}^{i}v^{i}\in\mathbb{N}[v,v^{-1}]$. For
each $i\in\mathbb{Z}$ we define

$Y_{i}=\sum_{w\in Z}p_{w}^{i-\ell(w)}\mathbf{N}_{w}.$ (3.12)

Since the elements $Y_{i}$ lie in different degrees (in the sense that
$G_{u}(Y_{i})$ and $G_{u}(Y_{j})$ are monomials of different degree if $i\neq
j$) in order to prove $X\overset{\mathbf{H}}{\geq}Y$ it is enough to show
$X\overset{\mathbf{H}}{\geq}Y_{i}$ for all $i\in\mathbb{Z}$. We stress that
$Y_{i}=0$ for all but finitely many integers. Henceforth, we refer to this
simplification as “degree reasons.”

In order to prove inequalities of the form $X\overset{\mathbf{H}}{\geq}Y_{i}$
we can make some extra reductions if $X$ is monotonic. For example, if $X$ is
monotonic and $Y_{i}$ is made of just one $\mathbf{N}$-element, i.e.
$Y_{i}=cv^{k}\mathbf{N}_{w}$, then in order to prove
$X\overset{\mathbf{H}}{\geq}Y_{i}$ it is enough to check $G_{w}(X)\geq
cv^{k}$. In contrast, if $Y_{i}$ is made of two or more $\mathbf{N}$-elements
then additional analysis of the relationship between the elements involved in
$Y_{i}$ in the Bruhat order is required.

We conclude this section with a useful result that allows us to rule out the
occurrence of terms in the sum in (3.3). A proof can be found in [KL79,
(2.3.f)] or [BB06, Proposition 5.1.9].

######  Lemma 3.6.

Let $x,w\in W$ such that $\mu(x,w)\neq 0$. Suppose that $l(w)-l(x)>1$. Then

$D_{R}(w)\subseteq D_{R}(x)\qquad\mbox{ and }\qquad D_{L}(w)\subseteq
D_{L}(x).$

In particular, if $s\not\in D_{R}(w)$ and ${\underline{\mathbf{H}}}_{x}$
appears in the expansion of
${\underline{\mathbf{H}}}_{w}{\underline{\mathbf{H}}}_{s}$ when written in
terms of the Kazhdan-Lusztig basis, then $D_{R}(w)\cup\\{s\\}\subseteq
D_{R}(x)$. Similarly, if $s\not\in D_{L}(w)$ and
${\underline{\mathbf{H}}}_{x}$ appears in the expansion of
${\underline{\mathbf{H}}}_{s}{\underline{\mathbf{H}}}_{w}$ when written in
terms of the Kazhdan-Lusztig basis, then $D_{L}(w)\cup\\{s\\}\subseteq
D_{L}(x)$.

###  3.2 Multiplication formulas for $\mathbf{N}_{w}$

In this section we collect several multiplicative formulas involving elements
$\mathbf{N}_{w}$.

######  Lemma 3.7.

Let $m$ and $n$ be positive integers. Then,

$\mathbf{N}_{\theta(m,n)}{\underline{\mathbf{H}}}_{t_{m}}=\mathbf{N}_{\theta(m,n)t_{m}}+v\mathbf{N}_{\theta(m-1,n)t_{m}^{\prime}}.$
(3.13)

###### Proof.

First, let us prove that the contents on both sides of (3.13) coincide. On the
left side, Corollary 2.5 shows that

$c(\mathbf{N}_{\theta(m,n)}{\underline{\mathbf{H}}}_{t_{m}})=2c(\mathbf{N}_{\theta(m,n)})=\left\lvert\theta(m,n)\right\rvert=16(m^{2}+2m+4mn+2n^{2}+2n+1).$

On the right side, Lemma 2.6 implies that

$c(\mathbf{N}_{\theta(m,n)t_{m}}+v\mathbf{N}_{\theta(m-1,n)t_{m}^{\prime}})=\left\lvert\theta(m,n)t_{m}\right\rvert+\left\lvert\theta(m-1,n)t_{m}^{\prime}\right\rvert=16(m^{2}+2m+4mn+2n^{2}+2n+1).$
(3.14)

Thus we only need to show that

$\mathbf{N}_{\theta(m,n)}{\underline{\mathbf{H}}}_{t_{m}}\overset{\mathbf{H}}{\geq}\mathbf{N}_{\theta(m,n)t_{m}}+v\mathbf{N}_{\theta(m-1,n)t_{m}^{\prime}}.$
(3.15)

By degree reasons it is enough to check

$\displaystyle\mathbf{N}_{\theta(m,n)}{\underline{\mathbf{H}}}_{t_{m}}$
$\displaystyle\overset{\mathbf{H}}{\geq}\mathbf{N}_{\theta(m,n)t_{m}},$ (3.16)
$\displaystyle\mathbf{N}_{\theta(m,n)}{\underline{\mathbf{H}}}_{t_{m}}$
$\displaystyle\overset{\mathbf{H}}{\geq}v\mathbf{N}_{\theta(m-1,n)t_{m}^{\prime}}.$
(3.17)

Furthermore, by the monotonicity of
$\mathbf{N}_{\theta(m,n)}{\underline{\mathbf{H}}}_{t_{m}}$ ensured by Lemma
3.3, inequalities (3.16) and (3.17) will follow from the inequalities

$\displaystyle
G_{\theta(m,n)t_{m}}(\mathbf{N}_{\theta(m,n)}{\underline{\mathbf{H}}}_{t_{m}})$
$\displaystyle\geq 1,$ (3.18) $\displaystyle
G_{\theta(m-1,n)t_{m}^{\prime}}(\mathbf{N}_{\theta(m,n)}{\underline{\mathbf{H}}}_{t_{m}})$
$\displaystyle\geq v,$ (3.19)

respectively. Inequality (3.18) is clear. On the other hand, a direct
computation shows that

$G_{\theta(m-1,n)t_{m}^{\prime}}(v^{2}\mathbf{H}_{\theta(m-1,n)t_{m}^{\prime}}{\underline{\mathbf{H}}}_{t_{m}})=v,$
(3.20)

which proves (3.19). The lemma is proved. ∎

######  Remark 3.8.

Henceforth, we adopt the convention that $\mathbf{N}_{x\theta(m,n)y}$ and
${\underline{\mathbf{H}}}_{x\theta(m,n)y}$ are equal to zero whenever $m$ or
$n$ is negative, for any $x,y\in W$. This will allow us to express some
results more compactly and consistently.

Using the same arguments as in the proof of Lemma 3.7 we obtain the following
four lemmas.

######  Lemma 3.9.

Let $m$ and $n$ be positive integers. We have

$\displaystyle\mathbf{N}_{\theta(0,n)}{\underline{\mathbf{H}}}_{s_{0}}$
$\displaystyle=\mathbf{N}_{\theta(0,n)s_{0}}+v^{2}\mathbf{N}_{\theta(0,n-1)s_{0}};$
(3.21) $\displaystyle\mathbf{N}_{\theta(m,0)}{\underline{\mathbf{H}}}_{t_{m}}$
$\displaystyle=\mathbf{N}_{\theta(m,0)t_{m}}+v\mathbf{N}_{\theta(m-1,0)t_{m}^{\prime}}.$
(3.22)

Furthermore,
$\mathbf{N}_{\theta(0,0)}{\underline{\mathbf{H}}}_{s_{0}}=\mathbf{N}_{\theta(0,0)s_{0}}$.

######  Lemma 3.10.

For all $m\in\mathbb{N}$ we have

${\underline{\mathbf{H}}}_{s_{0}}\mathbf{N}_{\theta(m,0)}=\mathbf{N}_{s_{0}\theta(m,0)}+v\mathbf{N}_{s_{1}\theta^{\prime}(m-1,0)},$
(3.23)

where $\theta^{\prime}(m-1,0)$ denotes the image of $\theta(m-1,0)$ under the
automorphism $\varphi$.

######  Lemma 3.11.

Let $m$ be a positive integer. We have

$\mathbf{N}_{s_{0}\theta(m,0)}{\underline{\mathbf{H}}}_{t_{m}}=\mathbf{N}_{s_{0}\theta(m,0)t_{m}}+v\mathbf{N}_{s_{0}\theta(m-1,0)t_{m}^{\prime}}.$
(3.24)

Furthermore,
$\mathbf{N}_{s_{0}\theta(0,0)}{\underline{\mathbf{H}}}_{s_{0}}=\mathbf{N}_{s_{0}\theta(0,0)s_{0}}+v^{2}\mathbf{N}_{s_{1}s_{0}}$.

######  Lemma 3.12.

Let $m$ be a positive integer. We have

$\mathbf{N}_{s_{1}s_{2}s_{0}\theta(m,0)}{\underline{\mathbf{H}}}_{t_{m}}=\mathbf{N}_{s_{1}s_{2}s_{0}\theta(m,0)t_{m}}+v\mathbf{N}_{s_{1}s_{2}s_{0}\theta(m-1,0)t_{m}^{\prime}}.$
(3.25)

The following lemma is proved using essentially the same argument as the one
used in the proof of Lemma 3.7. This, however, is the first time so far in
which we have a case where we must show $X\overset{\mathbf{H}}{\geq}Y$ with
$Y$ consisting of two or more $\mathbf{N}$-terms, which leads some extra
subtleties in the analysis.

######  Lemma 3.13.

Let $m$ and $n$ be positive integers. Then,

$\mathbf{N}_{\theta(m,n)}{\underline{\mathbf{H}}}_{t_{m}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{t_{m}}=2\mathbf{N}_{\theta(m,n)}{\underline{\mathbf{H}}}_{t_{m}}+\mathbf{N}_{\theta(m+1,n)}+\mathbf{N}_{\theta(m-1,n+1)}+\mathbf{N}_{\theta(m+1,n-1)}+\mathbf{N}_{\theta(m-1,n)}.$

(3.26)

###### Proof.

Let us denote by $L$ and $R$ the left-hand and right-hand side of (3.26),
respectively. A repeated application of Corollary 2.5 shows that

$c(L)=c(R)=64(m^{2}+2m+4mn+2n^{2}+2n+1).$ (3.27)

Therefore, to finish the proof we only need to show that
$L\overset{\mathbf{H}}{\geq}R$. Lemma 3.7 implies

$R=2\mathbf{N}_{\theta(m,n)t_{m}}+2v\mathbf{N}_{\theta(m-1,n)t_{m}^{\prime}}+\mathbf{N}_{\theta(m+1,n)}+\mathbf{N}_{\theta(m-1,n+1)}+\mathbf{N}_{\theta(m+1,n-1)}+\mathbf{N}_{\theta(m-1,n)}.$
(3.28)

Hence, by degree reasons, it is enough to check

$\displaystyle L$
$\displaystyle\overset{\mathbf{H}}{\geq}\mathbf{N}_{\theta(m+1,n)}$ (3.29)
$\displaystyle L$
$\displaystyle\overset{\mathbf{H}}{\geq}\mathbf{N}_{\theta(m-1,n)}$ (3.30)
$\displaystyle L$
$\displaystyle\overset{\mathbf{H}}{\geq}\mathbf{N}_{\theta(m-1,n+1)}+2\mathbf{N}_{\theta(m,n)t_{m}}$
(3.31) $\displaystyle L$
$\displaystyle\overset{\mathbf{H}}{\geq}\mathbf{N}_{\theta(m+1,n-1)}+2v\mathbf{N}_{\theta(m-1,n)t_{m}^{\prime}}$
(3.32)

We now notice that $L$ is monotonic of height $\theta(m+1,n)$ by Lemma 3.3. It
is clear that $G_{\theta(m+1,n)}(L)=1$. Then the monotonicity of $L$ shows
(3.29). On the other hand, a direct computation reveals that
$G_{\theta(m-1,n)}(v^{3}\mathbf{H}_{\theta(m-1,n)}{\underline{\mathbf{H}}}_{t_{m}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{t_{m}})=v^{2}+1$.
Therefore,

$G_{\theta(m-1,n)}(L)\geq
G_{\theta(m-1,n)}(v^{3}\mathbf{H}_{\theta(m-1,n)}{\underline{\mathbf{H}}}_{t_{m}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{t_{m}})=v^{2}+1\geq
1.$ (3.33)

The above inequality together with the monotonicity of $L$ proves (3.30).

We now prove (3.31). Since we have two $\mathbf{N}$-terms that cannot be
separated by degree reasons on the right-hand side, we need to proceed in a
different way. Let us explain this more generally. Suppose we want to prove

$L\overset{\mathbf{H}}{\geq}c_{1}v^{i}\mathbf{N}_{x}+c_{2}v^{j}\mathbf{N}_{y},$
(3.34)

for some positive integers $c_{1}$ and $c_{2}$, and where $j-i=l(x)-l(y)$
(otherwise, degree reasons allow us to split the inequality in (3.34) in two
inequalities with only one $\mathbf{N}$-term on the right-hand side). Further
suppose that $\leq x\ \cap\leq y=\leq z\ \cup\leq w$ for some elements $z$ and
$w$. Then, by the monotonicity of $L$, (3.34) will follow from

$\begin{array}[]{rl}L&\overset{\mathbf{H}}{\geq}c_{1}v^{i}\mathbf{N}_{x},\\\
L&\overset{\mathbf{H}}{\geq}c_{2}v^{j}\mathbf{N}_{y},\\\
L&\overset{\mathbf{H}}{\geq}(c_{1}+c_{2})v^{i+l(x)-l(z)}\mathbf{N}_{z},\text{
and}\\\
L&\overset{\mathbf{H}}{\geq}(c_{1}+c_{2})v^{i+l(x)-l(w)}\mathbf{N}_{w}.\end{array}$
(3.35)

Let us apply this general principle to prove (3.31). By the diagrammatic
description of lower intervals given in §2.1 we have

$(\leq\theta(m-1,n+1))\cap(\leq\theta(m,n)t_{m})=(\leq\theta(m-1,n)t_{m}^{\prime}s_{2}t_{m}).$
(3.36)

Therefore, we only need to prove

$G_{\theta(m-1,n+1)}(L)\geq 1,\qquad G_{\theta(m,n)t_{m}}(L)\geq
2\qquad\mbox{and}\qquad G_{\theta(m-1,n)t_{m}^{\prime}s_{2}t_{m}}(L)\geq 3v.$
(3.37)

These inequalities follow from the following identities which are obtained by
a repeated application of (3.8).

$\begin{split}G_{\theta(m-1,n+1)}(v\mathbf{H}_{\theta(m-1,n)t_{m}^{\prime}s_{2}}{\underline{\mathbf{H}}}_{t_{m}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{t_{m}})&=1\\\
G_{\theta(m,n)t_{m}}(\mathbf{H}_{\theta(m,n)}{\underline{\mathbf{H}}}_{t_{m}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{t_{m}})&=2\\\
G_{\theta(m-1,n)t_{m}^{\prime}s_{2}t_{m}}(v^{2}\mathbf{H}_{\theta(m-1,n)t_{m}^{\prime}}{\underline{\mathbf{H}}}_{t_{m}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{t_{m}})&=v\\\
G_{\theta(m-1,n)t_{m}^{\prime}s_{2}t_{m}}(v\mathbf{H}_{\theta(m-1,n)t_{m}^{\prime}s_{2}}{\underline{\mathbf{H}}}_{t_{m}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{t_{m}})&=2v.\\\
\end{split}$ (3.38)

The proof of (3.32) is similar, noting that

$(\leq\theta(m+1,n-1))\cap(\leq\theta(m-1,n)t_{m}^{\prime})=(\leq\theta(m-1,n))\cup(\leq\theta(m,n-1)t_{m}).$
(3.39)

This description of the lower intervals allows one to apply the discussion
leading up to (3.35); we leave the details to the reader.∎

######  Proposition 3.14.

Let $m$ and $n$ be positive integers. Then,

$\mathbf{N}_{\theta(m,n)}({\underline{\mathbf{H}}}_{t_{m}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{t_{m}}-2{\underline{\mathbf{H}}}_{t_{m}})=\mathbf{N}_{\theta(m+1,n)}+\mathbf{N}_{\theta(m-1,n+1)}+\mathbf{N}_{\theta(m+1,n-1)}+\mathbf{N}_{\theta(m-1,n)}.$
(3.40)

###### Proof.

The result is an immediate consequence of Lemma 3.13. ∎

Similarly, we have the following proposition.

######  Proposition 3.15.

Let $m,n\in\mathbb{N}$. We have

$\displaystyle\mathbf{N}_{\theta(m,0)}({\underline{\mathbf{H}}}_{t_{m}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{t_{m}}-2{\underline{\mathbf{H}}}_{t_{m}})$
$\displaystyle=\mathbf{N}_{\theta(m+1,0)}+\mathbf{N}_{\theta(m-1,1)}+(1+v^{2})\mathbf{N}_{\theta(m-1,0)},$
(3.41)
$\displaystyle\mathbf{N}_{\theta(0,n)}({\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{0}}-2{\underline{\mathbf{H}}}_{s_{0}})$
$\displaystyle=\mathbf{N}_{\theta(1,n)}+(1+v^{2})\mathbf{N}_{\theta(1,n-1)}+v^{2}\mathbf{N}_{\theta(1,n-2)}.$
(3.42)

Propositions 3.14 and 3.15 should be understood as a way to pass from
$\mathbf{N}_{\theta(m,n)}$ to $\mathbf{N}_{\theta(m+1,n)}$. We now focus on
obtaining a similar statement but this time we want to pass from
$\mathbf{N}_{\theta(0,n)}$ to $\mathbf{N}_{\theta(0,n+1)}$.

######  Lemma 3.16.

Let $n$ be a positive integer. We have

$\mathbf{N}_{\theta(0,n)s_{0}}{\underline{\mathbf{H}}}_{s_{2}}+v^{2}\mathbf{N}_{\theta(0,n-1)s_{0}s_{2}}=\mathbf{N}_{\theta(0,n)s_{0}s_{2}}+\mathbf{N}_{\theta(0,n)}+v\mathbf{N}_{\theta(1,n-1)}.$
(3.43)

###### Proof.

Once we notice that the element on the left-hand side of (3.43) is monotonic
(of height $\theta(0,n)s_{0}s_{2}$) we can argue as in the proof of Lemma 3.7.
∎

######  Lemma 3.17.

Let $n$ be an integer greater than $2$. We have

$\begin{array}[]{rc}&\mathbf{N}_{\theta(0,n+1)}\\\ &\\\
&2\mathbf{N}_{\theta(0,n)s_{0}s_{2}}+v^{2}\mathbf{N}_{\theta(0,n)}+\mathbf{N}_{\theta(2,n-1)}+\\\
&\\\
\mathbf{N}_{\theta(0,n)}{\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}}+2v^{4}\mathbf{N}_{\theta(0,n-2)s_{0}s_{2}}=&3\mathbf{N}_{\theta(0,n)}+2v\mathbf{N}_{\theta(1,n-1)}+v^{2}\mathbf{N}_{\theta(2,n-2)}+\\\
&\\\
&v^{-2}\mathbf{N}_{\theta(0,n)}+3v^{2}\mathbf{N}_{\theta(0,n-1)}+2v^{3}\mathbf{N}_{\theta(1,n-2)}+\\\
&\\\ &\mathbf{N}_{\theta(0,n-1)}.\end{array}$ (3.44)

###### Proof.

Let $L$ and $R$ be the left and right sides of (3.44), respectively. Corollary
2.5 and Lemma 2.6 imply

$c(L)=c(R)=8(36n^{2}+26n+18).$ (3.45)

Therefore, in order to prove $L=R$ we only need to show that
$L\overset{\mathbf{H}}{\geq}R$. By degree reasons, it is enough to prove the
following inequalities

$\displaystyle L\overset{\mathbf{H}}{\geq}$
$\displaystyle\mathbf{N}_{\theta(0,n+1)},$ (3.46) $\displaystyle
L\overset{\mathbf{H}}{\geq}$ $\displaystyle
2\mathbf{N}_{\theta(0,n)s_{0}s_{2}}+v^{2}\mathbf{N}_{\theta(0,n)}+\mathbf{N}_{\theta(2,n-1)},$
(3.47) $\displaystyle L\overset{\mathbf{H}}{\geq}$ $\displaystyle
3\mathbf{N}_{\theta(0,n)}+2v\mathbf{N}_{\theta(1,n-1)}+v^{2}\mathbf{N}_{\theta(2,n-2)},$
(3.48) $\displaystyle L\overset{\mathbf{H}}{\geq}$ $\displaystyle
v^{-2}\mathbf{N}_{\theta(0,n)}+3v^{2}\mathbf{N}_{\theta(0,n-1)}+2v^{3}\mathbf{N}_{\theta(1,n-2)},$
(3.49) $\displaystyle L\overset{\mathbf{H}}{\geq}$
$\displaystyle\mathbf{N}_{\theta(0,n-1)}.$ (3.50)

Using Lemma 3.3 we can see that
$\mathbf{N}_{\theta(0,n)}{\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}}$
is a monotonic element of height $\theta(0,n+1)$. Furthermore,
$\mathbf{N}_{\theta(0,n-2)s_{0}s_{2}}$ is clearly monotonic. Since
$\theta(0,n-2)s_{0}s_{2}\leq\theta(0,n+1)$ we conclude that $L$ is monotonic.

An easy computation shows that

$\displaystyle
G_{\theta(0,n+1)}(\mathbf{H}_{\theta(0,n)}{\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}})$
$\displaystyle=1,$ (3.51) $\displaystyle
G_{\theta(0,n-1)}(v^{3}\mathbf{H}_{\theta(0,n-1)s_{0}}{\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}})$
$\displaystyle=1+v^{2}.$ (3.52)

This allows us to conclude that $G_{\theta(0,n+1)}(L)\geq 1$ and
$G_{\theta(0,n-1)}(L)\geq 1$. Then, the monotonicity of $L$ proves (3.46) and
(3.50).

We now focus on (3.47). We notice that $\theta(0,n)$ is smaller than
$\theta(0,n)s_{0}s_{2}$ and $\theta(2,n-1)$, but the latter elements are
incomparable in Bruhat order. Furthermore, by the description of lower
intervals given in §2.1 we have

$(\leq\theta(0,n)s_{0}s_{2})\cap(\leq\theta(2,n-1))=(\leq\theta(1,n-1)s_{1}s_{2}).$
(3.53)

Finally, we notice that $\theta(0,n)\leq\theta(1,n-1)s_{1}s_{2}$. Thus, by the
monotonicity of $L$, in order to prove (3.47) it is enough to show that

$\displaystyle G_{\theta(0,n)s_{0}s_{2}}(L)$ $\displaystyle\geq 2;$ (3.54)
$\displaystyle G_{\theta(2,n-1)}(L)$ $\displaystyle\geq 1;$ (3.55)
$\displaystyle G_{\theta(1,n-1)s_{1}s_{2}}(L)$ $\displaystyle\geq 3v;$ (3.56)
$\displaystyle G_{\theta(0,n)}(L)$ $\displaystyle\geq 4v^{2}.$ (3.57)

A direct computation shows that
$G_{\theta(0,n)s_{0}s_{2}}\left(\mathbf{H}_{\theta(0,n)}{\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}}\right)=2$.
This proves (3.54). Similarly, we have
$G_{\theta(2,n-1)}\left(v\mathbf{H}_{\theta(0,n-1)s_{0}s_{2}s_{1}}{\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}}\right)=1$,
which proves (3.55). On the other hand, we have

$\displaystyle
G_{\theta(1,n-1)s_{1}s_{2}}(v\mathbf{H}_{\theta(0,n-1)s_{0}s_{2}s_{1}}{\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}})$
$\displaystyle=2v;$ (3.58) $\displaystyle
G_{\theta(1,n-1)s_{1}s_{2}}(v^{2}\mathbf{H}_{\theta(0,n-1)s_{0}s_{2}}{\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}})$
$\displaystyle=v.$ (3.59)

This proves (3.56). Finally, we have

$\displaystyle
G_{\theta(0,n)}\left(v\mathbf{H}_{\theta(0,n-1)s_{0}s_{2}s_{1}}{\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}}\right)$
$\displaystyle=v^{2};$ (3.60) $\displaystyle
G_{\theta(0,n)}\left(v^{2}\mathbf{H}_{\theta(0,n-1)s_{0}s_{2}}{\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}}\right)$
$\displaystyle=v^{2};$ (3.61) $\displaystyle
G_{\theta(0,n)}\left(v^{3}\mathbf{H}_{\theta(0,n-1)s_{0}}{\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}}\right)$
$\displaystyle=v^{2};$ (3.62) $\displaystyle
G_{\theta(0,n)}\left(v^{2}\mathbf{H}_{d_{4n+2}}{\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}}\right)$
$\displaystyle=v^{2}.$ (3.63)

These four equalities show (3.57). This completes the proof of inequality
(3.47). The remaining two inequalities (3.48) and (3.49) are treated
similarly. ∎

We now are in a position to obtain a multiplication formula that relates
$\mathbf{N}_{\theta(0,n)}$ and $\mathbf{N}_{\theta(0,n+1)}$.

######  Proposition 3.18.

Let $n$ be an integer greater than $2$. Then,

$\mathbf{N}_{\theta(0,n)}({\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}}-2{\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{2}}+1-(v+v^{-1})^{2})=\mathbf{N}_{\theta(0,n+1)}+(1+v^{2})\mathbf{N}_{\theta(0,n-1)}+v^{2}\mathbf{N}_{\theta(2,n-2)}+\mathbf{N}_{\theta(2,n-1)}.$

(3.64)

###### Proof.

By combining Lemma 3.9 and Lemma 3.16 we obtain

$\mathbf{N}_{\theta(0,n)}{\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{2}}=\mathbf{N}_{\theta(0,n)s_{0}s_{2}}+\mathbf{N}_{\theta(0,n)}+v\mathbf{N}_{\theta(1,n-1)}+v^{2}\mathbf{N}_{\theta(0,n-1)}+v^{3}\mathbf{N}_{\theta(1,n-2)}-v^{4}\mathbf{N}_{\theta(0,n-2)s_{0}s_{2}}.$
(3.65)

Hence, the result follows by combining Lemma 3.17 and (3.65). ∎

So far we have proved several multiplicative identities involving
$\mathbf{N}$-elements. These will be sufficient to obtain formulas for
Kazhdan-Lusztig basis elements corresponding to elements in the big region in
§4. We end this section by stating some extra multiplicative identities that
will be useful to prove formulas for Kazhdan-Lusztig basis elements
corresponding to elements in the thick region in §5.

######  Lemma 3.19.

For $m\geq 1$, the element
$\left({\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{0}}-{\underline{\mathbf{H}}}_{s_{0}}\right)\mathbf{N}_{\theta(m,0)}$
is equal to

$\mathbf{N}_{s_{1}s_{2}s_{0}\theta(m,0)}+(v^{-1}+2v)\mathbf{N}_{\theta(m,0)}+v(\mathbf{N}_{\theta(m-2,1)}+\mathbf{N}_{s_{1}\theta^{\prime}(m-1,0)})+v^{2}(\mathbf{N}_{s_{0}\theta(m-2,0)}-\mathbf{N}_{s_{1}s_{2}s_{0}\theta(m-2,0)}).$
(3.66)

Furthermore, we have

$\left({\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{0}}-{\underline{\mathbf{H}}}_{s_{0}}\right)\mathbf{N}_{\theta(0,0)}=\mathbf{N}_{s_{1}s_{2}s_{0}\theta(0,0)}+(v+v^{-1})\mathbf{N}_{\theta(0,0)}.$
(3.67)

###### Proof.

Equation (3.67) can be verified manually. Similarly, we can check (3.66) for
$m=1$. We stress that in this case some terms vanish in accordance with Remark
3.8. From now and on we fix $m\geq 2$. We define
$L:={\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{0}}\mathbf{N}_{\theta(m,0)}+v^{2}\mathbf{N}_{s_{1}s_{2}s_{0}\theta(m-2,0)}$
and

$R:={\underline{\mathbf{H}}}_{s_{0}}\mathbf{N}_{\theta(m,0)}+\mathbf{N}_{s_{1}s_{2}s_{0}\theta(m,0)}+(v^{-1}+2v)\mathbf{N}_{\theta(m,0)}+v(\mathbf{N}_{\theta(m-2,1)}+\mathbf{N}_{s_{1}\theta^{\prime}(m-1,0)})+v^{2}\mathbf{N}_{s_{0}\theta(m-2,0)}.$
(3.68)

It is clear that the claim in the lemma is equivalent to $L=R$, which we will
now prove. Using Lemma 3.10, we can rewrite $R$ as

$R=\mathbf{N}_{s_{0}\theta(m,0)}+\mathbf{N}_{s_{1}s_{2}s_{0}\theta(m,0)}+(v^{-1}+2v)\mathbf{N}_{\theta(m,0)}+v(\mathbf{N}_{\theta(m-2,1)}+2\mathbf{N}_{s_{1}\theta^{\prime}(m-1,0)})+v^{2}\mathbf{N}_{s_{0}\theta(m-2,0)}.$
(3.69)

A straightforward computation using Corollary 2.5 and Lemma 2.7 shows

$c(L)=c(R)=8(9m^{2}+17m+4).$ (3.70)

To complete the proof we only need to show that
$L\overset{\mathbf{H}}{\geq}R$. By degree reasons, this inequality will follow
from the next four inequalities

$\displaystyle L$
$\displaystyle\overset{\mathbf{H}}{\geq}\mathbf{N}_{s_{1}s_{2}s_{0}\theta(m,0)}$
(3.71) $\displaystyle L$
$\displaystyle\overset{\mathbf{H}}{\geq}\mathbf{N}_{s_{0}\theta(m,0)}+2v\mathbf{N}_{\theta(m,0)}$
(3.72) $\displaystyle L$
$\displaystyle\overset{\mathbf{H}}{\geq}v^{-1}\mathbf{N}_{\theta(m,0)}+2v\mathbf{N}_{s_{1}\theta^{\prime}(m-1,0)}+v\mathbf{N}_{\theta(m-2,1)}$
(3.73) $\displaystyle L$
$\displaystyle\overset{\mathbf{H}}{\geq}v^{2}\mathbf{N}_{s_{0}\theta(m-2,0)}.$
(3.74)

We notice that the left version of Lemma 3.3 shows that $L$ is monotonic.
Inequalities (3.71), (3.72) and (3.74) are easily obtained, so we will focus
on (3.73). We notice that $\theta(m,0)$ is greater than
$s_{1}\theta^{\prime}(m-1,0)$ and than $\theta(m-2,1)$ but the last two
elements are incomparable in Bruhat order. By the diagrammatic description of
the lower intervals given in §2.1 we obtain

$(\leq s_{1}\theta^{\prime}(m-1,0))\cap(\leq\theta(m-2,1))=(\leq
s_{1}s_{2}s_{0}\theta(m-2,0)).$ (3.75)

Therefore, by the monotonicity of $L$, (3.73) reduces to proving the following
polynomial inequalities

$\displaystyle G_{\theta(m,0)}(L)$ $\displaystyle\geq v^{-1},$ (3.76)
$\displaystyle G_{s_{1}\theta^{\prime}(m-1,0)}(L)$ $\displaystyle\geq 3v,$
(3.77) $\displaystyle G_{\theta(m-2,1)}(L)$ $\displaystyle\geq 2v,$ (3.78)
$\displaystyle G_{s_{1}s_{2}s_{0}\theta(m-2,0)}(L)$ $\displaystyle\geq
4v^{2}.$ (3.79)

Set
$X:={\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{0}}$.
A direct computation (using the left version of (3.8)) shows that
$G_{\theta(m,0)}(X\mathbf{H}_{\theta(m,0)})=v^{-1}$, proving (3.76).
Similarly, we have

$G_{s_{1}\theta^{\prime}(m-1,0)}(X(v\mathbf{H}_{s_{2}s_{1}\theta^{\prime}(m-1,0)}))=G_{s_{1}\theta^{\prime}(m-1,0)}(X(v^{2}\mathbf{H}_{s_{1}\theta^{\prime}(m-1,0)}))=G_{s_{1}\theta^{\prime}(m-1,0)}(X(v^{3}\mathbf{H}_{\theta^{\prime}(m-1,0)}))=v.$
(3.80)

These three equalities together prove (3.77). We now observe that

$G_{\theta(m-2,1)}(X(v^{2}\mathbf{H}_{s_{1}\theta^{\prime}(m-1,0)}))=G_{\theta(m-2,1)}(X(v^{2}\mathbf{H}_{\theta(m-2,1)}))=v.$
(3.81)

This proves (3.78). Finally, if we set $z:=s_{1}s_{2}s_{0}\theta(m-2,0)$ then
we have

$G_{z}(X(v^{2}\mathbf{H}_{s_{1}\theta^{\prime}(m-1,0)}))=G_{z}(X(v^{2}\mathbf{H}_{\theta(m-2,1)}))=G_{z}(X(v^{3}\mathbf{H}_{\theta^{\prime}(m-1,0)}))=v^{2}.$
(3.82)

These three equalities show that $G_{z}(X\mathbf{N}_{\theta(m,0)})\geq
3v^{2}$. Since $G_{z}(v^{2}\mathbf{N}_{z})=v^{2}$, inequality (3.79) follows
from the definition of $L$. The lemma is proved. ∎

Using similar arguments we can prove the following result, recalling the
definitions of $x_{n}$, $e_{n}$ and $u_{n}$ from the introduction. The details
are left to the reader.

######  Lemma 3.20.

Given an integer $k$ we set $f(k)=3k+1$. Let
$Y={\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{0}}-{\underline{\mathbf{H}}}_{s_{0}}$.
For $k\geq 2$,

$\displaystyle\mathbf{N}_{x_{f(k)}}Y$
$\displaystyle=\mathbf{N}_{x_{f(k+1)}}+\mathbf{N}_{x_{f(k-1)}}+\mathbf{N}_{\theta(k-1,0)t_{k-1}}+\mathbf{N}_{s_{1}s_{2}s_{0}\theta(k-2,0)t_{k-2}}+\mathbf{N}_{s_{1}\theta^{\prime}(k-2,0)t^{\prime}_{k-2}}+v\mathbf{N}_{\theta(k-2,0)t_{k-2}}$
(3.83) $\displaystyle\mathbf{N}_{u_{f(k)}}Y$
$\displaystyle=\mathbf{N}_{u_{f(k+1)}}+\mathbf{N}_{u_{f(k-1)}}+\mathbf{N}_{\theta(k-2,1)t_{k-2}}+(v+v^{-1})\mathbf{N}_{\theta(k-1,0)t_{k-1}}+v^{2}\mathbf{N}_{u_{f(k-1)}}$
(3.84) $\displaystyle\mathbf{N}_{e_{f(k)}}Y$
$\displaystyle=\mathbf{N}_{e_{f(k+1)}}+\mathbf{N}_{e_{f(k-1)}}+\mathbf{N}_{s_{0}\theta(k-1,0)t_{k-1}}+\mathbf{N}_{s_{1}\theta^{\prime}(k-1,0)t^{\prime}_{k-1}}+v\mathbf{N}_{s_{0}\theta(k-2,0)t_{k-2}}+v\mathbf{N}_{s_{1}\theta^{\prime}(k-2,0)t^{\prime}_{k-2}}.$
(3.85)

In each case, the identity also holds if $Y$ is replaced by
$Y^{\prime}={\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{1}}-{\underline{\mathbf{H}}}_{s_{1}}$.

######  Remark 3.21.

The reader may have noticed that in the second formula
$\mathbf{N}_{u_{f(k-1)}}$ shows up twice with different coefficients. This may
appear to be a slip, but it is not. The reason behind this choice will become
clear in Section 5.

##  4 Kazhdan-Lusztig basis in the big region

In this section we provide an explicit formula for Kazhdan-Lusztig basis
elements indexed by elements located in the big region.

###  4.1 Kazhdan-Lusztig basis in region $\mathfrak{C}$

Let us recall a definition from the introduction.

######  Definition 4.1.

Let $(m,n)\in\mathbb{N}^{2}$. We define

$\operatorname{Supp}(m,n)=\left\\{\begin{array}[]{ll}\\{(m-2i,n-j)\in\mathbb{N}^{2}\,|\,i,j\in\mathbb{N}\\},&\mbox{if
}m\mbox{ is odd;}\\\
\\{(m-2i,n-j)\in\mathbb{N}^{2}\,|\,i,j\in\mathbb{N}\\}-\\{(0,b)\,\
\,|\,b\not\equiv n\mod 2\\},&\mbox{if }m\mbox{ is even. }\end{array}\right.$
(4.1)

We also define

$\hat{{\underline{\mathbf{H}}}}_{\theta(m,n)}:=\sum_{(a,b)\in\operatorname{Supp}(m,n)}v^{(m-a)+2(n-b)}\mathbf{N}_{\theta(a,b)}.$
(4.2)

The first goal in this section is to prove that
${\underline{\mathbf{H}}}_{\theta(m,n)}=\hat{{\underline{\mathbf{H}}}}_{\theta(m,n)}$
for all $(m,n)\in\mathbb{N}^{2}$. To do this we need several preliminary
lemmas.

######  Lemma 4.2.

Let $m$ and $n$ be positive integers. Then,

$\hat{{\underline{\mathbf{H}}}}_{\theta(m,n)}=\mathbf{N}_{\theta(m,n)}+v^{2}\hat{{\underline{\mathbf{H}}}}_{\theta(m-2,n)}+v^{2}\hat{{\underline{\mathbf{H}}}}_{\theta(m,n-1)}-v^{4}\hat{{\underline{\mathbf{H}}}}_{\theta(m-2,n-1)}.$
(4.3)

Furthermore,

$\hat{{\underline{\mathbf{H}}}}_{\theta(0,n)}=\mathbf{N}_{\theta(0,n)}+v^{4}\hat{{\underline{\mathbf{H}}}}_{\theta(0,n-2)}\quad\mbox{
and
}\quad\hat{{\underline{\mathbf{H}}}}_{\theta(m,0)}=\mathbf{N}_{\theta(m,0)}+v^{2}\hat{{\underline{\mathbf{H}}}}_{\theta(m-2,0)}.$
(4.4)

###### Proof.

The result follows directly from the definition of the elements
$\hat{{\underline{\mathbf{H}}}}_{\theta(m,n)}$ once we recall our convention
about negative indices in Remark 3.8. ∎

######  Lemma 4.3.

Let $(m,n)\in\mathbb{N}^{2}$. Then

$\hat{{\underline{\mathbf{H}}}}_{\theta(m,n)}({\underline{\mathbf{H}}}_{t_{m}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{t_{m}}-2{\underline{\mathbf{H}}}_{t_{m}})=\hat{{\underline{\mathbf{H}}}}_{\theta(m+1,n)}+\hat{{\underline{\mathbf{H}}}}_{\theta(m-1,n+1)}+\hat{{\underline{\mathbf{H}}}}_{\theta(m+1,n-1)}+\hat{{\underline{\mathbf{H}}}}_{\theta(m-1,n)}.$
(4.5)

###### Proof.

A direct computation shows that (4.5) holds for the pairs $(0,0)$, $(1,0)$,
$(0,1)$ , $(2,0)$ , $(1,1)$ and $(0,2)$. We now fix $u\geq 3$ and assume that
(4.5) holds for all pairs $(m^{\prime},n^{\prime})$ with
$m^{\prime}+n^{\prime}<u$. We fix a pair $(m,n)$ with $m+n=u$. We split the
proof in four cases. We recall that the set of $D_{R}(\theta(a,b))$ only
depends on the parity of $a$. For the sake of brevity we write

$X_{\uparrow}^{1}:={\underline{\mathbf{H}}}_{t_{m}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{t_{m}}-2{\underline{\mathbf{H}}}_{t_{m}}.$
(4.6)

Case A. Suppose that $m\geq 2$ and $n\geq 1$.
Using Proposition 3.14, Lemma 4.2 and our inductive hypothesis we get

$\hat{{\underline{\mathbf{H}}}}_{\theta(m,n)}X_{\uparrow}^{1}=\begin{array}[]{cccccccc}\mathbf{N}_{\theta(m+1,n)}&+&\mathbf{N}_{\theta(m-1,n+1)}&+&\mathbf{N}_{\theta(m+1,n-1)}&+&\mathbf{N}_{\theta(m-1,n)}&+\\\
v^{2}\hat{{\underline{\mathbf{H}}}}_{\theta(m-1,n)}&+&v^{2}\hat{{\underline{\mathbf{H}}}}_{\theta(m-3,n+1)}&+&v^{2}\hat{{\underline{\mathbf{H}}}}_{\theta(m-1,n-1)}&+&v^{2}\hat{{\underline{\mathbf{H}}}}_{\theta(m-3,n)}&+\\\
v^{2}\hat{{\underline{\mathbf{H}}}}_{\theta(m+1,n-1)}&+&v^{2}\hat{{\underline{\mathbf{H}}}}_{\theta(m-1,n)}&+&v^{2}\hat{{\underline{\mathbf{H}}}}_{\theta(m+1,n-2)}&+&v^{2}\hat{{\underline{\mathbf{H}}}}_{\theta(m-1,n-1)}&-\\\
v^{4}\hat{{\underline{\mathbf{H}}}}_{\theta(m-1,n-1)}&-&v^{4}\hat{{\underline{\mathbf{H}}}}_{\theta(m-3,n)}&-&v^{4}\hat{{\underline{\mathbf{H}}}}_{\theta(m-1,n-2)}&-&v^{4}\hat{{\underline{\mathbf{H}}}}_{\theta(m-3,n-1)}.&\end{array}$
(4.7)

Then, by adding by columns in the right-hand side of (4.7) and using Lemma 4.2
we obtain (4.5).

Case B. Suppose that $m=1$ and $n\geq 2$.
The main difference with respect to the above Case A is that when we decompose
$\hat{{\underline{\mathbf{H}}}}_{\theta(1,n)}$ using Lemma 4.2 there are two
terms that do not appear. More concretely, we have

$\hat{{\underline{\mathbf{H}}}}_{\theta(1,n)}=\mathbf{N}_{\theta(1,n)}+v^{2}\hat{{\underline{\mathbf{H}}}}_{\theta(1,n-1)}.$
(4.8)

Using Proposition 3.14 and our inductive hypothesis we get

$\hat{{\underline{\mathbf{H}}}}_{\theta(1,n)}X_{\uparrow}^{1}=\begin{array}[]{cccccccc}\mathbf{N}_{\theta(2,n)}&+&\mathbf{N}_{\theta(0,n+1)}&+&\mathbf{N}_{\theta(2,n-1)}&+&\mathbf{N}_{\theta(0,n)}&+\\\
v^{2}\hat{{\underline{\mathbf{H}}}}_{\theta(2,n-1)}&+&v^{2}\hat{{\underline{\mathbf{H}}}}_{\theta(0,n)}&+&v^{2}\hat{{\underline{\mathbf{H}}}}_{\theta(2,n-2)}&+&v^{2}\hat{{\underline{\mathbf{H}}}}_{\theta(0,n-1)}.&\end{array}$
(4.9)

We now use (4.4) to rewrite $\mathbf{N}_{\theta(0,n+1)}$ and
$\mathbf{N}_{\theta(0,n)}$ as

$\mathbf{N}_{\theta(0,n+1)}=\hat{{\underline{\mathbf{H}}}}_{\theta(0,n+1)}-v^{4}\hat{{\underline{\mathbf{H}}}}_{\theta(0,n-1)}\quad\mbox{
and
}\quad\mathbf{N}_{\theta(0,n)}=\hat{{\underline{\mathbf{H}}}}_{\theta(0,n)}-v^{4}\hat{{\underline{\mathbf{H}}}}_{\theta(0,n-2)}$
(4.10)

within (4.9). Another application of Lemma 4.2 gives us (4.5).

Case C. Suppose that $m=0$ and $n\geq 3$.
As in the previous cases we use Lemma 4.2 in order to get

$\hat{{\underline{\mathbf{H}}}}_{\theta(0,n)}=\mathbf{N}_{\theta(0,n)}+v^{4}\hat{{\underline{\mathbf{H}}}}_{\theta(0,n-2)}.$
(4.11)

Using Proposition 3.15 and our inductive hypothesis we get

$\hat{{\underline{\mathbf{H}}}}_{\theta(0,n)}X_{\uparrow}^{1}=(\mathbf{N}_{\theta(1,n)}+v^{2}\mathbf{N}_{\theta(1,n-1)}+v^{4}\hat{{\underline{\mathbf{H}}}}_{\theta(1,n-2)})+(\mathbf{N}_{\theta(1,n-1)}+v^{2}\mathbf{N}_{\theta(1,n-2)}+v^{4}\hat{{\underline{\mathbf{H}}}}_{\theta(1,n-3)}).$
(4.12)

Finally, two applications of Lemma 4.2 give (4.5).

Case D.  $m\geq 3$ and $n=0$.
By combining (4.4), Proposition 3.15 and our inductive hypothesis we get

$\begin{array}[]{rl}\hat{{\underline{\mathbf{H}}}}_{\theta(m,0)}X_{\uparrow}^{1}=&(\mathbf{N}_{\theta(m+1,0)}+v^{2}\hat{{\underline{\mathbf{H}}}}_{\theta(m-1,0)})+(\mathbf{N}_{\theta(m-1,1)}+v^{2}\mathbf{N}_{\theta(m-1,0)}+v^{2}\hat{{\underline{\mathbf{H}}}}_{\theta(m-3,1)})+(\mathbf{N}_{\theta(m-1,0)}+v^{2}\hat{{\underline{\mathbf{H}}}}_{\theta(m-3,0)})\\\
=&\hat{{\underline{\mathbf{H}}}}_{\theta(m+1,0)}+\hat{{\underline{\mathbf{H}}}}_{\theta(m-1,1)}+\hat{{\underline{\mathbf{H}}}}_{\theta(m-1,0)}.\end{array}$

(4.13)

This completes the proof of the lemma. ∎

######  Lemma 4.4.

For all $n\in\mathbb{N}$ we have

$\hat{{\underline{\mathbf{H}}}}_{\theta(0,n)}({\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}}-2{\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{2}}+1-(v+v^{-1})^{2})=\hat{{\underline{\mathbf{H}}}}_{\theta(0,n+1)}+\hat{{\underline{\mathbf{H}}}}_{\theta(2,n-1)}+\hat{{\underline{\mathbf{H}}}}_{\theta(0,n-1)}.$
(4.14)

###### Proof.

We proceed by induction on $n$. The result can be checked directly for $n\leq
3$, so we assume that $n>3$ and that (4.14) holds for all $n^{\prime}<n$. We
write

$X_{\uparrow}^{2}:={\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}}-2{\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{2}}+1-(v+v^{-1})^{2}.$
(4.15)

By combining Proposition 3.18, Lemma 4.2 and our inductive hypothesis we
obtain

$\begin{array}[]{rl}&\left(\mathbf{N}_{\theta(0,n+1)}+v^{4}\hat{{\underline{\mathbf{H}}}}_{\theta(0,n-1)}\right)+\\\
\hat{{\underline{\mathbf{H}}}}_{\theta(0,n)}X_{\uparrow}^{2}=&\left(\mathbf{N}_{\theta(2,n-1)}+v^{2}\mathbf{N}_{\theta(2,n-2)}+v^{2}\mathbf{N}_{\theta(0,n-1)}+v^{4}\hat{{\underline{\mathbf{H}}}}_{\theta(2,n-3)}\right)+\\\
&\left(\mathbf{N}_{\theta(0,n-1)}+v^{4}\hat{{\underline{\mathbf{H}}}}_{\theta(0,n-3)}\right)\\\
=&\hat{{\underline{\mathbf{H}}}}_{\theta(0,n+1)}+\hat{{\underline{\mathbf{H}}}}_{\theta(2,n-1)}+\hat{{\underline{\mathbf{H}}}}_{\theta(0,n-1)},\end{array}$
(4.16)

where for the last equality we have used (4.4) and the identity

$\hat{{\underline{\mathbf{H}}}}_{\theta(2,n-1)}=\mathbf{N}_{\theta(2,n-1)}+v^{2}\mathbf{N}_{\theta(2,n-2)}+v^{2}\mathbf{N}_{\theta(0,n-1)}+v^{4}\hat{{\underline{\mathbf{H}}}}_{\theta(2,n-3)},$
(4.17)

which follows directly from the definition of
$\hat{{\underline{\mathbf{H}}}}_{\theta(2,n-1)}$. ∎

######  Theorem 4.5.

For all $(m,n)\in\mathbb{N}^{2}$ we have
$\hat{{\underline{\mathbf{H}}}}_{\theta(m,n)}={\underline{\mathbf{H}}}_{\theta(m,n)}$.

###### Proof.

By definition of $\hat{{\underline{\mathbf{H}}}}_{\theta(m,n)}$ it is clear
that $G_{\theta(m,n)}(\hat{{\underline{\mathbf{H}}}}_{\theta(m,n)})=1$ and
that $G_{x}(\hat{{\underline{\mathbf{H}}}}_{\theta(m,n)})\in v\mathbb{N}[v]$
for all $x<\theta(m,n)$. Therefore, in order to prove the theorem it is enough
to show that $\hat{{\underline{\mathbf{H}}}}_{\theta(m,n)}$ is self-dual. To
do this we proceed by induction on $m+n$. The result is clear for the pair
$(0,0)$ since
${\underline{\mathbf{H}}}_{\theta(0,0)}=\mathbf{N}_{\theta(0,0)}=\hat{{\underline{\mathbf{H}}}}_{\theta(0,0)}$.
We fix $u\in\mathbb{N}$ and assume that
$\hat{{\underline{\mathbf{H}}}}_{\theta(m,n)}$ is self-dual for all pairs
$(m,n)$ such that $m+n\leq u$. By Lemma 4.3 we know that

$\hat{{\underline{\mathbf{H}}}}_{\theta(m,n)}({\underline{\mathbf{H}}}_{t_{m}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{t_{m}}-2{\underline{\mathbf{H}}}_{t_{m}})=\hat{{\underline{\mathbf{H}}}}_{\theta(m+1,n)}+\hat{{\underline{\mathbf{H}}}}_{\theta(m-1,n+1)}+\hat{{\underline{\mathbf{H}}}}_{\theta(m+1,n-1)}+\hat{{\underline{\mathbf{H}}}}_{\theta(m-1,n)}.$
(4.18)

We notice that
${\underline{\mathbf{H}}}_{t_{m}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{t_{m}}-2{\underline{\mathbf{H}}}_{t_{m}}$
is self-dual. Also, the terms $\hat{{\underline{\mathbf{H}}}}_{\theta(m,n)}$,
$\hat{{\underline{\mathbf{H}}}}_{\theta(m-1,n+1)}$,
$\hat{{\underline{\mathbf{H}}}}_{\theta(m+1,n-1)}$ and
$\hat{{\underline{\mathbf{H}}}}_{\theta(m-1,n)}$ are self-dual by our
inductive hypothesis. We can thus conclude that
$\hat{{\underline{\mathbf{H}}}}_{\theta(m+1,n)}$ is self-dual as well. This
shows that $\hat{{\underline{\mathbf{H}}}}_{\theta(a,b)}$ is self-dual for all
the pairs $(a,b)$ with $a+b=u+1$ and $a\neq 0$.

It remains to show that $\hat{{\underline{\mathbf{H}}}}_{\theta(0,u+1)}$ is
self-dual. By Lemma 4.4 we know that

$\hat{{\underline{\mathbf{H}}}}_{\theta(0,u)}({\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}}-2{\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{2}}+1-(v+v^{-1})^{2})=\hat{{\underline{\mathbf{H}}}}_{\theta(0,u+1)}+\hat{{\underline{\mathbf{H}}}}_{\theta(2,u-1)}+\hat{{\underline{\mathbf{H}}}}_{\theta(0,u-1)}.$
(4.19)

We notice that
${\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}}-2{\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{2}}+1-(v+v^{-1})^{2}$
is self-dual and that $\hat{{\underline{\mathbf{H}}}}_{\theta(0,u-1)}$ is also
self-dual by our inductive hypothesis. Although the self-duality of
$\hat{{\underline{\mathbf{H}}}}_{\theta(2,u-1)}$ is not covered by our
inductive hypothesis, we have already proved its self-duality since $(2,u-1)$
is a pair $(a,b)$ with $a\neq 0$. As before, we conclude that
$\hat{{\underline{\mathbf{H}}}}_{\theta(0,u+1)}$ is self-dual as well, and the
theorem is proved. ∎

######  Remark 4.6.

There is an alternative way to prove Theorem 4.5 using the results in [LPP21].
We prefer to present the proof just given in order to keep this paper self-
contained and cite only available sources.

######  Theorem 4.7.

Let $(m,n)\in\mathbb{N}^{2}$. Then,

$\displaystyle{\underline{\mathbf{H}}}_{\theta(m,n)}{\underline{\mathbf{H}}}_{t_{m}}$
$\displaystyle={\underline{\mathbf{H}}}_{\theta(m,n)t_{m}}$ (4.20)
$\displaystyle{\underline{\mathbf{H}}}_{\theta(m,n)t_{m}}{\underline{\mathbf{H}}}_{s_{2}}$
$\displaystyle={\underline{\mathbf{H}}}_{\theta(m,n)t_{m}s_{2}}+{\underline{\mathbf{H}}}_{\theta(m,n)}$
(4.21)
$\displaystyle{\underline{\mathbf{H}}}_{\theta(m,n)t_{m}s_{2}}{\underline{\mathbf{H}}}_{t_{m}^{\prime}}$
$\displaystyle={\underline{\mathbf{H}}}_{\theta(m,n)t_{m}s_{2}t_{m}^{\prime}}+{\underline{\mathbf{H}}}_{\theta(m,n)t_{m}}.$
(4.22)

###### Proof.

By Lemma 2.16, we have $xt_{m}>x$ for all $x\lessdot\theta(m,n)$. On the other
hand, Theorem 4.5 implies that $\mu(x,\theta(m,n))\neq 0$ if and only if
$x\lessdot\theta(m,n)$. Hence, (3.3) implies (4.20).

In order to prove (4.21) we begin by noticing that Lemma 2.16 implies that the
only element in $\lessdot\theta(m,n)t_{m}$ satisfying $xs_{2}<x$ is
$\theta(m,n)$. Therefore, a combination of (3.3) and Lemma 3.6 yields

${\underline{\mathbf{H}}}_{\theta(m,n)t_{m}}{\underline{\mathbf{H}}}_{s_{2}}={\underline{\mathbf{H}}}_{\theta(m,n)t_{m}s_{2}}+{\underline{\mathbf{H}}}_{\theta(m,n)}+\sum_{\begin{subarray}{c}y\in
W\\\
D_{R}(y)=\\{t_{m},t_{m}^{\prime},s_{2}\\}\end{subarray}}{m_{y}}{\underline{\mathbf{H}}}_{y},$
(4.23)

where $m_{y}\in\mathbb{N}$. We stress that
$D_{R}(\theta(m,n)t_{m})=\\{t_{m},t_{m}^{\prime}\\}$. Since there is no $y\in
W$ with $D_{R}(y)=\\{t_{m},t_{m}^{\prime},s_{2}\\}$ we conclude that the sum
in (4.23) is empty. This gives (4.21).

We now prove (4.22). Once again, Lemma 2.16 shows that the only element in
$\lessdot\theta(m,n)t_{m}s_{2}$ satisfying $xt_{m}^{\prime}<x$ is
$\theta(m,n)t_{m}$. Hence (3.3) and Lemma 3.6 give

${\underline{\mathbf{H}}}_{\theta(m,n)t_{m}s_{2}}{\underline{\mathbf{H}}}_{t_{m}^{\prime}}={\underline{\mathbf{H}}}_{\theta(m,n)t_{m}s_{2}t_{m}^{\prime}}+{\underline{\mathbf{H}}}_{\theta(m,n)t_{m}}+\sum_{y\in
Y}{n_{y}}{\underline{\mathbf{H}}}_{y},$ (4.24)

where $n_{y}\in\mathbb{N}$ and $Y=\\{y\in
W\,|\,D_{R}(y)=\\{t_{m}^{\prime},s_{2}\\},\,D_{L}(y)=\\{s_{1},s_{2}\\}\\}$ .

By the discussion at the beginning of §2.1 we conclude that $y\in Y$ if and
only if there exist $(a,b)\in\mathbb{N}^{2}$ with $a\equiv m\bmod 2$ such that
$y=\theta(a,b)$. We now multiply (4.24) on the right by
${\underline{\mathbf{H}}}_{t_{m}}$ and using (3.4) and (4.20) we obtain

${\underline{\mathbf{H}}}_{\theta(m,n)t_{m}s_{2}}{\underline{\mathbf{H}}}_{t_{m}^{\prime}}{\underline{\mathbf{H}}}_{t_{m}}={\underline{\mathbf{H}}}_{\theta(m,n)t_{m}s_{2}t_{m}^{\prime}}{\underline{\mathbf{H}}}_{t_{m}}+(v+v^{-1}){\underline{\mathbf{H}}}_{\theta(m,n)t_{m}}+\sum_{y\in
Y}{n_{y}}{\underline{\mathbf{H}}}_{yt_{m}}.$ (4.25)

On the other hand, we combine (3.4), Lemma 4.3, Theorem 4.5, (4.20) and (4.21)
to obtain

${\underline{\mathbf{H}}}_{\theta(m,n)t_{m}s_{2}}{\underline{\mathbf{H}}}_{t_{m}}{\underline{\mathbf{H}}}_{t_{m}^{\prime}}=(v+v^{-1}){\underline{\mathbf{H}}}_{\theta(m,n)t_{m}}+{\underline{\mathbf{H}}}_{\theta(m+1,n)t_{m}^{\prime}}+{\underline{\mathbf{H}}}_{\theta(m-1,n+1)t_{m}^{\prime}}+{\underline{\mathbf{H}}}_{\theta(m+1,n-1)t_{m}^{\prime}}+{\underline{\mathbf{H}}}_{\theta(m-1,n)t_{m}^{\prime}}.$

(4.26)

We now notice that
${\underline{\mathbf{H}}}_{t_{m}}{\underline{\mathbf{H}}}_{t_{m}^{\prime}}={\underline{\mathbf{H}}}_{t_{m}^{\prime}}{\underline{\mathbf{H}}}_{t_{m}}$
and conclude that the right-hand side of (4.25) and (4.26) coincide.
Therefore, after cancelling out the term
$(v+v^{-1}){\underline{\mathbf{H}}}_{\theta(m,n)t_{m}}$ we get

${\underline{\mathbf{H}}}_{\theta(m,n)t_{m}s_{2}t_{m}^{\prime}}{\underline{\mathbf{H}}}_{t_{m}}+\sum_{y\in
Y}{n_{y}}{\underline{\mathbf{H}}}_{yt_{m}}={\underline{\mathbf{H}}}_{\theta(m+1,n)t_{m}^{\prime}}+{\underline{\mathbf{H}}}_{\theta(m-1,n+1)t_{m}^{\prime}}+{\underline{\mathbf{H}}}_{\theta(m+1,n-1)t_{m}^{\prime}}+{\underline{\mathbf{H}}}_{\theta(m-1,n)t_{m}^{\prime}}.$
(4.27)

Suppose that $n_{y}\neq 0$ for some $y=\theta(a,b)\in Y$. Since $a\equiv
m\bmod 2$ we know that $a\neq m\pm 1$. In particular, $\theta(a,b)t_{m}$ is
not equal to any of the elements that index the Kazhdan-Lusztig basis elements
on the right-hand side of (4.27). We reach a contradiction and conclude that
$n_{y}=0$ for all $y\in Y$. If we look back at (4.24) then we see that it
reduces to (4.22). ∎

###  4.2 Kazhdan-Lusztig basis for the whole big region

Let us remark that Theorem 4.5 and Theorem 4.7 give us all the Kazhdan-Lusztig
basis elements indexed by elements in the fundamental region $\mathfrak{C}$
and also in the region $\varphi(\mathfrak{C})$. In this section we extend this
result to all the elements in the big region. We stress that we only need
specify the description of the Kazhdan-Lusztig basis elements for the regions
$s_{0}\mathfrak{C}$, $s_{2}s_{0}\mathfrak{C}$ and
$s_{1}s_{2}s_{0}\mathfrak{C}$ since the description for the elements in the
regions $s_{1}\varphi(\mathfrak{C})$, $s_{2}s_{1}\varphi(\mathfrak{C})$ and
$s_{0}s_{2}s_{1}\varphi(\mathfrak{C})$ will follow from the above by applying
the automorphism $\varphi$.

######  Theorem 4.8.

Let $(m,n)\in\mathbb{N}^{2}$. Then,

$\displaystyle{\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{\theta(m,n)}$
$\displaystyle={\underline{\mathbf{H}}}_{s_{0}\theta(m,n)}$ (4.28)
$\displaystyle{\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{\theta(m,n)t_{m}}$
$\displaystyle={\underline{\mathbf{H}}}_{s_{0}\theta(m,n)t_{m}}$ (4.29)
$\displaystyle{\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{\theta(m,n)t_{m}s_{2}}$
$\displaystyle={\underline{\mathbf{H}}}_{s_{0}\theta(m,n)t_{m}s_{2}}$ (4.30)
$\displaystyle{\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{\theta(m,n)t_{m}s_{2}t_{m}^{\prime}}$
$\displaystyle={\underline{\mathbf{H}}}_{s_{0}\theta(m,n)t_{m}s_{2}t_{m}^{\prime}}$
(4.31)
$\displaystyle{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{0}\theta(m,n)}$
$\displaystyle={\underline{\mathbf{H}}}_{s_{2}s_{0}\theta(m,n)}+{\underline{\mathbf{H}}}_{\theta(m,n)}$
(4.32)
$\displaystyle{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{0}\theta(m,n)t_{m}}$
$\displaystyle={\underline{\mathbf{H}}}_{s_{2}s_{0}\theta(m,n)t_{m}}+{\underline{\mathbf{H}}}_{\theta(m,n)t_{m}}$
(4.33)
$\displaystyle{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{0}\theta(m,n)t_{m}s_{2}}$
$\displaystyle={\underline{\mathbf{H}}}_{s_{2}s_{0}\theta(m,n)t_{m}s_{2}}+{\underline{\mathbf{H}}}_{\theta(m,n)t_{m}s_{2}}$
(4.34)
$\displaystyle{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{0}\theta(m,n)t_{m}s_{2}t_{m}^{\prime}}$
$\displaystyle={\underline{\mathbf{H}}}_{s_{2}s_{0}\theta(m,n)t_{m}s_{2}t_{m}^{\prime}}+{\underline{\mathbf{H}}}_{\theta(m,n)t_{m}s_{2}t_{m}^{\prime}}$
(4.35)
$\displaystyle{\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}s_{0}\theta(m,n)}$
$\displaystyle={\underline{\mathbf{H}}}_{s_{1}s_{2}s_{0}\theta(m,n)}+{\underline{\mathbf{H}}}_{s_{0}\theta(m,n)}$
(4.36)
$\displaystyle{\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}s_{0}\theta(m,n)t_{m}}$
$\displaystyle={\underline{\mathbf{H}}}_{s_{1}s_{2}s_{0}\theta(m,n)t_{m}}+{\underline{\mathbf{H}}}_{s_{0}\theta(m,n)t_{m}}$
(4.37)
$\displaystyle{\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}s_{0}\theta(m,n)t_{m}s_{2}}$
$\displaystyle={\underline{\mathbf{H}}}_{s_{1}s_{2}s_{0}\theta(m,n)t_{m}s_{2}}+{\underline{\mathbf{H}}}_{s_{0}\theta(m,n)t_{m}s_{2}}$
(4.38)
$\displaystyle{\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}s_{0}\theta(m,n)t_{m}s_{2}t_{m}^{\prime}}$
$\displaystyle={\underline{\mathbf{H}}}_{s_{1}s_{2}s_{0}\theta(m,n)t_{m}s_{2}t_{m}^{\prime}}+{\underline{\mathbf{H}}}_{s_{0}\theta(m,n)t_{m}s_{2}t_{m}^{\prime}}.$
(4.39)

###### Proof.

We fix $(m,n)\in\mathbb{N}^{2}$ and let
$\mathcal{R}:=\\{e,t_{m},t_{m}s_{2},t_{m}s_{2}t_{m}^{\prime}\\}$. By our
description of the set of coatoms for lower intervals in Lemma 2.16 we have
$s_{0}x>x$ for all $y\in\mathcal{R}$ and $x\lessdot\theta(m,n)y$. Therefore,
since $D_{{L}}(\theta(m,n)y)=\\{s_{1},s_{2}\\}$ for all $y\in\mathcal{R}$ and
there is no element $z\in W$ with $D_{L}(z)=\\{s_{0},s_{1},s_{2}\\}$, we
obtain via the left version of (3.3) and Lemma 3.6 all the identities
(4.28)–(4.31). We pause our proof for a moment to make an observation that
will be useful for the rest of the proof.

######  Remark 4.9.

We remark that (4.28)–(4.31) together are equivalent to the following: For any
$z\in\mathfrak{C}$ we have
${\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{z}={\underline{\mathbf{H}}}_{s_{0}z}$.
Of course, by applying $\varphi$ to the above equality we get
${\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{u}={\underline{\mathbf{H}}}_{s_{1}u}$
for all $u\in\varphi(\mathfrak{C})$.

We continue with the proof of the next four identities. Now, Lemma 2.18 allows
us to conclude that for each $y\in\mathcal{R}$ the only element in $\lessdot
s_{0}\theta(m,n)y$ satisfying $s_{2}x<x$ is $\theta(m,n)y$. Since
$D_{{L}}(s_{0}\theta(m,n)y)=\\{s_{0},s_{1}\\}$ for all $y\in\mathcal{R}$,
another application of the left version of (3.3) and Lemma 3.6 give us
(4.32)–(4.35).

For the last four identities we need to work a little harder. In this case we
have $D_{L}(s_{2}s_{0}\theta(m,n)y)=\\{s_{2}\\}$ for all $y\in\mathcal{R}$.
Therefore, the left version of (3.3) and Lemma 3.6 only allow us to conclude
that for each $y\in\mathcal{R}$ we have

${\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}s_{0}\theta(m,n)y}={\underline{\mathbf{H}}}_{s_{1}s_{2}s_{0}\theta(m,n)y}+{\underline{\mathbf{H}}}_{s_{0}\theta(m,n)y}+\sum_{z\in\mathfrak{C}}m_{z}^{y}{\underline{\mathbf{H}}}_{z},$
(4.40)

where $m_{z}^{y}\in\mathbb{N}$.

We now multiply (4.40) by ${\underline{\mathbf{H}}}_{s_{0}}$ on the left, and
using (3.4) together with Remark 4.9 we get

${\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}s_{0}\theta(m,n)y}={\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{1}s_{2}s_{0}\theta(m,n)y}+(v+v^{-1}){\underline{\mathbf{H}}}_{s_{0}\theta(m,n)y}+\sum_{z\in\mathfrak{C}}m_{z}^{y}{\underline{\mathbf{H}}}_{s_{0}z}.$
(4.41)

We now compute
${\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}s_{0}\theta(m,n)y}$
in a different way using the fact that
${\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{1}}={\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{0}}$.
Lemma 2.18 shows that for all $y\in\mathcal{R}$ the only element in $\lessdot
s_{2}s_{0}\theta(m,n)y$ satisfying $s_{0}x<x$ is $s_{0}\theta(m,n)y$. On the
other hand, we notice that $s_{0}s_{2}s_{0}\theta(m,n)y$ belongs to
$\varphi(\mathfrak{C})$ since
$D_{L}(s_{0}s_{2}s_{0}\theta(m,n)y)=\\{s_{0},s_{2}\\}$. Using these two facts
together with the left version of (3.3) and Lemma 3.6 we obtain

$\begin{array}[]{rl}{\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{2}s_{0}\theta(m,n)y}=&{\underline{\mathbf{H}}}_{s_{1}}\left({\underline{\mathbf{H}}}_{s_{0}s_{2}s_{0}\theta(m,n)y}+{\underline{\mathbf{H}}}_{s_{0}\theta(m,n)y}+\displaystyle\sum_{u\in\varphi(\mathfrak{C})}n_{u}^{y}{\underline{\mathbf{H}}}_{u}\right)\\\
&\\\
=&{\underline{\mathbf{H}}}_{s_{1}s_{0}s_{2}s_{0}\theta(m,n)y}+(v+v^{-1}){\underline{\mathbf{H}}}_{s_{0}\theta(m,n)y}+\displaystyle\sum_{u\in\varphi(\mathfrak{C})}n_{u}^{y}{\underline{\mathbf{H}}}_{s_{1}u},\end{array}$
(4.42)

for some $n_{u}^{y}\in\mathbb{N}$.

We now fix $y\in\mathcal{R}$ and suppose that $m_{z}^{y}\neq 0$ for some
$z\in\mathfrak{C}$. By comparing the right-hand sides of (4.41) and (4.42), we
conclude that $s_{0}z\in s_{1}\varphi(\mathfrak{C})$, which is absurd since
$s_{0}\mathfrak{C}\cap s_{1}\varphi(\mathfrak{C})=\emptyset$. Therefore,
$m_{z}^{y}=0$ for all $z\in\mathfrak{C}$ and (4.40) reduces to

${\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}s_{0}\theta(m,n)y}={\underline{\mathbf{H}}}_{s_{1}s_{2}s_{0}\theta(m,n)y}+{\underline{\mathbf{H}}}_{s_{0}\theta(m,n)y}.$
(4.43)

Since this identity holds for all $y\in\mathcal{R}$ we obtain (4.36)–(4.39). ∎

######  Remark 4.10.

The formulas in Theorem 4.7 and Theorem 4.8 are apparently different from the
ones presented in Theorem 1.1. It is an easy exercise (which is left to the
reader) to show that both are equivalent.

###  4.3 Extra explicit formulas needed in the sequel

Formulas given in §4.1 and §4.2 enable the efficient computation of any
Kazhdan-Lusztig polynomial $h_{x,w}(v)$ for all $x\in W$ and all $w$ in the
big region. In order to obtain formulas for the thick region in §5, it will be
convenient to have more explicit expressions on hand for certain Kazhdan-
Lusztig basis elements in the big region. This is the main goal of this
section.

######  Lemma 4.11.

Let $m\geq 0$. We have
${\underline{\mathbf{H}}}_{\theta(m,0)t_{m}}=\mathbf{N}_{\theta(m,0)t_{m}}+v{\underline{\mathbf{H}}}_{\theta(m-1,0)t_{m-1}}$.

###### Proof.

We proceed by induction on $m$. The cases $m=0$ and $m=1$ are easily checked.
We assume $m>1$ and that the lemma holds for $m-1$. Using Lemma 3.9, the
explicit formula for ${\underline{\mathbf{H}}}_{\theta(m,0)}$, (4.20), our
inductive hypothesis and the fact that $t_{m}=t_{m-2}$ we obtain

$\begin{array}[]{rl}{\underline{\mathbf{H}}}_{\theta(m,0)t_{m}}=&{\underline{\mathbf{H}}}_{\theta(m,0)}{\underline{\mathbf{H}}}_{t_{m}}\\\
=&(\mathbf{N}_{\theta(m,0)}+v^{2}{\underline{\mathbf{H}}}_{\theta(m-2,0)}){\underline{\mathbf{H}}}_{t_{m}}\\\
=&\mathbf{N}_{\theta(m,0)t_{m}}+v\mathbf{N}_{\theta(m-1,0)t_{m-1}}+v^{2}{\underline{\mathbf{H}}}_{\theta(m-2,0)t_{m}}\\\
=&\mathbf{N}_{\theta(m,0)t_{m}}+v(\mathbf{N}_{\theta(m-1,0)t_{m-1}}+v{\underline{\mathbf{H}}}_{\theta(m-2,0)t_{m-2}})\\\
=&\mathbf{N}_{\theta(m,0)t_{m}}+v{\underline{\mathbf{H}}}_{\theta(m-1,0)t_{m-1}}.\end{array}$
(4.44)

∎

The proof of the following lemma is very similar.

######  Lemma 4.12.

For all $m\geq 0$, we have
${\underline{\mathbf{H}}}_{s_{0}\theta(m,0)}=\mathbf{N}_{s_{0}\theta(m,0)}+v{\underline{\mathbf{H}}}_{s_{1}\theta^{\prime}(m-1,0)}$.

######  Lemma 4.13.

For all $m\geq 0$ the element
${\underline{\mathbf{H}}}_{s_{1}s_{2}s_{0}\theta(m,0)}$ is equal to

$\mathbf{N}_{s_{1}s_{2}s_{0}\theta(m,0)}+\displaystyle
v\sum_{i=0}^{\lfloor\frac{m-1}{2}\rfloor}v^{2i}(\mathbf{N}_{\theta(m-2i,0)}+\mathbf{N}_{s_{1}\theta^{\prime}(m-1-2i,0)})+\sum_{i=1}^{\lfloor\frac{m}{2}\rfloor}v^{2i}(v^{-1}\mathbf{N}_{\theta(m-2i,1)}+\mathbf{N}_{s_{0}\theta(m-2i,0)}).$

(4.45)

###### Proof.

For $m=0$ and $m=1$ the result can be checked by a direct computation. We then
assume $m\geq 2$. Definition 4.1 and Theorem 4.5 give us the following
identity

${\underline{\mathbf{H}}}_{\theta(m,0)}=\displaystyle\sum_{i=0}^{\lfloor\frac{m}{2}\rfloor}v^{2i}\mathbf{N}_{\theta(m-2i,0)}.$
(4.46)

Then, combining (4.28), (4.32) and (4.36) we get

$\begin{array}[]{rl}{\underline{\mathbf{H}}}_{s_{1}s_{2}s_{0}\theta(m,0)}&=\left({\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{0}}-{\underline{\mathbf{H}}}_{s_{0}}-{\underline{\mathbf{H}}}_{s_{1}}\right){\underline{\mathbf{H}}}_{\theta(m,0)}\\\
&\\\
&=\left({\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{0}}-{\underline{\mathbf{H}}}_{s_{0}}\right){\underline{\mathbf{H}}}_{\theta(m,0)}-(v+v^{-1}){\underline{\mathbf{H}}}_{\theta(m,0)}\\\
&\\\
&=\left({\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{0}}-{\underline{\mathbf{H}}}_{s_{0}}\right)\displaystyle\sum_{i=0}^{\lfloor\frac{m}{2}\rfloor}v^{2i}\mathbf{N}_{\theta(m-2i,0)}-(v+v^{-1})\displaystyle\sum_{i=0}^{\lfloor\frac{m}{2}\rfloor}v^{2i}\mathbf{N}_{\theta(m-2i,0)}\\\
&=\displaystyle\sum_{i=0}^{\lfloor\frac{m}{2}\rfloor}\left({\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{0}}-{\underline{\mathbf{H}}}_{s_{0}}\right)v^{2i}\mathbf{N}_{\theta(m-2i,0)}-(v+v^{-1})\displaystyle\sum_{i=0}^{\lfloor\frac{m}{2}\rfloor}v^{2i}\mathbf{N}_{\theta(m-2i,0)}.\end{array}$
(4.47)

We assume $m$ is odd, the case $m$ even being similar. We then use Lemma 3.19
to conclude that

$\begin{array}[]{rl}{\underline{\mathbf{H}}}_{s_{1}s_{2}s_{0}\theta(m,0)}=&\displaystyle\sum_{i=0}^{\lfloor\frac{m}{2}\rfloor}v^{2i}\left[\mathbf{N}_{s_{1}s_{2}s_{0}\theta(m-2i,0)}-v^{2}\mathbf{N}_{s_{1}s_{2}s_{0}\theta(m-2(i+1),0)}\right]+\\\
&\\\
&\displaystyle\sum_{i=0}^{\lfloor\frac{m}{2}\rfloor}v^{2i}\left[v(\mathbf{N}_{\theta(m-2i,0)}+\mathbf{N}_{s_{1}\theta^{\prime}(m-1-2i,0)})+v^{2}(v^{-1}\mathbf{N}_{\theta(m-2(i+1),1)}+\mathbf{N}_{s_{0}\theta(m-2(i+1),0)})\right].\end{array}$

(4.48)

We notice that the first sum in (4.48) telescopes to
$\mathbf{N}_{s_{1}s_{2}s_{0}\theta(m,0)}$ and therefore the right-hand side of
(4.48) reduces to (4.45). We stress that the apparent discrepancy between both
expressions is solved by the fact that in (4.48) the term
$v^{-1}\mathbf{N}_{\theta(m-2(i+1),1)}+\mathbf{N}_{s_{0}\theta(m-2(i+1),0)}$
becomes zero when $i=(m-1)/2$. ∎

######  Corollary 4.14.

For all $m\geq 1$ we have

$\begin{array}[]{ll}{\underline{\mathbf{H}}}_{s_{1}s_{2}s_{0}\theta(m,0)t_{m}}=&\mathbf{N}_{s_{1}s_{2}s_{0}\theta(m,0)t_{m}}+v\mathbf{N}_{s_{1}s_{2}s_{0}\theta(m-1,0)t_{m-1}}+v^{k+2}\mathbf{N}_{s_{1}s_{0}}+\displaystyle\sum_{i=0}^{m}v^{i+1}\mathbf{N}_{\theta(m-i,0)t_{m-i}}+\\\
&\displaystyle\sum_{i=1}^{m}v^{i}\mathbf{N}_{s_{1}\theta^{\prime}(m-i,0)t^{\prime}_{m-i}}+\sum_{i=2}^{m}\left(v^{i-1}\mathbf{N}_{\theta(m-i,1)t_{m-i}}+v^{i}\mathbf{N}_{s_{0}\theta(m-i,0)t_{m-i}}\right).\end{array}$

(4.49)

Consequently,

$\begin{array}[]{ll}{\underline{\mathbf{H}}}_{s_{1}s_{2}s_{0}\theta(m+1,0)t_{m+1}}=&\mathbf{N}_{s_{1}s_{2}s_{0}\theta(m+1,0)t_{m+1}}+v{\underline{\mathbf{H}}}_{s_{1}s_{2}s_{0}\theta(m,0)t_{m}}-v^{2}\mathbf{N}_{s_{1}s_{2}s_{0}\theta(m-1,0)t_{m-1}}+\\\
&\\\
&v\mathbf{N}_{\theta(m+1,0)t_{m+1}}+v\mathbf{N}_{s_{1}\theta^{\prime}(m,0)t_{m}^{\prime}}+v\mathbf{N}_{\theta(m-1,1)t_{m-1}}+v^{2}\mathbf{N}_{s_{0}\theta(m-1,0)t_{m-1}}.\end{array}$
(4.50)

###### Proof.

We first notice that $(s_{1}s_{2}s_{0}\theta(m,0))^{-1}$ belongs to
$\mathfrak{C}$ (resp. $\varphi(\mathfrak{C})$) if $m$ is even (resp. odd).
Thus, using either (4.31) or its image under $\varphi$ we conclude that

${\underline{\mathbf{H}}}_{t_{m}}{\underline{\mathbf{H}}}_{(s_{1}s_{2}s_{0}\theta(m,0))^{-1}}={\underline{\mathbf{H}}}_{t_{m}(s_{1}s_{2}s_{0}\theta(m,0))^{-1}}.$
(4.51)

It follows that
${\underline{\mathbf{H}}}_{s_{1}s_{2}s_{0}\theta(m,0)t_{m}}={\underline{\mathbf{H}}}_{s_{1}s_{2}s_{0}\theta(m,0)}{\underline{\mathbf{H}}}_{t_{m}}$.
Therefore we can use the expression for
${\underline{\mathbf{H}}}_{s_{1}s_{2}s_{0}\theta(m,0)}$ given in Lemma 4.13 in
order to compute ${\underline{\mathbf{H}}}_{s_{1}s_{2}s_{0}\theta(m,0)t_{m}}$.
Then (4.49) follows by a combination of Lemma 3.7 with $n=1$, Lemma 3.9, Lemma
3.11 and its $\varphi$-image and Lemma 3.12. Finally, (4.50) is a direct
consequence of (4.49). ∎

The following result can be proved with similar arguments. For the sake of
brevity we omit the proof.

######  Lemma 4.15.

Let $m\in\mathbb{N}$. Then, we have

$\displaystyle{\underline{\mathbf{H}}}_{s_{0}\theta(m+1,0)t_{m+1}}$
$\displaystyle=\mathbf{N}_{s_{0}\theta(m+1,0)t_{m+1}}+v\mathbf{N}_{s_{1}\theta^{\prime}(m,0)t_{m}^{\prime}}+v{\underline{\mathbf{H}}}_{s_{0}\theta(m,0)t_{m}},$
(4.52)
$\displaystyle{\underline{\mathbf{H}}}_{s_{1}\theta^{\prime}(m+1,0)t_{m+1}^{\prime}}$
$\displaystyle=\mathbf{N}_{s_{1}\theta^{\prime}(m+1,0)t_{m+1}^{\prime}}+v\mathbf{N}_{s_{0}\theta(m,0)t_{m}}+v{\underline{\mathbf{H}}}_{s_{1}\theta^{\prime}(m,0)t_{m}^{\prime}}.$
(4.53)

##  5 Kazhdan-Lusztig polynomials for the thick region

In this section we compute Kazhdan-Lusztig basis elements corresponding to
elements in the thick region. We recall from Figure 1 that this region is made
of four sub-regions: north ($\mathcal{N}$), south ($\mathcal{S}$), east
($\mathcal{E}$) and west ($\mathcal{W}$). Recall from introduction that
$\mathcal{N}=\\{x_{n}\mid n\geq 1\\}\cup\\{\overline{x}_{3n}\mid n\geq 1\\}$,
where $x_{n}=a_{1}\cdots a_{n}$ and $\overline{x}_{n}=s_{1}s_{2}s_{0}x_{n-3}$,
and the $a_{i}$ are defined by the sequence
$\\{a_{n}\\}_{n=1}^{\infty}=(s_{1},s_{2},s_{1},s_{0},s_{2},s_{0},s_{1},s_{2},s_{1},s_{0},s_{2},s_{0},\ldots).$
We also recall that $\mathcal{S}=\varphi(\mathcal{N})$,
$\mathcal{E}=\\{e_{n}=s_{1}x^{\prime}_{n}\mid n\geq
1\\}\cup\\{e^{\prime}_{3k}\mid k\geq 1\\}$, and
$\mathcal{W}=s_{2}(\mathcal{E})\cup\\{s_{2}\\}$.

###  5.1 North and South

######  Definition 5.1.

We recall from the introduction the notation $f(k)=3k+1$ and
$u_{n}=s_{2}x_{n}$. For all $k\geq 2$ we define

$\hat{{\underline{\mathbf{H}}}}_{x_{f(k)}}=\mathbf{N}_{x_{f(k)}}+v\mathbf{N}_{x_{f(k-1)}}+\left(\sum_{j=2}^{k-1}v^{j-1}(\mathbf{N}_{e_{f(k-j)}}+\mathbf{N}_{u_{f(k-j)}})\right)+v^{k-1}\mathbf{N}_{s_{1}s_{0}}.$
(5.1)

######  Lemma 5.2.

Let
$Y={\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{1}}{\underline{\mathbf{H}}}_{s_{0}}-{\underline{\mathbf{H}}}_{s_{0}}$.
For all $k\geq 2$ we have

$\hat{{\underline{\mathbf{H}}}}_{x_{f(k)}}Y=\hat{{\underline{\mathbf{H}}}}_{x_{f(k+1)}}+\hat{{\underline{\mathbf{H}}}}_{x_{f(k-1)}}+{\underline{\mathbf{H}}}_{s_{1}\theta^{\prime}(k-2,0)t^{\prime}_{k-2}}+{\underline{\mathbf{H}}}_{\theta(k-1,0)t_{k-1}}+{\underline{\mathbf{H}}}_{\theta(k-3,0)t_{k-3}}+{\underline{\mathbf{H}}}_{s_{1}s_{2}s_{0}\theta(k-2,0)t_{k-2}}.$
(5.2)

###### Proof.

We proceed by induction on $k$. The case $k=2$ follows by a direct
computation. We assume the lemma holds for some $k\geq 2$. It follows directly
from Definition 5.1 that

$\hat{{\underline{\mathbf{H}}}}_{x_{f(k+1)}}=\mathbf{N}_{x_{f(k+1)}}+v\mathbf{N}_{e_{{f(k-1)}}}+v\mathbf{N}_{u_{f(k-1)}}-v^{2}\mathbf{N}_{x_{f(k-1)}}+v\hat{{\underline{\mathbf{H}}}}_{x_{f(k)}}.$
(5.3)

Multiplying this equality on the right by $Y$ and using our inductive
hypothesis and Lemma 3.20 we obtain that
$\hat{{\underline{\mathbf{H}}}}_{x_{f(k+1)}}Y$ is equal to the sum of all the
entries of the following matrix.

$\begin{array}[]{|c|c|c|c|c|c|}\hline\cr\mathbf{N}_{x_{f(k+2)}}&\mathbf{N}_{x_{f(k)}}&\mathbf{N}_{\theta(k,0)t_{k}}&\mathbf{N}_{s_{1}s_{2}s_{0}\theta(k-1,0)t_{k-1}}&\mathbf{N}_{s_{1}\theta^{\prime}(k-1,0)t^{\prime}_{k-1}}&v\mathbf{N}_{\theta(k-1,0)t_{k-1}}\\\
\hline\cr
v\mathbf{N}_{u_{f(k)}}&v\mathbf{N}_{u_{f(k-2)}}&v\mathbf{N}_{\theta(k-3,1)t_{k-3}}&v^{2}\mathbf{N}_{\theta(k-2,0)t_{k-2}}&\mathbf{N}_{\theta(k-2,0)t_{k-2}}&v^{3}\mathbf{N}_{u_{f(k-2)}}\\\
\hline\cr
v\mathbf{N}_{e_{f(k)}}&v\mathbf{N}_{e_{f(k-2)}}&v\mathbf{N}_{s_{0}\theta(k-2,0)t_{k-2}}&v\mathbf{N}_{s_{1}\theta^{\prime}(k-2,0)t^{\prime}_{k-2}}&v^{2}\mathbf{N}_{s_{0}\theta(k-3,0)t_{k-3}}&v^{2}\mathbf{N}_{s_{1}\theta^{\prime}(k-3,0)t^{\prime}_{k-3}}\\\
\hline\cr-v^{2}\mathbf{N}_{x_{f(k)}}&-v^{2}\mathbf{N}_{x_{f(k-2)}}&-v^{2}\mathbf{N}_{\theta(k-2,0)t_{k-2}}&-v^{2}\mathbf{N}_{s_{1}s_{2}s_{0}\theta(k-3,0)t_{k-3}}&-v^{2}\mathbf{N}_{s_{1}\theta^{\prime}(k-3,0)t^{\prime}_{k-3}}&-v^{3}\mathbf{N}_{\theta(k-3,0)t_{k-3}}\\\
\hline\cr
v\hat{{\underline{\mathbf{H}}}}_{x_{f(k+1)}}&v\hat{{\underline{\mathbf{H}}}}_{x_{f(k-1)}}&v{\underline{\mathbf{H}}}_{s_{1}\theta^{\prime}(k-2,0)t^{\prime}_{k-2}}&v{\underline{\mathbf{H}}}_{\theta(k-1,0)t_{k-1}}&v{\underline{\mathbf{H}}}_{\theta(k-3,0)t_{k-3}}&v{\underline{\mathbf{H}}}_{s_{1}s_{2}s_{0}\theta(k-2,0)t_{k-2}}\\\
\hline\cr\end{array}$

(5.4)

We denote this matrix by $A=(A_{ij})$. Using (5.3) we see that

$\hat{{\underline{\mathbf{H}}}}_{x_{f(k+2)}}=\sum_{i=1}^{5}A_{i1}\qquad\mbox{
and }\qquad\hat{{\underline{\mathbf{H}}}}_{x_{f(k)}}=\sum_{i=1}^{5}A_{i2}.$
(5.5)

By Lemma 4.11 we have
${\underline{\mathbf{H}}}_{\theta(k,0)t_{k}}=A_{13}+A_{54}$ and
${\underline{\mathbf{H}}}_{\theta(k-2,0)t_{k-2}}=A_{25}+A_{55}$. On the other
hand, Lemma 4.15 implies that
${\underline{\mathbf{H}}}_{s_{1}\theta^{\prime}(k-1,0)t_{k-1}^{\prime}}=A_{15}+A_{33}+A_{53}$.
We also observe that $A_{24}+A_{43}=A_{36}+A_{45}=A_{26}+A_{46}=0$, this last
equality being a consequence of the fact that
$\theta(k-3,0)t_{k-3}=u_{f({k-2})}$. Finally, we notice that Corollary 4.14
yields
${\underline{\mathbf{H}}}_{s_{1}s_{2}s_{0}\theta(k-1,0)t_{k-1}}=A_{14}+A_{56}+A_{44}+A_{16}+A_{34}+A_{23}+A_{35}$.
Putting all this together we obtain

$\hat{{\underline{\mathbf{H}}}}_{x_{f(k+1)}}Y=\hat{{\underline{\mathbf{H}}}}_{x_{f(k+2)}}+\hat{{\underline{\mathbf{H}}}}_{x_{f(k)}}+{\underline{\mathbf{H}}}_{s_{1}\theta^{\prime}(k-1,0)t^{\prime}_{k-1}}+{\underline{\mathbf{H}}}_{\theta(k,0)t_{k}}+{\underline{\mathbf{H}}}_{\theta(k-2,0)t_{k-2}}+{\underline{\mathbf{H}}}_{s_{1}s_{2}s_{0}\theta(k-1,0)t_{k-1}},$
(5.6)

as we wanted to show. ∎

######  Theorem 5.3.

For all $k\geq 2$ we have
${\underline{\mathbf{H}}}_{x_{f(k)}}=\hat{{\underline{\mathbf{H}}}}_{x_{f(k)}}$.

###### Proof.

For $k=2$ the result follows by a direct computation. We now fix some $k\geq
2$ and assume the theorem holds for all $2\leq k^{\prime}\leq k$. We notice
that $G_{x_{f(k+1)}}(\hat{{\underline{\mathbf{H}}}}_{x_{f(k+1)}})=1$ and
$G_{z}(\hat{{\underline{\mathbf{H}}}}_{x_{f(k+1)}})\in v\mathbb{N}[v]$, for
all $z<x_{f(k+1)}$. Thus we only need to show that
$\hat{{\underline{\mathbf{H}}}}_{x_{f(k+1)}}$ is self-dual. This is an
immediate consequence of Lemma 5.2 and our inductive hypothesis. ∎

######  Theorem 5.4.

Let $k\geq 2$. We have

${\underline{\mathbf{H}}}_{x_{3k+1}}{\underline{\mathbf{H}}}_{s_{2}}={\underline{\mathbf{H}}}_{x_{3k+2}}.$
(5.7)
${\underline{\mathbf{H}}}_{x_{3k+2}}{\underline{\mathbf{H}}}_{s_{0}}=\left\\{\begin{array}[]{ll}{\underline{\mathbf{H}}}_{\overline{x}_{3k+3}}+{\underline{\mathbf{H}}}_{x_{3k+1}}+{\underline{\mathbf{H}}}_{\theta(k-1,0)}+{\underline{\mathbf{H}}}_{s_{1}\theta^{\prime}(k-2,0)}+{\underline{\mathbf{H}}}_{\theta(k-3,0)},&\mbox{if
}k\mbox{ is even;}\\\
{\underline{\mathbf{H}}}_{x_{3k+3}}+{\underline{\mathbf{H}}}_{x_{3k+1}}+{\underline{\mathbf{H}}}_{s_{1}s_{2}s_{0}\theta(k-2,0)},&\mbox{if
}k\mbox{ is odd.}\end{array}\right.$ (5.8)
${\underline{\mathbf{H}}}_{x_{3k+2}}{\underline{\mathbf{H}}}_{s_{1}}=\left\\{\begin{array}[]{ll}{\underline{\mathbf{H}}}_{x_{3k+3}}+{\underline{\mathbf{H}}}_{x_{3k+1}}+{\underline{\mathbf{H}}}_{s_{1}s_{2}s_{0}\theta(k-2,0)},&\mbox{if
}k\mbox{ is even;}\\\
{\underline{\mathbf{H}}}_{\overline{x}_{3k+3}}+{\underline{\mathbf{H}}}_{x_{3k+1}}+{\underline{\mathbf{H}}}_{\theta(k-1,0)}+{\underline{\mathbf{H}}}_{s_{1}\theta^{\prime}(k-2,0)}+{\underline{\mathbf{H}}}_{\theta(k-3,0)},&\mbox{if
}k\mbox{ is odd.}\end{array}\right.$ (5.9)

###### Proof.

The claim can be checked directly for $k=2$. From now on we assume $k\geq 3$.
An inspection of the explicit formula for
${\underline{\mathbf{H}}}_{x_{3k+1}}$ provided in Definition 5.1 allows us to
conclude that $xs_{2}>x$ for all $x\in W$ such that $\mu(x,x_{3k+1})\neq 0$.
Thus the sum in (3.3) is empty and (5.7) follows.

We now prove (5.8). We first treat the case $k$ even. Equation (3.4), Lemma
5.2 and Theorem 5.3 imply

$\begin{array}[]{rl}{\underline{\mathbf{H}}}_{x_{3k+1}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{1}}=&(v+v^{-1}){\underline{\mathbf{H}}}_{x_{3k+1}}+{\underline{\mathbf{H}}}_{x_{3k+4}}+{\underline{\mathbf{H}}}_{x_{3k-2}}+\\\
&\\\
&{\underline{\mathbf{H}}}_{s_{1}\theta^{\prime}(k-2,0)s_{1}}+{\underline{\mathbf{H}}}_{\theta(k-1,0)s_{1}}+{\underline{\mathbf{H}}}_{\theta(k-3,0)s_{1}}+{\underline{\mathbf{H}}}_{s_{1}s_{2}s_{0}\theta(k-2,0)s_{0}}.\end{array}$
(5.10)

On the other hand, we can combine (3.10), (5.1) and (5.7) to obtain

$\displaystyle h_{s_{1}\theta^{\prime}(k-2,0),x_{3k+2}}(v)$
$\displaystyle=v^{-1}h_{s_{1}\theta^{\prime}(k-2,0),x_{3k+1}}(v)+h_{e_{3(k-1)},x_{3k+1}}(v)$
(5.11) $\displaystyle=v^{-1}(v^{2})+v^{3}$ (5.12) $\displaystyle=v+v^{3}$
(5.13) $\displaystyle h_{\theta(k-3,0),x_{3k+2}}(v)$
$\displaystyle=v^{-1}h_{\theta(k-3,0),x_{3k+1}}(v)+h_{x_{3(k-2)},x_{3k+1}}(v)$
(5.14) $\displaystyle=v^{-1}(v^{6}+v^{4}+v^{2})+(v^{7}+v^{5}+2v^{3})$ (5.15)
$\displaystyle=v+3v^{3}+2v^{5}+v^{7}.$ (5.16)

From this we conclude that

$\mu(s_{1}\theta^{\prime}(k-2,0),x_{3k+2})=\mu(\theta(k-3,0),x_{3k+2})=1.$
(5.17)

We have the following equalities

$\displaystyle{\underline{\mathbf{H}}}_{x_{3k+1}}{\underline{\mathbf{H}}}_{s_{2}}{\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{1}}=$
$\displaystyle{\underline{\mathbf{H}}}_{x_{3k+2}}{\underline{\mathbf{H}}}_{s_{0}}{\underline{\mathbf{H}}}_{s_{1}}$
(5.18) $\displaystyle=$
$\displaystyle\left({\underline{\mathbf{H}}}_{\overline{x}_{3k+3}}+{\underline{\mathbf{H}}}_{x_{3k+1}}+{\underline{\mathbf{H}}}_{\theta(k-1,0)}+{\underline{\mathbf{H}}}_{s_{1}\theta^{\prime}(k-2,0)}+{\underline{\mathbf{H}}}_{\theta(k-3,0)}\displaystyle+\sum_{y\in
Y}m_{y}{\underline{\mathbf{H}}}_{y}\right){\underline{\mathbf{H}}}_{s_{1}}$
(5.19) $\displaystyle=$
$\displaystyle\left({\underline{\mathbf{H}}}_{{x}_{3k+4}}+{\underline{\mathbf{H}}}_{s_{1}s_{2}s_{0}\theta(k-2,0)s_{0}}+\displaystyle\sum_{z\in
Z}n_{z}{\underline{\mathbf{H}}}_{z}\right)+(v+v^{-1}){\underline{\mathbf{H}}}_{x_{3k+1}}+$
(5.20)
$\displaystyle{\underline{\mathbf{H}}}_{\theta(k-1,0)s_{1}}+{\underline{\mathbf{H}}}_{s_{1}\theta^{\prime}(k-2,0)s_{1}}+{\underline{\mathbf{H}}}_{\theta(k-3,0)s_{1}}\displaystyle+\sum_{y\in
Y}m_{y}{\underline{\mathbf{H}}}_{ys_{1}}.$ (5.21)

where $m_{y},n_{z}\in\mathbb{N}$, $Z=\\{z\in W\mid
D_{R}(y)=\\{s_{0},s_{1}\\}\\}$ and

$Y=\\{y\in W\mid
D_{R}(y)=\\{s_{0},s_{2}\\}\\}\setminus\\{s_{1}\theta^{\prime}(k-2,0),\theta(k-3,0)\\}.$
(5.22)

Let us explain how to obtain the above equalities. The first equality is a
direct consequence of (5.7). For the second one we use (3.3); first consider
the elements in $\lessdot x_{3k+2}$ satisfying $ws_{0}<w$. Lemma 2.13 together
with an easy case analysis show that these elements are $x_{3k+1}$ and
$\theta(k-1,0)$. This justifies the occurrence of the terms
${\underline{\mathbf{H}}}_{x_{3k+1}}$ and
${\underline{\mathbf{H}}}_{\theta(k-1,0)}$. On the other hand, (5.17) explains
the occurrence of the terms
${\underline{\mathbf{H}}}_{s_{1}\theta^{\prime}(k-2,0)}$ and
${\underline{\mathbf{H}}}_{\theta(k-3,0)}$. Finally, the equality
$D_{R}(x_{3k+2})=\\{s_{2}\\}$ allows us to conclude, via Lemma 3.6, that any
other term occurring must have right descent set equal to $\\{s_{0},s_{2}\\}$.
This explains the appearance of the sum. We remark that
$D_{R}(s_{1}\theta^{\prime}(k-2,0))=D_{R}(\theta(k-3,0))=\\{s_{0},s_{2}\\}$ as
well (for $k$ even). However the elements $s_{1}\theta^{\prime}(k-2,0)$ and
$\theta(k-3,0)$ were already considered, which explains the somewhat strange
definition of $Y$.

For the last equality, the terms inside the parentheses are justified applying