Unipotent Hecke algebras: the structure, representation theory, and combinatorics

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au

Last updated: 26 March 2015

This is an excerpt of the PhD thesis Unipotent Hecke algebras: the structure, representation theory, and combinatorics by F. Nathaniel Edgar Thiem.

A basis with multiplication in the $G={GL}_n\left({𝔽}_q\right)$ case

Unipotent Hecke algebras

The group ${GL}_n\left({𝔽}_q\right)$

Let $G={GL}_n\left({𝔽}_q\right)$ be the general linear group over the finite field ${𝔽}_q$ with $q$ elements. Define the subgroups $$\begin{array}{cc}{\displaystyle \begin{array}{c}T=\left\{\text{diagonal matrices}\right\},N=\left\{\text{monomial matrices}\right\},\\ W=\left\{\text{permutation matrices}\right\},\text{and}U=\left\{\left(\begin{array}{ccc}1& & *\\ & \ddots & \\ 0& & 1\end{array}\right)\right\},\end{array}}& \text{(4.1)}\end{array}$$ where a monomial matrix is a matrix with exactly one nonzero entry in each row and column $\text{(}N=WT\text{).}$ If necessary, specify the size of the matrices by a subscript such as $G_n,U_n,W_n,$ etc. If $a\in G_m$ and $b\in G_n$ are matrices, then let $a\oplus b\in G_{m+n}$ be the block diagonal matrix $$a\oplus b=\left(\begin{array}{cc}a& 0\\ 0& b\end{array}\right)\text{.}$$

Let $x_{ij}\left(t\right)\in U$ be the matrix with $t$ in position $(i,j),$ ones on the diagonal and zeroes elsewhere; write $x_i\left(t\right)=x_{i,i+1}\left(t\right)\text{.}$ Let $h_{{\epsilon }_i}\left(t\right)\in T$ denote the diagonal matrix with $t$ in the $i\text{th}$ slot and ones elsewhere, and let $s_i\in W\subseteq N$ be the identity matrix with the $i\text{th}$ and $(i+1)\text{st}$ columns interchanged. That is, $$\begin{array}{cc}{\displaystyle \begin{array}{rcl}{\displaystyle x_i\left(t\right)}& =& {\displaystyle {\text{Id}}_{i-1}\oplus \left(\begin{array}{cc}1& t\\ 0& 1\end{array}\right)\oplus {\text{Id}}_{n-i-1},}\\ {\displaystyle h_{{\epsilon }_i}\left(t\right)}& =& {\displaystyle {\text{Id}}_{i-1}\oplus \left(t\right)\oplus {\text{Id}}_{n-i},}\\ {\displaystyle s_i}& =& {\displaystyle {\text{Id}}_{i-1}\oplus \left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)\oplus {\text{Id}}_{n-i-1},}\end{array}}& \text{(4.2)}\end{array}$$ where ${\text{Id}}_k$ is the $k\times k$ identity matrix. Then $$\begin{array}{cc}{\displaystyle \begin{array}{c}W=⟨s_1,s_2,\dots ,s_{n-1}⟩,T=⟨h_{{\epsilon }_i}\left(t\right)\hspace{0.17em}|\hspace{0.17em}1\le i\le n,t\in {𝔽}_q^{*}⟩,N=WT,\\ U=⟨x_{ij}\left(t\right)\hspace{0.17em}|\hspace{0.17em}1\le i<j\le n,t\in {𝔽}_q⟩,G=⟨U,W,T⟩\text{.}\end{array}}& \text{(4.3)}\end{array}$$ The Chevalley group relations for $G$ are (see also Section 3.3.1) $$\begin{array}{rcll}{\displaystyle x_{ij}\left(a\right)x_{rs}\left(b\right)}& =& {\displaystyle x_{ij}\left(b\right)x_{rs}\left(a\right)x_{is}\left({\delta }_{jr}ab\right)x_{rj}(-{\delta }_{is}ab),(i,j)\ne (r,s),}& \text{(U1)}\\ {\displaystyle x_{ij}\left(a\right)x_{ij}\left(b\right)}& =& {\displaystyle x_{ij}(a+b),}& \text{(U2)}\\ {\displaystyle s_i^2}& =& {\displaystyle 1,}& \text{(N1)}\\ {\displaystyle s_i{s}_{i+1}{s}_i}& =& {\displaystyle s_{i+1}{s}_i{s}_{i+1}\text{and}{s}_i{s}_j=s_j{s}_i,\mid i-j\mid >1,}& \text{(N2)}\\ {\displaystyle h_{{\epsilon }_i}\left(b\right)h_{{\epsilon }_i}\left(a\right)}& =& {\displaystyle h_{{\epsilon }_i}\left(ab\right),}& \text{(N4)}\\ {\displaystyle h_{{\epsilon }_j}\left(b\right)h_{{\epsilon }_i}\left(a\right)}& =& {\displaystyle h_{{\epsilon }_j}\left(b\right)h_{{\epsilon }_i}\left(a\right),}& \text{(N5)}\\ {\displaystyle s_r{x}_{ij}\left(t\right)}& =& {\displaystyle x_{s_r\left(i\right)s_r\left(j\right)}\left(t\right)s_r,}& \text{(UN1)}\\ {\displaystyle x_{ij}\left(a\right)h_{{\epsilon }_r}\left(t\right)}& =& {\displaystyle h_{{\epsilon }_r}\left(t\right)x_{ij}\left(t^{-{\delta }_{ri}}{t}^{{\delta }_{rj}}a\right),}& \text{(UN2)}\\ {\displaystyle s_i{x}_i\left(t\right)s_i}& =& {\displaystyle x_i\left(t^{-1}\right)s_i{x}_i(-t)h_{{\epsilon }_i}\left(t\right)h_{{\epsilon }_{i+1}}(-t^{-1}),t\ne 0,}& \text{(UN3)}\end{array}$$ where ${\delta }_{ij}$ is the Kronecker delta.

A pictorial version of ${GL}_n\left({𝔽}_q\right)$

For the results that follow, it will be useful to view these elements of $ℂG$ as braid-like diagrams instead of matrices. Consider the following depictions of elements by diagrams with vertices, strands between the vertices, and various objects that slide around on the strands. View $$\begin{array}{rcll}{\displaystyle s_i}& \text{as}& {\displaystyle \begin{array}{c} ⋯ ⋯ i \end{array},}& \text{(4.4)}\\ {\displaystyle h_{{\epsilon }_i}\left(t\right)}& \text{as}& {\displaystyle \begin{array}{c} ⋯ ⋯ 1 1 t 1 1 i \end{array},}& \text{(4.5)}\\ {\displaystyle x_{ij}\left(ab\right)}& \text{as}& {\displaystyle \begin{array}{c} ⋯ ⋯ ⋯ a∘→ b←∘ i j \end{array},}& \text{(4.6)}\end{array}$$ where each diagram has two rows of $n$ vertices. Multiplication in $G$ corresponds to the concatenation of two diagrams; for example, $s_2{s}_1$ is $$s_2{s}_1=\begin{array}{c} s1 s2 \end{array}=\begin{array}{c} \end{array}=\begin{array}{c} \end{array}\text{.}$$ In the following Chevalley relations, curved strands indicate longer strands, so for example (UN1) indicates that $\overrightarrow{\underset{\circ }{a}}$ and $\underleftarrow{\stackrel{\circ }{b}}$ slide along the strands they are on (no matter how long). The Chevalley relations are $$\begin{array}{cc}{\displaystyle \begin{array}{c} a∘→ a∘→ 1←∘ b←∘ \end{array}=\begin{array}{c} a∘→ a∘→ a∘→ 1←∘ b←∘ b←∘ \end{array}}& \text{(U1)}\\ {\displaystyle \begin{array}{c} 1∘→ 1∘→ a←∘ b←∘ \end{array}=\begin{array}{c} 1∘→ a+b←∘ \end{array}}& \text{(U2)}\\ {\displaystyle \begin{array}{c} \end{array}=\begin{array}{c} \end{array}}& \text{(N1)}\\ {\displaystyle \begin{array}{c} \end{array}=\begin{array}{c} \end{array}\text{and}\begin{array}{c} \end{array}=\begin{array}{c} \end{array}}& \text{(N2)}\\ {\displaystyle \begin{array}{c} a b \end{array}=\begin{array}{c} ab \end{array}}& \text{(N4)}\\ {\displaystyle \begin{array}{c} a b \end{array}=\begin{array}{c} a b \end{array}}& \text{(N5)}\\ {\displaystyle \begin{array}{c} a∘→ b←∘ \end{array}=\begin{array}{c} a∘→ b←∘ \end{array}}& \text{(UN1)}\\ {\displaystyle \begin{array}{c} a∘→ b←∘ r s \end{array}=\begin{array}{c} ar-1∘‾ bs←∘ r s \end{array}}& \text{(UN2)}\\ {\displaystyle \begin{array}{c} a∘→ b←∘ \end{array}=\begin{array}{c} b∘→ -a←∘ b-1∘→ a-1←∘ ab -(ab)-1 \end{array}ab\ne 0\text{.}}& \text{(UN3)}\end{array}$$

