# Hecke Algebra of a Coxeter Group

Let $G$ be a Coxeter group with a generating set $S.$

Definition 1.  The Hecke algebra of $G,$ denoted $H(G),$ is generated by elements $\{T_g\}_{g\in G}$ over the ring $\mathbb{Z}[q^{1/2},q^{-1/2}]$ such that multiplication satisfies

$\begin{array}{lcll}T_sT_x&=&qT_{sx}+(q-1)T_x&\mbox{if~}sx

where the order is Bruhat.  It is trivial to verify that the Hecke algebra is unital with unit $T_1.$

Proposition 2.  If $s\in S,$ then $T_s$ is invertible with inverse

$T_{s}^{-1}=(q^{-1}-1)T_1+q^{-1}T_s.$

Proof.

$\begin{array}{lcl}T_sT_{s}^{-1}&=&T_s\left((q^{-1}-1)T_1+q^{-1}T_s\right)\\&=&T_s(q^{-1}T_1-T_1+q^{-1}T_s)\\&=&q^{-1}T_sT_1-T_sT_1+q^{-1}T_sT_s\\&=&(q^{-1}-1)T_sT_1+q^{-1}T_sT_s\\&=&(q^{-1}-1)T_s+T_1+q^{-1}(q-1)T_s\\&=&T_1.\end{array}$

It follows that all elements of the form $T_g$ with $g\in G$ are invertible, so the Hecke algebra is a division algebra.  Moreover it is a *-algebra with involution defined by

$\displaystyle \overline{\sum_{g\in G}p_g(q^{1/2})T_g}=\sum_{g\in G}p_g(q^{1/2})T_{g^{-1}}^{-1}.$

It turns out that there is a basis $\{x_g\}_{g\in G}$ of $H(G)$ where

$\displaystyle x_g=q^{\ell(g)/2}\sum_{h\leq g}(-1)^{\ell(h,g)}q^{-\ell(h)}P_{h,g}T_h$

with $\ell(h,g)=|\ell(h)-\ell(g)|$ and $P_{h,g}\in\mathbb{Z}[q],$ which can be proven to uniquely exist for elements $h,g\in G,$ which are called the Kazhdan-Lusztig polynomials.

[1]  Björner, Anders and Francesco Brenti.  Combinatorics of Coxeter Groups.  Vol. 231.  Graduate Texts in Mathematics.  Springer.  2005.

# Bruhat Order

The Bruhat order is defined on a Coxeter group $G$ in the following manner for $x,y\in G$:

1. $x\stackrel{t}{\to}y\Leftrightarrow x^{-1}y=t$ with $t$ a reflection (conjugate of a generator) and $\ell(x)<\ell(y)$,
2. $x\leq y\Leftrightarrow x\stackrel{t_0}{\to}x_1\stackrel{t_1}{\to}\cdots\stackrel{t_{n-1}}{\to}x_n\stackrel{t_n}{\to}y.$