The unipotent Hecke algebra ${\mathscr{H}}_{\mu }$

Fix a nontrivial group homomorphism $\psi :{𝔽}_q^{+}\to {ℂ}^{*},$ and a map $$\begin{array}{cc}{\displaystyle \begin{array}{cccc}\mu :& \left\{(i,j)\hspace{0.17em}\right|\hspace{0.17em}1\le i<j\le n\}& ⟶& {𝔽}_q\\ & (i,j)& ⟼& {\mu }_{ij}\end{array}\text{with}\hspace{0.17em}{\mu }_{ij}=0\hspace{0.17em}\text{for}\hspace{0.17em}j\ne i+1\text{.}}& \text{(4.7)}\end{array}$$ Then $$\begin{array}{cc}{\displaystyle \begin{array}{cccc}{\psi }_{\mu }:& U& ⟶& {ℂ}^{*}\\ & x_{ij}\left(t\right)& ⟼& \psi \left({\mu }_{ij}t\right)\end{array}}& \text{(4.8)}\end{array}$$ is a group homomorphism. Since ${\mu }_{ij}=0$ for all $j\ne i+1,$ write $$\begin{array}{cc}{\displaystyle \mu =({\mu }_{\left(1\right)},{\mu }_{\left(2\right)},\dots ,{\mu }_{(n-1)},{\mu }_{\left(n\right)}),\text{where}\hspace{0.17em}{\mu }_{\left(i\right)}={\mu }_{i,i+1}\hspace{0.17em}\text{and}\hspace{0.17em}{\mu }_{\left(n\right)}=0\text{.}}& \text{(4.7)}\end{array}$$

The unipotent Hecke algebra ${\mathscr{H}}_{\mu }$ of the triple $(G,U,{\psi }_{\mu })$ is $$\begin{array}{cc}{\displaystyle {\mathscr{H}}_{\mu }={\text{End}}_G\left({\text{Ind}}_U^G\left({\psi }_{\mu }\right)\right)\cong e_{\mu }ℂG{e}_{\mu },\text{where}{e}_{\mu }=\frac{1}{\mid U\mid }\sum _{u\in U}{\psi }_{\mu }\left(u^{-1}\right)u\text{.}}& \text{(4.9)}\end{array}$$

The type of a linear character ${\psi }_{\mu }:U\to {ℂ}^{*}$ is the composition $\nu$ such that $${\mu }_{\left(i\right)}=0\text{if and only if}i\in {\nu }_{\le }\text{(with}\hspace{0.17em}{\nu }_{\le }\hspace{0.17em}\text{as in Section 2.3.2).}$$

Let $\nu$ be a composition. Suppose $\chi$ and $\chi \prime$ are two type $\nu$ linear characters of $U\text{.}$ Then $$\mathscr{H}(G,U,\chi )\cong \mathscr{H}(G,U,\chi \prime )\text{.}$$

Proposition 4.1 implies that given any fixed character $\psi :{𝔽}_q^{+}\to {ℂ}^{*},$ it suffices to specify the type of the linear character ${\psi }_{\mu }\text{.}$ Note that the map (given by example) $$\begin{array}{cc}{\displaystyle \begin{array}{ccc}\left\{\begin{array}{c}\text{Compositions}\\ \mu =({\mu }_1,{\mu }_2,\dots ,{\mu }_{\ell })\models n\end{array}\right\}& ⟷& \left\{\begin{array}{c}\mu =({\mu }_{\left(1\right)},{\mu }_{\left(2\right)},\dots ,{\mu }_{\left(n\right)})\\ {\mu }_{\left(i\right)}\in \{0,1\}\hspace{0.17em}\text{and}\hspace{0.17em}{\mu }_{\left(n\right)}=0\end{array}\right\}\\ \mu =\begin{array}{c} 1 0 1 1 1 1 0 1 1 0 1 1 1 0 \end{array}& ⟷& (1,0,1,1,1,1,0,1,1,0,1,1,1,0)\end{array}}& \text{(4.10)}\end{array}$$ is a bijection. In the following sections identify the compositions $\mu =({\mu }_1,\dots ,{\mu }_{\ell })$ with the map $\mu =({\mu }_{\left(1\right)},\dots ,{\mu }_{\left(n\right)})$ using this bijection.

The classical examples of unipotent Hecke algebras are the Yokonuma algebra ${\mathscr{H}}_{\left(1^n\right)}$ [Yok1969-2] and the Gelfand-Graev Hecke algebra ${\mathscr{H}}_{\left(n\right)}$ [Ste1967].

An indexing for the standard basis of ${\mathscr{H}}_{\mu }$

The group $G$ has a double-coset decomposition $G=\underset{v\in N}{⨆}UvU,$ so if $$\begin{array}{cc}{\displaystyle \begin{array}{rcl}{\displaystyle N_{\mu }}& =& {\displaystyle \{v\in N\hspace{0.17em}|\hspace{0.17em}{e}_{\mu }v{e}_{\mu }\ne 0\}}\\ & =& {\displaystyle \{v\in N\hspace{0.17em}|\hspace{0.17em}u,vu{v}^{-1}\in U\hspace{0.17em}\text{implies}\hspace{0.17em}{\psi }_{\mu }\left(u\right)={\psi }_{\mu }\left(vu{v}^{-1}\right)\}}\end{array}}& \text{(4.11)}\end{array}$$ then the isomorphism in (4.9) implies that the set $\left\{e_{\mu }v{e}_{\mu }\hspace{0.17em}\right|\hspace{0.17em}v\in N_{\mu }\}$ is a basis for ${\mathscr{H}}_{\mu }$ [CRe1981, Prop. 11.30].

Suppose $a\in M_{\ell }\left({𝔽}_q\left[X\right]\right)$ is an $\ell \times \ell$ matrix with polynomial entries. Let $d\left(a_{ij}\right)$ be the degree of the polynomial $a_{ij}\text{.}$ Define the degree row sums and the degree column sums of $a$ to be the compositions $$d^{\to }\left(a\right)=(d^{\to }{\left(a\right)}_1,d^{\to }{\left(a\right)}_2,\dots ,d^{\to }{\left(a\right)}_{\ell })\text{and}{d}^{\downarrow }\left(a\right)=(d^{\downarrow }{\left(a\right)}_1,d^{\downarrow }{\left(a\right)}_2,\dots ,d^{\downarrow }{\left(a\right)}_{\ell }),$$ where $$d^{\to }{\left(a\right)}_i=\sum _{j=1}^{\ell }d\left(a_{ij}\right)\text{and}{d}^{\downarrow }{\left(a\right)}_j=\sum _{i=1}^{\ell }d\left(a_{ij}\right)\text{.}$$ Let $$\begin{array}{cc}{\displaystyle M_{\mu }=\{a\in M_{\ell \left(\mu \right)}\left({𝔽}_q\left[X\right]\right)\hspace{0.17em}|\hspace{0.17em}{d}^{\to }\left(a\right)=d^{\downarrow }\left(a\right)=\mu ,a_{ij}\hspace{0.17em}\text{monic,}\hspace{0.17em}{a}_{ij}\left(0\right)\ne 0\}\text{.}}& \text{(4.12)}\end{array}$$ For example, $$\begin{array}{cc}{\displaystyle \begin{array}{ccccccc}(& X+1& 1& 1& X+2& )& (1+0+0+1=2)\\ X+3& X^3+2X+3& 1& X+2& (1+3+0+1=5)\\ 1& X^2+4X+2& X+2& 1& (0+2+1+0=3)\\ 1& 1& X^2+3X+1& X^2+2& (0+0+2+2=4)\\ & (1+1+0+0=2)& (0+3+2+0=5)& (0+0+1+2=3)& (1+1+0+2=4)\end{array}\in M_{(2,5,3,4)}\text{.}}& (*)\end{array}$$

Suppose $\left(f\right)=(a_0+a_1{X}^{i_1}+a_2{X}^{i_2}+\cdots +a_r{X}^{i_r}+X^n)\in M_{\left(n\right)}$ is a $1\times 1$ matrix with $a_0,a_1,\dots ,a_r\ne 0\text{.}$ Let $$\begin{array}{cc}{\displaystyle v_{\left(f\right)}=\begin{array}{c} (f) \end{array}=w_{\left(n\right)}(w_{\left(i_1\right)}{a}_0\oplus w_{(i_2-i_1)}{a}_1\oplus \cdots \oplus w_{(n-i_r)}{a}_r)\in N,}& \text{(4.13)}\end{array}$$ where $$w_{\left(k\right)}=\begin{array}{c} ⋯ ⋯ \end{array}\in W_k,$$ and by convention $v_{\left(1\right)}$ is the empty strand (not a strand). For example, $v_{(a+b{X}^3+c{X}^4+X^6)}$ is $$\begin{array}{c} (a+bX3+cX4+X6) \end{array}=\begin{array}{c} a a a b c c \end{array}=\begin{array}{c} a a a b c c \end{array}\text{.}$$

For each $a\in M_{\mu }$ define a matrix $v_a\in N$ pictorially by $$\begin{array}{cc}{\displaystyle v_a=\begin{array}{c} ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ (aℓ1) (a21) (a11) (aℓ2) (a22) (a12) (aℓℓ) (a2ℓ) (a1ℓ) \end{array},}& \text{(4.14)}\end{array}$$ where $a_{ij}$ is the $(i,j)\text{th}$ entry of $a,$ and the top vertex associated with $a_{ij}$ goes to the bottom vertex associated with $a_{ji}\text{.}$ Note that if $a_{ij}=1,$ then both its strand and corresponding vertices vanish. The fact that $a\in M_{\mu }$ guarantees that we are left with two rows of exactly $n$ vertices.

For example, if $a$ is as in $(*),$ then $v_a$ is $$\begin{array}{c}\begin{array}{c} (3+X) (1+X) (2+4X+X2) (3+2X+X3) (1+3X+X2) (2+X) (2+X2) (2+X) (2+X) \end{array}\\ =\begin{array}{c} [3] [1] [2 4] [3 2 2] [1 3] [2] [2 2] [2] [2] \end{array}\text{.}\end{array}$$

Viewed as a matrix, $$v_a=\begin{array}{c} ⏞ ⏞ ⏞ ⋯ μ1 columns μ2 columns μ3 columns } } } ⋮ μ1 rows μ2 rows μ3 rows ( v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) 0 v(a11) v(a11) ⋯ v(a11) v(a11) 0 v(a11) v(a11) 0 v(a11) v(a11) v(a13) v(a11) 0 v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) v(a12) v(a11) 0 v(a11) 0 v(a11) 0 v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) 0 v(a11) 0 v(a11) 0 v(a11) 0 v(a11) 0 v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) 0 v(a11) 0 v(a11) 0 v(a11) ⋯ v(a11) v(a11) 0 v(a11) 0 v(a11) 0 v(a11) v(a11) v(a23) 0 v(a11) 0 v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) v(a22) 0 0 0 0 v(a11) 0 v(a11) v(a11) v(a11) v(a21) 0 0 0 0 0 0 0 v(a11) 0 v(a11) v(a11) v(a11) v(a11) v(a11) 0 0 0 0 v(a11) 0 0 v(a11) ⋯ v(a11) 0 0 0 v(a11) v(a33) 0 0 v(a11) 0 v(a11) v(a11) v(a11) v(a11) v(a32) 0 0 0 0 0 0 v(a11) 0 v(a11) v(a11) v(a31) 0 0 0 0 0 0 0 0 0 0 v(a11) 0 v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) ⋮ 0 0 0 ⋮ 0 0 0 ⋮ 0 0 0 v(a11) ⋱ v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) v(a11) ) \end{array}$$

Let $N_{\mu }$ be as in (4.11) and $M_{\mu }$ be as in (4.12). The map $$\begin{array}{ccc}{M}_{\mu }& ⟶& N_{\mu }\\ a& ⟼& v_a,\end{array}$$ given by (4.14) is a bijection.

Remark. When $\mu =\left(n\right)$ this theorem says that the map $\left(f\right)\mapsto v_{\left(f\right)}$ of (4.13) is a bijection between $M_{\left(n\right)}$ and $N_{\left(n\right)}\text{.}$

Remark. This bijection will prove useful in developing a generalization of the RSK correspondence in Chapter 5.

Let $$m_{\mu }=\{a\in M_{\ell }\left({\mathbb{Z}}_{\ge 0}\right)\hspace{0.17em}|\hspace{0.17em}\text{row-sums and column-sums are}\hspace{0.17em}\mu \}$$ and for $a\in m_{\mu },$ let $$\ell \left(a\right)=\text{Card}\{a_{ij}\ne 0\hspace{0.17em}|\hspace{0.17em}1\le i,j\le \ell \}\text{.}$$

Let $\mu \models n\text{.}$ Then $$\text{dim}\left({\mathscr{H}}_{\mu }\right)=\sum _{a\in m_{\mu }}{(q-1)}^{\ell \left(a\right)}{q}^{n-\ell \left(a\right)}$$

Multiplication in ${\mathscr{H}}_{\mu }$

This section examines the implications of the unipotent Hecke algebra multiplication relations from Chapter 3 in the case $G={GL}_n\left({𝔽}_q\right)\text{.}$ The final goal is the algorithm given in Theorem 4.5.

Pictorial versions of $e_{\mu }v{e}_{\mu }$

Note that the map $$\begin{array}{cc}{\displaystyle \begin{array}{cccccc}\pi :& N& =& WT& ⟶& W\\ & & & wh& ⟼& w,& \text{for}\hspace{0.17em}w\in W,h\in T,\hfill \end{array}}& \text{(4.15)}\end{array}$$ is a surjective group homomorphism. Since $W\subseteq N,$ adjust the decomposition of (3.4) as follows. Let $u\in N$ with $\pi \left(u\right)=s_{i_1}\cdots s_{i_r}$ for $r$ minimal. Then $u$ has a unique decomposition $$\begin{array}{cc}{\displaystyle u=u_1{u}_2\cdots u_r{u}_T,\text{where}\hspace{0.17em}{u}_k=s_{i_k},u_T\in T\text{.}}& \text{(4.16)}\end{array}$$ For $t\in {𝔽}_q,$ write $u_k\left(t\right)=s_{i_k}{x}_{i_k}\left(t\right)\text{.}$

Fix a composition $\mu \text{.}$ The decomposition $$U=\prod _{1\le i<j\le n}{U}_{ij}\text{where}{U}_{ij}=⟨x_{ij}\left(t\right)\hspace{0.17em}|\hspace{0.17em}t\in {𝔽}_q⟩,$$ implies $$\begin{array}{cc}{\displaystyle e_{\mu }=\prod _{1\le i<j\le n}{e}_{ij}\left(1\right),\text{where}{e}_{ij}\left(k\right)=\frac{1}{q}\prod _{t\in {𝔽}_q}\psi (-{\mu }_{ij}kt)x_{ij}\left(t\right)\text{.}}& \text{(4.17)}\end{array}$$