Reflexivity is clear since $x\stackrel{1}{\to}x$ (assuming $1$ is considered a generator).  Transitivity is trivial.  And if we have $x\leq y$ and $y\leq x,$ then in the simple case where $x\stackrel{t}{\to}y$ and $y\stackrel{t'}{\to}x,$ we have

$x^{-1}y=t$

and

$y^{-1}x=t'$

which imply that $t'=t^{-1}$ and hence that $t=t'.$  So $x^{-1}y=y^{-1}x.$  Since we must have $\ell(x)=\ell(y),$ it follows that $x=y.$  The general cases are done by induction.  So we have antisymmetry.

So it is a partial order on the Coxeter group.  The Bruhat digraph is constructed with elements as vertices and a directed edge from $x$ to $y$ iff $x\leq y.$  Note how this ordering differs from the simplicial ordering we previously mentioned on the induced Coxeter complex.

Recall the notion of standard subgroups (also known as parabolic subgroups) of a Coxeter group where $J$ triply represents a subset of indices of a generating set, the corresponding generators indexed by those indices, and the subgroup generated by such generators.  Also recall the definition of descents of elements.  In the following definition, $I,J$ are used in the second sense (as subsets of generators), and we will use $G_J$ to represent the subgroup generated by $J.$

Definition 1.  Let $I\subseteq J\subseteq S$ and define

$\begin{array}{l}D_I^J=\{g\in G:I\subseteq D_R(g)\subseteq J\}\\D_I=D_I^I\\D^I=D_\varnothing^{S-I}.\end{array}$

The sets $D_I^J$ are called the right descent classes (or the analogous definition for left descent classes).

Proposition 2.  Let $J\subseteq S.$  Then every $g\in G$ has a unique factorization of the form $g=g^Jg_J$ where $g^J\in D^J$ and $g_J\in G_J.$  Moreover we have $\ell(g)=\ell(g^J)+\ell(g_J).$

We can define the map $P^J:G\to G^J$ where $P^J(g)=g^J.$  This map is clearly idempotent.  Moreover we have the following.

Proposition 3.  The map $P^J$ preserves Bruhat order $(g_1\leq g_2\Rightarrow g_1^J\leq g_2^J).$

[1]  Björner, Anders and Francesco Brenti.  Combinatorics of Coxeter Groups.  Vol. 231.  Graduate Texts in Mathematics.  Springer.  2005.

# More on Coxeter Groups

Definition 1.  Let $B$ and $N$ be subgroups of a group $G.$  They are called a BN-pair if

1. $B\cup N$ generates $G$ and $B\cap N\unlhd N.$
2. $W=N/(B\cap N)$ is generated by a set $S$ of involutions.
3. Let $s\in S$ and $w\in W,$ then $BsB\cdot BwB\subseteq BswB\cup BwB.$
4. Let $s\in S,$ then $BsB\cdot BsB\neq B.$

$W$ is called the Weyl group of the BN-pair, and $|S|$ is called the rank of the BN-pair.

So from 3 and 4 we have $BsB\cdot BsB\subseteq BsB.$  If $G$ has a BN-pair, then it has a direct decomposition called the Bruhat decomposition.  It has the form

$\displaystyle G=\bigsqcup_{w\in W}BwB.$

This is plausible since $W$ has stuff in $N$ but not in $B$ (if not $1$).  So a term in the union is represented as a product of something in $N$ (but not $B$) multiplied on both sides by something in $B,$ but together $B$ and $N$ generate $G.$

One can further show that if $G$ has a BN-pair, then $W$ is a Coxeter group with generating set $S.$  Also, every element by definition has the form $g=r_1\cdots r_k$ with $r_i$ generators and $k$ minimal.  $k$ is then called the length of $g$ and denoted $\ell(g).$

Definition 2.  We define a reflection in a Coxeter group $G$ as a conjugate of a generator.

Exchange Property.  Let $g=s_1\cdots s_k$ be a reduced word with each $s_i$ a generator.  If $\ell(sg)\leq\ell(g)$ for a generator $s,$ then $sg=s_1\cdots\hat{s_i}\cdots s_k$ for some $i\leq k.$

We could replace the generator $s$ with a reflection $t$ and remove the reduced and possible equality to obtain the Strong Exchange Property.

Proposition 3.  The strong exchange property holds in a Coxeter group.

Deletion Property.  Let $g=s_1\cdots s_k$ and $\ell(g) then $g=s_1\cdots\hat{s_i}\cdots\hat{s_j}\cdots s_k$ for $1\leq i

Theorem 4.  Let $(G,S)$ be a pair with $G$ a group and $S$ a generating set of $G$ such that $s^2=1$ for all $s\in S.$  Then the following are equivalent.

1. $G$ is a Coxeter group.
2. $(G,S)$ satisfies the exchange property.
3. $(G,S)$ satisfies the deletion property.

Also worthy of mentioning is the concept of descents.  Let $(G,S)$ be a pair as described above and $T$ be the set of reflections in $G.$

Definition 5.  Define

$T_L(g)=\{t\in T:\ell(tg)<\ell(g)\}$

$T_R(g)=\{t\in T:\ell(gt)<\ell(g)\}$

and then define $D_L(g)=T_L(g)\cap S$ and $D_R(g)=T_R(g)\cap S.$  The latter two sets are respectively called the left and right descents of $g.$

My initial terminological intuition is that $s\in D_L(g)$ is a left descent in the sense that the “altitude” relative to $g$ is lower when shifted to $s$: $\ell(sg)<\ell(g).$

Now let $g=s_1\cdots s_k$ be reduced.  Then $\ell(g)=k.$  Moreover left multiples of $g$ that shorten its length must have the form $s_1s_2\cdots s_i\cdots s_2s_1$ where $1\leq i\leq k.$  So $T_L(g)$ are precisely those elements.  There are $k$ such palindrome killers.  So we have $|T_L(g)|=\ell(g).$The palindrome notion is clear.  The killer part refers to the palindrome killing more letters than it adds–namely killing $i$ letters while adding $i-1$ letters (hence net kill $1$).

Since the inverse of an element is its mirror, it follows that $T_L(g)=T_R(g^{-1})$ and $\ell(g)=\ell(g^{-1}).$  We also thus have $|T_L(g^{-1})|=\ell(g).$  This is easy to see as palindrome killers of the inverse have the form $s_ks_{k-1}\cdots s_{k-i}\cdots s_{k-1}s_k$ with $0\leq i\leq k-1.$

[1]  Björner, Anders and Francesco Brenti.  Combinatorics of Coxeter Groups.  Vol. 231.  Graduate Texts in Mathematics.  Springer.  2005.

# Metric Construction of Buildings

Let $G$ be a Coxeter group where $G$ is generated by $n$ elements.  Also by $\ell(g)$ for $g\in G$ we mean the minimal length is a product decomposition of $g.$  Let us first use the book definition.

Definition 1.  A Weyl distance function is a map $\delta:C\times C\to G$ where $C$ a set whose elements are called chambers such that

1. $\delta(x,y)=1\Leftrightarrow x=y;$
2. if $\delta(x,y)=g$ and $w\in C$ such that $\delta(w,x)=r_i,$ then $\delta(w,y)\in\{r_ig,g\}.$  If we also have that $\ell(r_ig)=\ell(g)+1,$ then $\delta(w,y)=r_ig;$
3. if $\delta(x,y)=g,$ then for any $i$ we have a chamber $w\in C$ such that $\delta(w,x)=r_i$ and $\delta(w,y)=r_ig.$

The pair $(C,\delta)$ is called a $W$– metric space.  The triple $(C,G,\delta)$ is called a building.

I’m fairly certain I copied correctly (triple checked), but it looks like $3\Rightarrow 2,$ or the first sentence in $2$ at least.  Of importance is the fact we previously mentioned:  that chambers of a Coxeter complex coincide with elements of the Coxeter group (since they are (standard) cosets of the trivial standard subgroup).  If we thus let $C=C(G_\Delta),$ then $\delta:G\times G\to G$ can be thought of as a product on $G.$  By condition $1,$ the element $1\in G$ is thus not an identity with respect to this product.  Also in this regard one can show that the chambers $C(G_\Delta)$ of a Coxeter complex form a building where

$d(x,y)=\ell(\delta(x,y))$

with $d$ being the gallery metric we previously defined.

Conversely we can say two elements in $C$ are $r_i$-adjacent if $\delta(x,y)=r_i$ and $r_i$-equivalent if they are either $r_i$-adjacent or equal.  If $x$ and $y$ are $r_i$-equivalent, we write $x\sim_{r_i}y.$  This is an equivalence relation since

Proposition 2.  $\delta(x,y)=\delta(y,x)$ if one takes a generator value.

Proof.  Suppose $\delta(x,y)=r_i.$  By part $3$ of the definition there is a $w\in C$ such that $\delta(w,x)=r_i$ and $\delta(w,y)=r_i^2=1.$  Thus by $1$ we have $w=y$ and thus

$\delta(y,x)=\delta(w,x)=r_i=\delta(x,y).$

The equivalence classes under $\sim_{r_i}$ are called $r_i$-panels.  A panel is an $r_i$-panel for some $i.$  Galleries can be defined similarly with this terminology.  Thus $(C,G,\delta)=\left(C(G_\Delta),d\right).$

[1]  Abramenko, Peter and Kenneth Brown.  Buildings.  Graduate Texts in Mathematics.  Vol. 248.  Springer Science and Business Media.  2008.

# Coxeter Complexes

Let $G$ be a Coxeter group with $n$ generators and $J$ be a subset of $\{1,...,n\}.$  We define the subgroup $\langle \{r_i\}_{i\in J}\rangle$ as the standard subgroup $J$ (i.e. hereafter we abuse notation by using $J$ interchangeably for the subset of indicies as well as the subgroup generated by the corresponding elements of $G$).  Its cosets will be called standard cosets of $J$.

Definition 1.  Let $g_1H,g_2J$ be (standard) cosets of standard subgroups $H$ and $J.$  We define the partial ordering $g_1H\leq g_2J\Leftrightarrow g_2J\subseteq g_1H.$  If $G_\Delta$ denotes the set of standard cosets in $G,$ then we call $(G_\Delta,\leq)$ the Coxeter complex of $G,$ and will denote it $G_\Delta$ for short.

It’s clear that $G_\Delta$ is a poset since the ordering is merely reverse containment on all cosets.  Elements of $G_\Delta$ will be called simplices, maximal elements will be called chambers.  Since $1$ is a standard subgroup with $J=\varnothing,$ it follows that the chambers simply coincide with elements of $G.$  Also if $J$ is generated by one generator, then it has two elements: $J=\{1,r_i\}.$  Cosets of such standard subgroups have the form $gJ=\{g,gr_i\},$ and are called panels.  In the case where $g=1,$ we call $1J=J$ the fundamental panel of $J.$ Also if $g$ is a chamber and $J$ is generated by a singleton, then $gJ$ is a face of $g.$  Note that $G$ is the trivial minimal element, but suppose $J$ is generated by $n-1$ generators of $G$, then a coset of $J$ is called a vertex.

Every panel is the face of exactly two chambers:  panels have the form $\{g,gr_i\},$ and are thus faces of $g$ and $gr_i.$

Recall every element in a Coxeter group has the form

$\displaystyle g=\prod_{k=1}^ls_k$

where $s_k=r_i$ for some $i$.  If $g$ is a chamber and we define the chamber $g_i=gs_1\cdots s_i,$ then $g_i$ and $g_{i+1}$ have a panel in common: $\{g_i,g_is_{i+1}=g_{i+1}\}.$  A gallery is a sequence $(g_1,...,g_l)$ of chambers such that $g_i$ and $g_{i+1}$ have a panel in common.  We can thus define a metric on $G$

$\displaystyle d(x,y)=\min\{l:(x=g_1,...,g_l=y)\mbox{~is a gallery}\}.$

This metric can be extended to any simplices, where it is the minimized version of the above taken over all chambers containing those simplices.

Definition 2.  A type function is a map $\tau:G_V\to\{1,...,n\}$ where $G_V$ denotes the vertices in $G_\Delta$ such that it is a bijection on $G_V(g)=\{gJ\}$ for all $g$ where $G_V(g)$ are the $n$ vertices of the chamber $g.$  The value (or singleton set) $\tau(gJ)$ is called the type of $gJ;$  we may dually call $\{\tau(gJ)\}^C$ the cotype of $gJ.$

The standard type function on a Coxeter complex $G_\Delta$ is defined chamber-wise by

$\tau(gJ)=S-J,$

by which we mean the one element of $S-J,$ as $J$ ranges through $\{1,...,n\}$ (in the sense of which generator it excludes).  Remember we use $J$ both to represent a subset of $\{1,...,n\}$ and to represent the Coxeter subgroup (aka standard subgroup) generated by the elements $\{r_i\}_{i\in J}.$

We can generalize the type function on the Coxeter complex from vertices to all simplices.  We simply map the simplex to the subset of $\{1,...,n\}$ to which all of its vertices are sent.  Hence chambers get sent to the whole set, and have empty cotype.

Definition 3.  Let $gJ$ be a simplex.  We define its link, denoted $lnk(gJ),$ as the set of all simplices $\{g'K\}$ such that $gJ\cap g'K=\varnothing$ and $gJ,g'K$ have a lower bound.

The link is clearly a subcomplex since if $gJ\cap g'K=\varnothing,$ then $gJ\cap S=\varnothing$ for all subsets $S\subseteq g'K.$  Thus the facet ordering is still transitive.

Proposition 4.  Let $gJ$ be a simplex.  Then $lnk(gJ)=J_\Delta$ (as posets).

[1]  Abramenko, Peter and Kenneth Brown.  Buildings.  Graduate Texts in Mathematics.  Vol. 248.  Springer Science and Business Media.  2008.