Pictorially, let $$\begin{array}{rcll}{\displaystyle u_k}& \text{as}& {\displaystyle \begin{array}{c} ⋯ ⋯ ik k \end{array},}& \text{(4.18)}\\ {\displaystyle u_k\left(t_k\right)}& \text{as}& {\displaystyle \begin{array}{c} ⋯ ⋯ ik k \end{array},}& \text{(4.19)}\\ {\displaystyle e_{ij}\left(k\right)}& \text{as}& {\displaystyle \begin{array}{c} ⋯ ⋯ ⋯ ⋯ i j k \end{array},}& \text{(4.20)}\\ {\displaystyle e_{\mu }}& \text{as}& {\displaystyle \begin{array}{c} ⋯ μ(1) μ(2) μ(n-1) \end{array}\text{.}}& \text{(4.21)}\end{array}$$

Examples: 1. If $u=u_1{u}_2\cdots u_8{u}_T\in N$ decomposes according to $s_3{s}_1{s}_2{s}_3{s}_1{s}_4{s}_2{s}_3\in W$ with $u_T=\text{diag}(a,b,c,d,e),$ then $$u=\begin{array}{c} a b c d e 1 2 3 4 5 6 7 8 \end{array},u_1\left(t_1\right)u_2\left(t_2\right)\cdots u_8\left(t_8\right)u_T=\begin{array}{c} a b c d e 1 2 3 4 5 6 7 8 \end{array}$$ and $$e_{\mu }u{e}_{\mu }=\begin{array}{c} a b c d e μ(1) μ(2) μ(3) μ(4) μ(1) μ(2) μ(3) μ(4) 1 2 3 4 5 6 7 8 \end{array}\text{.}$$ 2. If $n=5,$ then (4.17) implies $$\begin{array}{c} μ(1) μ(2) μ(3) μ(4) \end{array}=\begin{array}{c} 1 1 1 1 1 1 1 1 1 1 \end{array}$$ $\text{(}{e}_{\mu }=e_{45}\left(1\right)e_{35}\left(1\right)e_{34}\left(1\right)e_{25}\left(1\right)e_{24}\left(1\right)e_{23}\left(1\right)e_{15}\left(1\right)e_{14}\left(1\right)e_{13}\left(1\right)e_{12}\left(1\right)\text{).}$

The elements $e_{ij}\left(k\right)$ also interact with $U$ and $N$ as follows (see also Section 3.3.1) $$\begin{array}{rcll}{\displaystyle s_r{e}_{ij}\left(k\right)s_r}& =& {\displaystyle e_{s_r\left(i\right)s_r\left(j\right)}\left(k\right),}& \text{(E1)}\\ {\displaystyle e_{\mu }v{e}_{ij}\left(1\right)}& =& {\displaystyle e_{\mu }v,v\in N_{\mu },\left(\pi v\right)\left(i\right)<\left(\pi v\right)\left(j\right),}& \text{(E2)}\\ {\displaystyle e_{ij}\left(k\right)h_{{\epsilon }_r}\left(t\right)}& =& {\displaystyle h_{{\epsilon }_r}\left(t\right)e_{ij}\left(t^{{\delta }_{ri}}{t}^{-{\delta }_{rj}}k\right),}& \text{(E3)}\\ {\displaystyle e_{\mu }{x}_{ij}\left(t\right)}& =& {\displaystyle \psi \left({\mu }_{ij}t\right)e_{\mu }=x_{ij}\left(t\right)e_{\mu },}& \text{(E4)}\end{array}$$ or pictorially, $$\begin{array}{c} k \end{array}=\begin{array}{c} k \end{array}\text{(E1)}\begin{array}{c} k r s \end{array}=\begin{array}{c} krs-1 r s \end{array}\text{(E3)}\begin{array}{c} k a∘→ b←∘ \end{array}=\psi \left(kab\right)\begin{array}{c} k \end{array}\text{and}\begin{array}{c} k a∘→ b←∘ \end{array}=\psi \left(kab\right)\begin{array}{c} k \end{array}\text{(E4)}$$ and for $v\in N_{\mu },$ $$\begin{array}{cc}{\displaystyle \begin{array}{c} ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ 1 v μ(i) μ(j-1) \end{array}=\begin{array}{c} ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ v μ(i) μ(j-1) \end{array}}& \text{(E2)}\end{array}$$

Suppose $u=u_1{u}_2\cdots u_r{u}_T\in N_{\mu }$ with $u_T=\text{diag}(h_1,h_2,\dots ,h_n)\text{.}$ Then using (4.17), (E3), (E1) and (E2), we can rewrite $e_{\mu }u{e}_{\mu }$ as $$\begin{array}{cc}{\displaystyle \begin{array}{c} μ(1) μ(2) μ(3) ⋯ μ(n-1) h1 h2 h3 ⋯ hn u1u2⋯ur μ(1) μ(2) μ(3) ⋯ μ(n-1) \end{array}=\frac{1}{q^r}\sum _{t\in {𝔽}_q^r}(\psi \circ f_u)\left(t\right)\begin{array}{c} h1 h2 h3 ⋯ hn u1(t1)u2(t2)⋯ur(tr) μ(1) μ(2) μ(3) ⋯ μ(n-1) \end{array}}& \text{(4.22)}\end{array}$$ where $f_u\in {𝔽}_q[y_1,y_2,\dots ,y_r]$ is given by $$\begin{array}{cc}{\displaystyle f_u(y_1,y_2,\dots ,y_r)=-{\mu }_{i_1{j}_1}{h}_{i_1}{h}_{j_1}^{-1}{y}_1-{\mu }_{i_2{j}_2}{h}_{i_2}{h}_{j_2}^{-1}{y}_2-\cdots -{\mu }_{i_r{j}_r}{h}_{i_r}{h}_{j_r}^{-1}{y}_r,}& \text{(4.23)}\end{array}$$ for $(i_k,j_k)=(a,b),$ if the $k\text{th}$ crossing in $u$ crosses the strands coming from the $a\text{th}$ and $b\text{th}$ top vertices.

Example (continued). Suppose $u=u_1{u}_2\cdots u_8{u}_T\in N$ decomposes according to $s_3{s}_1{s}_2{s}_3{s}_1{s}_4{s}_2{s}_3\in W$ and $u_T=\text{diag}(a,b,c,d,e)\in T$ (as in Example 1 above). Consider the ordering $$e_{\mu }=\begin{array}{c} 1 1 1 1 1 1 1 1 1 1 \end{array},$$ or $e_{\mu }=e_{13}\left(1\right)e_{23}\left(1\right)e_{12}\left(1\right)e_{45}\left(1\right)e_{15}\left(1\right)e_{25}\left(1\right)e_{14}\left(1\right)e_{35}\left(1\right)e_{24}\left(1\right)e_{34}\left(1\right)\text{.}$ Then $$\begin{array}{rcl}{\displaystyle e_{\mu }u{e}_{\mu }}& =& {\displaystyle e_{\mu }u\underleftarrow{e_{13}\left(1\right)e_{23}\left(1\right)}{e}_{12}\left(1\right)e_{45}\left(1\right)e_{15}\left(1\right)e_{25}\left(1\right)e_{14}\left(1\right)e_{35}\left(1\right)e_{24}\left(1\right)e_{34}\left(1\right)}\\ & =& {\displaystyle e_{\mu }u{e}_{12}\left(1\right)e_{45}\left(1\right)e_{15}\left(1\right)e_{25}\left(1\right)e_{14}\left(1\right)e_{35}\left(1\right)e_{24}\left(1\right)e_{34}\left(1\right)\text{(by (E2))}}\\ & =& {\displaystyle e_{\mu }{u}_1{u}_2\cdots u_8{u}_T\underleftarrow{e_{12}\left(1\right)e_{45}\left(1\right)e_{15}\left(1\right)e_{25}\left(1\right)e_{14}\left(1\right)e_{35}\left(1\right)e_{24}\left(1\right)e_{34}\left(1\right)}}\\ & =& {\displaystyle e_{\mu }{u}_1{u}_2\cdots u_8\underleftarrow{e_{12}\left(\frac{a}{b}\right)e_{45}\left(\frac{d}{e}\right)e_{15}\left(\frac{a}{e}\right)e_{25}\left(\frac{b}{e}\right)e_{14}\left(\frac{a}{d}\right)e_{35}\left(\frac{c}{e}\right)e_{24}\left(\frac{b}{d}\right)e_{34}\left(\frac{c}{d}\right)}{U}_T\text{(by (E3))}}\\ & =& {\displaystyle e_{\mu }{u}_1{e}_{34}\left(\frac{a}{b}\right)u_2{e}_{12}\left(\frac{d}{e}\right)u_3{e}_{23}\left(\frac{a}{e}\right)u_4{e}_{34}\left(\frac{b}{e}\right)u_5{e}_{12}\left(\frac{a}{d}\right)u_6{e}_{45}\left(\frac{c}{e}\right)u_7{e}_{23}\left(\frac{b}{d}\right)u_8{e}_{34}\left(\frac{c}{d}\right)u_T\text{(by (E1))}}\\ & =& {\displaystyle \frac{e_{\mu }}{q^8}\sum _{t\in {𝔽}_q^8}(\psi \circ f)\left(t\right)u_1{x}_{34}\left(\frac{a}{b}{t}_1\right)u_2{x}_{12}\left(\frac{d}{e}{t}_2\right)u_3{x}_{23}\left(\frac{a}{e}{t}_3\right)\cdots u_8{x}_{34}\left(\frac{c}{d}{t}_8\right)u_T,}\end{array}$$ where by (4.17), $f=-y_1-y_2-y_8\text{.}$ Therefore, by renormalizing $$\begin{array}{rcl}{\displaystyle e_{\mu }u{e}_{\mu }}& =& {\displaystyle \frac{e_{\mu }}{q^8}\sum _{t\prime \in {𝔽}_q^8}(\psi \circ f_u)\left(t\prime \right)u_1{x}_{34}\left(t_1\right)u_2{x}_{12}\left(t_2\right)u_3{x}_{23}\left(t_3\right)\cdots u_8{x}_{34}\left(t_8\right)u_T}\\ & =& {\displaystyle \frac{e_{\mu }}{q^8}\sum _{t\prime \in {𝔽}_q^8}(\psi \circ f_u)\left(t\prime \right)u_1\left(t_1\right)u_2\left(t_2\right)u_3\left(t_3\right)\cdots u_8\left(t_8\right)u_T,}\end{array}$$ where $f_u=-b{a}^{-1}{y}_1-e{d}^{-1}{y}_2-d{c}^{-1}{y}_8\text{.}$ Pictorially, by sliding the $e_{ij}\left(1\right)$ down along the strands until they get stuck, this computation gives $$\begin{array}{cc}{\displaystyle e_{\mu }u{e}_{\mu }=\begin{array}{c} a b c d e μ(1) μ(2) μ(3) μ(4) μ(1) μ(2) μ(3) μ(4) 1 2 3 4 5 6 7 8 \end{array}=\frac{1}{q^8}\sum _{t\in {𝔽}_q^8}(\psi \circ f_u)\left(t\right)\begin{array}{c} a b c d e μ(1) μ(2) μ(3) μ(4) 1 2 3 4 5 6 7 8 \end{array}}& \text{(4.24)}\end{array}$$ where $f_u=-b{a}^{-1}{y}_1-e{d}^{-1}{y}_2-d{c}^{-1}{y}_8$ (as in (4.23)), since $(i_1,j_1)=(1,2),$ $(i_2,j_2)=(4,5),$ $(i_3,j_3)=(1,5),$ etc.

Relations for multiplying basis elements.

Let $u=u_1{u}_2\cdots u_r{u}_T\in N_{\mu }$ decompose according to a minimal expression in $W$ as in (4.16). Let $v\in N_{\mu }$ and use (N3) and (N4) to write $u_{T}v=w·\text{diag}(a_1,a_2,\cdots ,a_n)$ for some $w=\pi \left(v\right)\in W$ (see (4.7)). Then use (4.22) to write $$\begin{array}{cc}{\displaystyle \left(e_{\mu }u{e}_{\mu }\right)\left(e_{\mu }v{e}_{\mu }\right)=\frac{1}{q^r}\sum _{t\in {𝔽}_q^r}(𝓅\circ f_u)\left(t\right)\begin{array}{c} μ(1) μ(2) μ(3) ⋯ μ(n-1) a1 a2 a3 an w u1(t1)u2(t2)⋯ur(tr) μ(1) μ(2) μ(3) ⋯ μ(n-1) \end{array}}& \text{(4.25)}\end{array}$$ (This form corresponds to ${\mathrm{\Xi }}^{\varnothing }(u,u_{T}v)$ of Corollary 3.9).

Example (continued). If $u$ is as in (4.24) and $v=s_2{s}_3{s}_2{s}_1{s}_2·\text{diag}(f,g,h,i,j)\in N,$ then $$\left(e_{\mu }u{e}_{\mu }v{e}_{\mu }\right)=\frac{1}{q^8}\sum _{t\in {𝔽}_q^8}(\psi \circ f_u)\left(t\right)\begin{array}{c} fd gc ah bi ej μ(1) μ(2) μ(3) μ(4) μ(1) μ(2) μ(3) μ(4) 1 2 3 4 5 6 7 8 \end{array}\text{.}$$

Consider the crossing in (4.25) corresponding to $u_r\left(t_r\right)\text{.}$ There are two possibilities.

Case 1 the strands that cross at $\overline{)r}$ do not cross again as they go up to the top of the diagram $\text{(}\ell \left(u_{r}w\right)>\ell \left(w\right)\text{),}$

Case 2 the strands that cross at $\overline{)r}$ cross once on the way up to the top of the diagram $\text{(}\left(u_{r}w\right)<\ell \left(w\right)\text{).}$

In the first case, $$e_{\mu }u{e}_{\mu }v{e}_{\mu }=\frac{1}{q_r}\sum _{t\in {𝔽}_q^r}(\psi \circ f_u)\left(t\right)\begin{array}{c} r ⋯ μ(i) ⋯ μ(j-1) ⋯ a1 ai aj an w u1(t1)⋯ur-1(tr-1) μ(1) μ(2) μ(3) ⋯ μ(n-1) \end{array},$$ so (UN1), (UN2) and (E4) imply $$\begin{array}{cc}{\displaystyle e_{\mu }u{e}_{\mu }v{e}_{\mu }=\frac{1}{q^r}\sum _{t\in {𝔽}_q^r}(\psi \circ f^{(+0)})\left(t\right)\begin{array}{c} μ(1) μ(2) μ(3) ⋯ μ(n-1) a1 a2 a3 an urw u1(t1)⋯ur(tr) μ(1) μ(2) μ(3) ⋯ μ(n-1) \end{array}}& \text{(4.26)}\end{array}$$ where $f^{(+0)}=f_u+{\mu }_{ij}{a}_j{a}_i^{-1}{y}_r\text{.}$

In the second case, $$e_{\mu }u{e}_{\mu }v{e}_{\mu }=\frac{1}{q^r}\sum _{t\in {𝔽}_q^r}(\psi \circ f_u)\left(t\right)\begin{array}{c} r ⋯ μ(i) ⋯ μ(j-1) ⋯ a1 ai aj an w u1(t1)⋯ur-1(tr-1) μ(1) μ(2) μ(3) ⋯ μ(n-1) \end{array}\text{.}$$ Use (UN3) and (N1) to split the sum into two parts corresponding to $t_r=0$ and $t_r\ne 0,$ $$\begin{array}{rcl}{\displaystyle e_{\mu }u{e}_{\mu }v{e}_{\mu }}& =& {\displaystyle \frac{1}{q^r}\sum _{\underset{t_r=0}{t\in {𝔽}_q^r}}(\psi \circ f^{(-0)})\left(t\right)\begin{array}{c} ⋯ μ(i) ⋯ μ(j-1) ⋯ a1 ai aj an urw u1(t1)⋯ur-1(tr-1) μ(1) μ(2) μ(3) ⋯ μ(n-1) \end{array}}\\ & & {\displaystyle +\frac{1}{q^r}\sum _{\underset{t_r\in {𝔽}_q^{*}}{t\in {𝔽}_q^r}}(\psi \circ f_u)\left(t\right)\begin{array}{c} r 1∘→ -1∘→ tr←∘ tr-1←∘ ⋯ μ(i) ⋯ μ(j-1) ⋯ a1 aitr -ajtr-1 an w u1(t1)⋯ur-1(tr-1) μ(1) μ(2) μ(3) ⋯ μ(n-1) \end{array}}\end{array}$$ where $f^{(-0)}=f_u\text{.}$ Now use (UN1), (UN2), (U2), (U1) and (E4) on the second sum to get $$\begin{array}{cc}{\displaystyle \begin{array}{rcl}{\displaystyle e_{\mu }u{e}_{\mu }v{e}_{\mu }}& =& {\displaystyle \frac{1}{q^r}\sum _{\underset{t_r=0}{t\in {𝔽}_q^r}}(\psi \circ f^{(-0)})\left(t\right)\begin{array}{c} μ(1) μ(2) μ(3) ⋯ μ(n-1) a1 a2 a3 an urw u1(t1)⋯ur-1(tr-1) μ(1) μ(2) μ(3) ⋯ μ(n-1) \end{array}}\\ & & {\displaystyle +\frac{1}{q^r}\sum _{\underset{t_r\in {𝔽}_q^{*}}{t\in {𝔽}_q^r}}(\psi \circ f^{\left(1\right)})\left(t\right)\begin{array}{c} ⋯ μ(i) ⋯ μ(j-1) ⋯ a1 aitr -ajtr-1 an w u1(t1)⋯ur-1(tr-1) μ(1) μ(2) μ(3) ⋯ μ(n-1) \end{array}}\end{array}}& \text{(4.27)}\end{array}$$ where $f^{\left(1\right)}={\phi }_r\left(f_u\right)+{\mu }_{ij}{a}_j{a}_i^{-1}{y}_r^{-1},$ and ${\phi }_r\left(f\right)$ is defined by $$\begin{array}{cc}{\displaystyle \sum _{\underset{t_r\in {𝔽}_q^{*}}{t\in {𝔽}_q^r}}(\psi \circ f)\left(t\right)\begin{array}{c} r 1∘→ tr-1←∘ u1(t1)⋯ur-1(tr-1) μ(1) μ(2) μ(3) ⋯ μ(n-1) \end{array}=\sum _{\underset{t_r\in {𝔽}_q^{*}}{t\in {𝔽}_q^r}}(\psi \circ {\phi }_r\left(f\right))\left(t\right)\begin{array}{c} r u1(t1)⋯ur-1(tr-1) μ(1) μ(2) μ(3) ⋯ μ(n-1) \end{array}\text{.}}& (*)\end{array}$$

Remarks: (a) We could have applied these steps for any $u,$ $u,$ and $v,$ so we can iterate the process with each sum. (b) The most complex step in these computations is determining ${\phi }_r\text{.}$ The following section will develop an efficient algorithm for computing the right-hand side of $(*)\text{.}$

Computing ${\phi }_k$ via painting, paths and sinks.

Painting algorithm $\left(u^{\overline{)k}}\right)\text{.}$ Suppose $u=u_1{u}_2\cdots u_r\in N$ decomposes according to $s_{i_1}{s}_{i_2}\cdots s_{i_k}\in W$ (assume $u_T=1\text{).}$ Paint flows down strands (by gravity). Each step is illustrated with the example $u=u_1{u}_2\cdots u_8,$ decomposed according to $s_3{s}_1{s}_2{s}_3{s}_1{s}_4{s}_2{s}_3\in W\text{.}$ (1) Paint the left [respectively right] strand exiting $\overline{)k}$ red [blue] all the way to the bottom of the diagram. $$\begin{array}{c} 1 2 3 4 5 6 7 8 \end{array}\text{where}\hspace{0.17em}\overline{)k}\hspace{0.17em}\text{is}\hspace{0.17em}\overline{)8}\text{.}$$ (2) For each crossing that the red [blue] strand passes through, paint the right [left] strand (if possible) red [blue] until that strand either reaches the bottom or crosses the blue [red] strand of (1). $$\begin{array}{cc}{\displaystyle \begin{array}{c} 1 2 3 4 5 6 7 8 \end{array}\begin{array}{c} 1 2 3 4 5 6 7 8 \end{array}\begin{array}{c} 1 2 3 4 5 6 7 8 \end{array}}& \text{(4.28)}\end{array}$$ Let $$\begin{array}{cc}{\displaystyle u^{\overline{)k}}{u}_1\left(t_1\right)u_2\left(t_2\right)\cdots u_k\left(t_k\right)\hspace{0.17em}\text{painted according to the above algorithm}}& \text{(4.29)}\end{array}$$

Sinks and paths. The diagram $u^{\overline{)k}}$ has a crossed sink at $\overline{)j}$ if $\overline{)j}$ is a crossing between a red strand and a blue one, or $$\begin{array}{c} j \end{array}$$ Note that since $u$ is decomposed according to a minimal expression in $U,$ there will be no crossings of the form $$\begin{array}{c} j \end{array}\text{(since}\hspace{0.17em}\begin{array}{c} j \end{array}\hspace{0.17em}\text{would imply}\hspace{0.17em}\begin{array}{c} j′ j \end{array}\hspace{0.17em}\text{for some}\hspace{0.17em}j\prime \ge j\text{.)}$$ The diagram $u^{\overline{)k}}$ has a bottom sink at $j$ if a red strand enters $j\text{th}$ bottom vertex and a blue strand enters the $(j+1)\text{st}$ bottom vertex, or $$\begin{array}{c} j j+1 \end{array}$$ A red [respectively blue] path $p$ from a sink $s$ (either crossed or bottom) in $u^{\overline{)k}}$ is an increasing sequence $$j_1<j_2<\cdots <j_l=k,$$ such that in $u^{\overline{)k}}$ (a) $\overline{)j_m}$ is directly connected (no intervening crossings) to $\overline{)j_{m+1}}$ by a red [blue] strand, (b) if $s$ is a crossed sink, then $\overline{)j_1}=s,$ (b') if $s$ is a bottom sink, then • in a red path, the $s\text{th}$ bottom vertex connects to the crossing $\overline{)j_1}$ with a red strand. • in a blue path, the $(s+1)\text{st}$ bottom vertex connects to the crossing $\overline{)j_1}$ with a blue strand. Let $$\begin{array}{cc}{\displaystyle P_{=}(u^{\overline{)k}},s)=\left\{\text{red paths from}\hspace{0.17em}s\hspace{0.17em}\text{in}\hspace{0.17em}{u}^{\overline{)k}}\right\}\text{and}{P}_{:}(u^{\overline{)k}},s)=\left\{\text{blue paths from}\hspace{0.17em}s\hspace{0.17em}\text{in}\hspace{0.17em}{u}^{\overline{)k}}\right\}}& \text{(4.30)}\end{array}$$ The weight of a path $p$ is $$\begin{array}{cc}{\displaystyle \text{wt}\left(p\right)=\{\begin{array}{ll}\prod _{\underset{\text{strands at}\hspace{0.17em}\overline{)i}}{p\hspace{0.17em}\text{switches}}}{y}_i,& \text{if}\hspace{0.17em}p\in P_{=}(u^{\overline{)k}},s),\\ \prod _{\underset{\text{strands at}\hspace{0.17em}\overline{)i}}{p\hspace{0.17em}\text{switches}}}(-y_i),& \text{if}\hspace{0.17em}p\in P_{:}(u^{\overline{)k}},s)\text{.}\end{array}}& \text{(4.31)}\end{array}$$ Each sink $s$ in $u^{\overline{)k}}$ (either crossed $\overline{)j}$ or bottom $j\text{)}$ has an associated polynomial $g_s\in {𝔽}_q[y_1,y_2,\dots ,y_{k-1},y_k^{-1}]$ given by $$\begin{array}{cc}{\displaystyle g_s=\sum _{\underset{p\prime \in P_{:}(u^{\overline{)k}},s)}{p\in P_{=}(u^{\overline{)k}},s)}}\text{wt}\left(p\right)y_k^{-1}\text{wt}\left(p\prime \right)\text{.}}& \text{(4.32)}\end{array}$$

Example (continued). If $u=u_1{u}_2\cdots u_8$ decomposes according to $s_3{s}_1{s}_2{s}_3{s}_1{s}_4{s}_2{s}_3$ (as in (4.28)), then $$P_{=}(u^{\overline{)8}},4)=\{\begin{array}{c} 1 3 5 7 8 \end{array},\begin{array}{c} 1 4 7 8 \end{array}\}{P}_{:}(u^{\overline{)8}},4)=\left\{\begin{array}{c} 6 8 \end{array}\right\}$$ with $\text{wt}(1<3<5<7<8)=y_5,$ $\text{wt}(1<4<7<8)=y_1{y}_7,$ and $\text{wt}(6<8)=1\text{.}$ The corresponding polynomial is $$\begin{array}{cc}{\displaystyle g_4=y_5{y}_8^{-1}+y_1{y}_7{y}_8^{-1}\text{.}}& \text{(4.33)}\end{array}$$

Let $u=u_1{u}_2\cdots u_r$ and ${\phi }_r$ be as in (4.27) and $\text{(}*\text{);}$ suppose $u^{\overline{)r}}$ is painted as above. Then $${\phi }_r\left(f\right)=f{|}_{\{y_j\mapsto y_j-g_{\overline{)j}}\hspace{0.17em}|\hspace{0.17em}\overline{)j}\hspace{0.17em}\text{a crossed sink}\}}+\sum _{\underset{\text{sink}}{j\hspace{0.17em}\text{a bottom}}}{\mu }_{\left(j\right)}{g}_j\text{.}$$

Example (continued). Recall $u=s_3{s}_1{s}_2{s}_3{s}_1{s}_4{s}_2{s}_3\text{.}$ Then $u^{\overline{)8}}$ at $\overline{)2},$ $\overline{)3},$ and $\overline{)4}\text{.}$ The only bottom sink is at $4\text{.}$ Therefore, $${\phi }_8\left(f\right)=f{|}_{\underset{\underset{y_2\mapsto y_2-g_{\overline{)2}}}{y_3\mapsto y_3-g_{\overline{)3}}}}{y_4\mapsto y_4-g_{\overline{)4}}}}+{\mu }_{\left(4\right)}{g}_4=f{|}_{\underset{\underset{y_2\mapsto y_2+y_2{y}_8^{-1}{y}_6}{y_3\mapsto y_3+y_5{y}_8^{-1}{y}_6}}{y_4\mapsto y_4+y_7{y}_8^{-1}{y}_6}}+{\mu }_{\left(4\right)}(y_5{y}_8^{-1}+y_1{y}_7{y}_8^{-1})\text{.}$$ (for example, $g_4$ was computed in (4.33)).

A multiplication algorithm

(The algorithm). Let $G={GL}_n\left({𝔽}_q\right)$ and $u,v\in N_{\mu }\text{.}$ An algorithm for multiplying $e_{\mu }u{e}_{\mu }$ and $e_{\mu }v{e}_{\mu }$ is (1) Decompose $u=u_1{u}_2\cdots u_r{u}_T$ according to some minimal expression in $W$ (as in (4.16)). (2) Put $e_{\mu }u{e}_{\mu }v{e}_{\mu }$ into the form specified by (4.25), with $u_{T}v=w·\text{diag}(a_1,a_2,\dots ,a_n)$ $\text{(}w=\pi \left(v\right)\in W\text{).}$ (3) Complete the following (a) If $\ell \left(u_{r}w\right)>\ell \left(w\right),$ then apply relation (4.26). (b) If $\ell \left(u_{r}w\right)<\ell \left(w\right),$ then apply relation (4.27), using ${\left(u_1{u}_2\cdots u_r\right)}^{\overline{)r}}$ and Lemma 4.4 to compute ${\phi }_r\text{.}$ (4) If $r>1,$ then reapply (3) to each sum with $r≔r-1$ and with (a) $w≔u_{r}w,$ after using (3a) or using (3b), in the first sum, (b) $w≔w,$ after using (3b), in the second sum. (5) Set all diagrams not in $N_{\mu }$ to zero.

Sample computation. Suppose $n=3$ and ${\mu }_{\left(i\right)}=1$ for all $1\le i\le 3$ (i.e.. the Gelfand-Graev case). Then $$N_{\mu }=\{\begin{array}{c} a a a \end{array},\begin{array}{c} a a b \end{array},\begin{array}{c} a b b \end{array},\begin{array}{c} a b c \end{array}\hspace{0.17em}|\hspace{0.17em}a,b,c\in {𝔽}_q^{*}\}$$ Suppose $$u=\begin{array}{c} a b c \end{array}\text{and}v=\begin{array}{c} d e e \end{array}\text{.}$$

1. Theorem 4.5 (1): Let $u=u_1{u}_2{u}_3{u}_T\in N_{\mu }$ decompose according to $s_2{s}_1{s}_2\in W,$ with $u_T=\text{diag}(a,b,c)\text{.}$

2. Theorem 4.5 (2): By (4.25) $$\left(e_{\mu }\begin{array}{c} a b c \end{array}{e}_{\mu }\right)\left(e_{\mu }\begin{array}{c} d e e \end{array}{e}_{\mu }\right)=\frac{1}{q^3}\sum _{t\in {𝔽}_q^3}(\psi \circ f_u)\left(t\right)\begin{array}{c} 1 2 3 1 1 1 1 cd ae be \end{array}$$ with $u_{T}v=s_2{s}_1·\text{diag}(cd,ae,be)$ (so $w=s_2{s}_1\text{),}$ and $f_u=-\frac{b}{a}{y}_1-\frac{c}{b}{y}_3$ (as in (4.23)).

3. Theorem 4.5 (3b): Since $\ell \left(u_{3}w\right)<\ell \left(w\right),$ paint $u_1\left(t_1\right)u_2\left(t_2\right)u_3\left(t_3\right)$ to get ${\left(u_1{u}_2{u}_3\right)}^{\overline{)3}}$ (as in (4.29)), $$=\frac{1}{q^3}\sum _{t\in {𝔽}_q^3}(\psi \circ f_u)\left(t\right)\begin{array}{c} 1 2 3 1 1 1 1 cd ae be \end{array}$$ Now apply (4.27), $$=\frac{1}{q^3}\sum _{\underset{t_3=0}{t\in {𝔽}_q^3}}(\psi \circ f^{(-0)})\left(t\right)\begin{array}{c} 1 2 1 1 1 1 cd ae be \end{array}+\frac{1}{q^3}\sum _{\underset{t_3\in {𝔽}_q^{*}}{t\in {𝔽}_q^3}}(\psi \circ f^{\left(1\right)})\left(t\right)\begin{array}{c} 1 2 1 1 1 1 cdt3 ae -bet3-1 \end{array}$$ where $f^{(-0)}=-\frac{b}{a}{y}_1-\frac{c}{b}{y}_3$ and by Lemma 4.4, $$f^{\left(1\right)}={\phi }_3\left(f_u\right)+{\mu }_{13}\frac{be}{cd}{y}_3^{-1}=-\frac{b}{a}{y}_1+\frac{b}{a}{y}_2{y}_3^{-1}-\frac{c}{d}{y}_3+y_3^{-1}\text{.}$$

4. Theorem 4.5 (4): Set $r≔2$ with $w≔u_{r}w=s_1$ in the first sum and $w≔w$ in the second sum.

5. Theorem 4.5 (3a) (3b): In the first sum, $\ell \left(u_2{s}_1\right)<\ell \left(s_1\right),$ so paint $u_1\left(t_1\right)u_2\left(t_2\right)$ to get ${\left(u_1{u}_2\right)}^{\overline{)2}}\text{.}$ In the second sum, $\ell \left(u_2{s}_2{s}_1\right)>\ell \left(s_2{s}_1\right),$ so apply (4.26), $$=\frac{1}{q^3}\sum _{\underset{t_3=0}{t\in {𝔽}_q^3}}(\psi \circ f^{(-0)})\left(t\right)\begin{array}{c} 1 2 1 1 1 1 cd ae be \end{array}+\frac{1}{q^3}\sum _{\underset{t_3\in {𝔽}_q^{*}}{t\in {𝔽}_q^3}}(\psi \circ f^{(+0,1)})\left(t\right)\begin{array}{c} 1 1 1 1 1 cdt3 ae -bet3-1 \end{array}$$ where $f^{(+0,1)}=-\frac{b}{a}{y}_1+\frac{b}{a}{y}_2{y}_3^{-1}-\frac{c}{d}{y}_3+y_3^{-1}-{\mu }_{\left(3\right)}\frac{b}{a}{y}_2{y}_3^{-1}=-\frac{b}{a}{y}_1-\frac{c}{b}{y}_3+y_3^{-1}\text{.}$ Now apply (4.27) to the first sum, $$\begin{array}{rcl}{\displaystyle }& =& {\displaystyle \frac{1}{q^3}\sum _{\underset{t_2=t_3=0}{t\in {𝔽}_q^3}}(\psi \circ f^{(-0,-0)})\left(t\right)\begin{array}{c} 1 1 1 1 1 cd ae be \end{array}+\frac{1}{q^3}\sum _{\underset{t_2\in {𝔽}_q^{*},t_3=0}{t\in {𝔽}_q^3}}(\psi \circ f^{(1,-0)})\left(t\right)\begin{array}{c} 1 1 1 1 1 cdt2 -aet2-1 be \end{array}}\\ & & {\displaystyle +\frac{1}{q^3}\sum _{\underset{t_3\in {𝔽}_q^{*}}{t\in {𝔽}_q^3}}(\psi \circ f^{(+0,1)})\left(t\right)\begin{array}{c} 1 1 1 1 1 cdt3 ae -bet3-1 \end{array}}\end{array}$$ where $f^{(-0,-0)}=-\frac{b}{a}{y}_1-\frac{c}{b}{y}_3$ and $f^{(1,-0)}=\phi \left(f^{(-0)}\right)+{\mu }_{\left(1\right)}\frac{ae}{cd}{y}_2^{-1}=-\frac{b}{a}{y}_1-y_2^{-1}{y}_1+\frac{ae}{cd}{y}_2^{-1}\text{.}$

6. Theorem 4.5 (4): Set $r=1$ with $w≔u_2{s}_1=1$ in the first sum, $w≔s_1$ in the second sum, and $w≔s_1{s}_2{s}_1$ in the third sum.

7. Theorem 4.5 (3a) (3a) (3b): In the first sum $\ell \left(s_{2}1\right)>\ell \left(1\right),$ so apply (4.26); in the second sum $\ell \left(s_2{s}_1\right)>\ell \left(s_1\right),$ so apply (4.26); in the third sum, $\ell \left(s_2{s}_1{s}_2{s}_1\right)<\ell \left(s_1{s}_2{s}_1\right),$ so paint $u_1\left(t_1\right)$ to get $u_1^{\overline{)1}},$ $$\begin{array}{rcl}{\displaystyle }& =& {\displaystyle \frac{1}{q^3}\sum _{\underset{t_2=t_3=0}{t\in {𝔽}_q^3}}(\psi \circ f^{(+0,-0,-0)})\left(t\right)\begin{array}{c} 1 1 1 1 cd ae be \end{array}+\frac{1}{q^3}\sum _{\underset{t_2\in {𝔽}_q^{*},t_3=0}{t\in {𝔽}_q^3}}(\psi \circ f^{(+0,1,-0)})\left(t\right)\begin{array}{c} 1 1 1 1 cdt2 -aet2-1 be \end{array}}\\ & & {\displaystyle +\frac{1}{q^3}\sum _{\underset{t_3\in {𝔽}_q^{*}}{t\in {𝔽}_q^3}}(\psi \circ f^{(+0,1)})\left(t\right)\begin{array}{c} 1 1 1 1 1 cdt3 ae -bet3-1 \end{array}}\end{array}$$ where $f^{(+0,-0,-0)}=-\frac{b}{a}{y}_1-\frac{c}{b}{y}_3+\frac{b}{a}{y}_1=-\frac{c}{b}{y}_3$ and $f^{(+0,1,-0)}=-\frac{b}{a}{y}_1+\frac{ae}{cd}{y}_2^{-1}-y_2^{-1}{y}_1\text{.}$ Now apply (4.27) to the third sum $$\begin{array}{rcl}{\displaystyle }& =& {\displaystyle \frac{1}{q^3}\sum _{\underset{t_2=t_3=0}{t\in {𝔽}_q^3}}(\psi \circ f^{(+0,-0,-0)})\left(t\right)\begin{array}{c} 1 1 1 1 cd ae be \end{array}+\frac{1}{q^3}\sum _{\underset{t_2\in {𝔽}_q^{*},t_3=0}{t\in {𝔽}_q^3}}(\psi \circ f^{(+0,1,-0)})\left(t\right)\begin{array}{c} 1 1 1 1 cdt2 -aet2-1 be \end{array}}\\ & & {\displaystyle +\frac{1}{q^3}\sum _{\underset{t_1=0,t_3\in {𝔽}_q^{*}}{t\in {𝔽}_q^3}}(\psi \circ f^{(-0,+0,1)})\left(t\right)\begin{array}{c} 1 1 1 1 cdt3 ae -bet3-1 \end{array}+\frac{1}{q^3}\sum _{\underset{t_1,t_3\in {𝔽}_q^{*}}{t\in {𝔽}_q^3}}(\psi \circ f^{(1,+0,1)})\left(t\right)\begin{array}{c} 1 1 1 1 cdt1t3 -aet1-1 -bet3-1 \end{array}}\end{array}$$ where $f^{(-0,+0,1)}=-\frac{c}{b}{y}_3+y_3^{-1}$ and $$f^{(1,+0,1)}={\phi }_1\left(f^{(+0,1)}\right)+{\mu }_{\left(1\right)}\frac{ae}{cd}{y}_1^{-1}{y}_3^{-1}=-\frac{b}{a}{y}_1-\frac{c}{b}{y}_3+y_3^{-1}+y_1^{-1}+\frac{ae}{cd}{y}_1^{-1}{y}_3^{-1}\text{.}$$

8. Theorem 4.5 (5): The first sum contains no elements of $N_{\mu },$ so set it to zero. The second sum contains elements of $N_{\mu }$ when $be=-ae{t}_2^{-1},$ so set $t_2=-\frac{a}{b}\text{.}$ The third sum contains elements of $N_{\mu }$ when $cd{t}_3=ae,$ so set $t_3=\frac{ae}{cd}\text{.}$ All the terms in the fourth sum are basis elements. $$\begin{array}{rcl}{\displaystyle }& =& {\displaystyle 0+\frac{1}{q^3}\sum _{\underset{t_2=-\frac{a}{b},t_3=0}{t\in {𝔽}_q^3}}(\psi \circ f^{(+0,1,-0)})\left(t\right)\begin{array}{c} 1 1 1 1 -ab-1cd be be \end{array}}\\ & & {\displaystyle +\frac{1}{q^3}\sum _{\underset{t_1=0,t_3=\frac{ae}{cd}}{t\in {𝔽}_q^3}}(\psi \circ f^{(-0,+0,1)})\left(t\right)\begin{array}{c} 1 1 1 1 ae ae -a-1bcd \end{array}+\frac{1}{q^3}\sum _{\underset{t_1,t_3\in {𝔽}_q^{*}}{t\in {𝔽}_q^3}}(\psi \circ f^{(1,+0,1)})\left(t\right)\begin{array}{c} 1 1 1 1 cdt1t3 -aet1-1 -bet3-1 \end{array}}\\ & =& {\displaystyle \frac{1}{q^2}\psi (-\frac{be}{cd})\begin{array}{c} 1 1 1 1 -ab-1cd be be \end{array}+\frac{1}{q^2}\psi (-\frac{ae}{bd}+\frac{cd}{ae})\begin{array}{c} 1 1 1 1 ae ae -a-1bcd \end{array}}\\ & & {\displaystyle +\frac{1}{q^2}\sum _{t_1,t_3\in {𝔽}_q^{*}}\psi (-\frac{b}{a}{t}_1-\frac{c}{b}{t}_3+t_3^{-1}+t_1^{-1}+\frac{ae}{cd}{t}_1^{-1}{t}_3^{-1})\begin{array}{c} 1 1 1 1 cdt1t3 -aet1-1 -bet3-1 \end{array}\text{.}}\end{array}$$

Notes and References

This is an excerpt of the PhD thesis Unipotent Hecke algebras: the structure, representation theory, and combinatorics by F. Nathaniel Edgar Thiem.

page history