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

Last updated: 26 March 2015

## Preliminaries

### Hecke algebras

This section gives some of the main representation theoretic results used in this thesis, and defines Hecke algebras. Three roughly equivalent structures are commonly used to describe the representation theory of an algebra $A\text{:}$ (1) Modules. Modules are vector spaces on which $A$ acts by linear transformations. (2) Representations. Every choice of basis in an $n\text{-dimensional}$ vector space on which $A$ acts gives a representation, or an algebra homomorphism from $A$ to the algebra of $n×n$ matrices. (3) Characters. The trace of a matrix is the sum of its diagonal entries. A character is the composition of the algebra homomorphism of (2) with the trace map. The following discussion will focus on modules and characters.

#### Modules and characters

Let $A$ be a finite dimensional algebra over the complex numbers $ℂ\text{.}$ An $A\text{-module}$ $V$ is a finite dimensional vector space over $ℂ$ with a map $A×V ⟶ V (a,v) ⟼ av$ such that $(c1)v = cv, c∈ℂ, (ab)v = a(bv), a,b∈A,v∈V, (a+b) (c1v1+c2v2) = c1av1+ c2av2+ c1bv1+ c2bv2, c1,c2∈ℂ.$ An $A\text{-module}$ $V$ is irreducible if it contains no nontrivial, proper subspace $V\prime$ such that $av\prime \in V\prime$ for all $a\in A$ and $v\prime \in V\prime \text{.}$

An $A\text{-module}$ homomorphism $\theta :V\to V\prime$ is a $ℂ\text{-linear}$ transformation such that $aθ(v)=θ(av), for a∈A,v∈V,$ and an $A\text{-module}$ isomorphism is a bijective $A\text{-module}$ homomorphism. Write $HomA(V,V′) = {A-module homomorphisms V→V′} EndA(V) = HomA(V,V).$

Let $\stackrel{ˆ}{A}$ be an indexing set for the irreducible modules of $A$ (up to isomorphism), and fix a set ${Aγ}γ∈Aˆ$ of isomorphism class representatives. An algebra $A$ is semisimple if every $A\text{-module}$ $V$ decomposes $V≅⨁γ∈Aˆ mγ(V)Aγ, wheremγ(V)∈ ℤ≥0,mγ (V)Aγ= Aγ⊕⋯⊕Aγ⏟mγ(V) terms.$ In this thesis, all algebras (though not necessarily all Lie algebras) are semisimple.

(Schur's Lemma). Suppose $\gamma ,\mu \in \stackrel{ˆ}{A}$ with corresponding irreducible modules ${A}^{\gamma }$ and ${A}^{\mu }\text{.}$ Then $dim(HomA(Aγ,Aμ))= δγμ= { 1, if γ=μ, 0, otherwise.$

Suppose $A\subseteq B$ is a subalgebra of $B$ and let $V$ be an $A\text{-module}\text{.}$ Then $B{\otimes }_{A}V$ is the vector space over $ℂ$ presented by generators $\left\{b\otimes v | b\in B,v\in V\right\}$ with relations $ba⊗v = b⊗av, a∈A,b∈B,v∈V, (b1+b2)⊗ (v1+v2) = b1⊗v1+ b1⊗v2+ b2⊗v1+ b2⊗v2, b1,b2∈B, v1,v2∈V.$ Note that the map $B×(B⊗AV) ⟶ B⊗AV (b′,b⊗v) ⟼ (b′b)⊗v$ makes $B{\otimes }_{A}V$ a $B\text{-module.}$ Define induction and restriction (respectively) as the maps $IndAB: {A-modules} ⟶ {B-modules} V ⟼ B⊗AV ResAB: {B-modules} ⟶ {A-modules} V ⟼ V$

Suppose $V$ is an $A\text{-module.}$ Every choice of basis $\left\{{v}_{1},{v}_{2},\dots ,{v}_{n}\right\}$ of $V$ gives rise to an algebra homomorphism $ρ:A→Mn(ℂ), where Mn(ℂ)= {n×n matrices with entries in ℂ}.$ The character ${\chi }_{V}:A\to ℂ$ associated to $V$ is $χV(a)= tr(ρ(a)).$ The character ${\chi }_{V}$ is independent of the choice of basis, and if $V\cong V\prime$ are isomorphic $A\text{-modules,}$ then ${\chi }_{V}={\chi }_{V\prime }\text{.}$ A character ${\chi }_{V}$ is irreducible if $V$ is irreducible. The degree of a character ${\chi }_{V}$ is ${\chi }_{V}\left(1\right)=\text{dim}\left(V\right),$ and if $\chi \left(1\right)=1,$ then a character is linear; note that linear characters are both irreducible characters and algebra homomorphisms.

Define $R[A]=ℂ-span {χγ | γ∈Aˆ} ,where χγ= χAγ,$ with a $ℂ\text{-bilinear}$ inner product given by $⟨χγ,χμ⟩ =δγμ. (2.1)$ Note that the semisimplicity of $A$ implies that any character is contained in the subspace $ℤ≥0-span {χγ | γ∈Aˆ}.$ If ${\chi }_{V}$ is a character of a subalgebra $A$ of $B,$ then let $IndAB(χV)= χB⊗AV$ and if ${\chi }_{V\prime }$ is a character of $B,$ then ${\text{Res}}_{A}^{B}\left({\chi }_{V\prime }\right)$ is the restriction of the map ${\chi }_{V\prime }$ to $A\text{.}$

(Frobenius Reciprocity). Let $A$ be a subalgebra of $B\text{.}$ Suppose $\chi$ is a character of $A$ and $\chi \prime$ is a character of $B\text{.}$ Then $⟨IndAB(χ),χ′⟩= ⟨χ,ResAB(χ′)⟩.$

#### Weight space decompositions

Suppose $A$ is a commutative algebra. Then $dim(Aγ)=1, for all γ∈Aˆ.$ The corresponding character ${\chi }^{\gamma }:A\to ℂ$ is an algebra homomorphism, and we may identify the label $\gamma$ with the character ${\chi }^{\gamma },$ so that $av=χγ(a)v= γ(a)v,for a∈A,v∈Aγ.$

If $A$ is a commutative subalgebra of $B$ and $V$ is an $B\text{-module,}$ then as a $A\text{-module}$ $V=⨁γ∈Aˆ Vγ,where Vγ ={v∈V | av=γ(a)v,a∈A}.$ The subspace ${V}_{\gamma }$ is the $\gamma \text{-weight}$ space of $V,$ and if ${V}_{\gamma }\ne 0$ then $V$ has a weight $\gamma \text{.}$

For large subalgebras $A,$ such a decomposition can help construct the module $V\text{.}$ For example, 1. If $0\ne {v}_{\gamma }\in {V}_{\gamma },$ then ${\left\{{v}_{\gamma }\right\}}_{{V}_{\gamma }\ne 0}$ is a linearly independent set of vectors. In particular, if $\text{dim}\left({V}_{\gamma }\right)=1$ for all ${V}_{\gamma }\ne 0,$ then $\left\{{v}_{\gamma }\right\}$ is a basis for $V\text{.}$ 2. If $V$ is irreducible, then $B{V}_{\gamma }=V\text{.}$ Chapter 6 uses this idea to construct irreducible modules of the Yokonuma algebra.

#### Characters in a group algebra

Let $G$ be a finite group. The group algebra $ℂG$ is the algebra $ℂG=ℂ-span{g∈G}$ with basis $G$ and multiplication determined by the group multiplication in $G\text{.}$ A $G\text{-module}$ $V$ is a vector space over $ℂ$ with a map $G×V ⟶ V (g,v) ⟼ gv$ such that $(gg′)v=g(g′v), g(cv+c′v′)=cgv+c′gv′, for c,c′∈ℂ,g,g′∈G,v,v′∈V.$ Note that there is a natural bijection ${ℂG-modules} ⟶ {G-modules} V ⟼ V ,$ so I will use $G\text{-modules}$ and $ℂG\text{-modules}$ interchangeably. Let $\stackrel{ˆ}{G}$ index the irreducible $ℂG\text{-modules.}$

The inner product (2.1) on $R\left[G\right]$ has an explicit expression $⟨·,·⟩: R[G]×R[G] ⟶ ℂ (χ,χ′) ⟼ 1∣G∣∑g∈Gχ(g)χ′(g-1),$ and if $U$ is a subgroup of $G,$ then induction is given by $IndUG(χ): G ⟶ ℂ g ⟼ 1∣U∣∑x∈Gxgx-1∈Uχ(xgx-1).$

#### Hecke algebras

An idempotent $e\in ℂG$ is a nonzero element that satisfies ${e}^{2}=e\text{.}$ For $\gamma \in \stackrel{ˆ}{G},$ let $eγ= χλ(1)∣G∣ ∑g∈Gχγ (g-1)g∈ ℂG.$ These are the minimal central idempotents of $ℂG,$ and they satisfy $1=∑γ∈Gˆ eγ,eγ2= eγ,eγ eμ=δγμ eγ,ℂGeγ ≅dim(Gγ)Gγ.$ In particular, as a $G\text{-module,}$ $ℂG≅⨁γ∈Gˆ ℂGeγ.$

Let $U$ be a subgroup of $G$ with an irreducible $U\text{-module}$ $M\text{.}$ The Hecke algebra $ℋ\left(G,U,M\right)$ is the centralizer algebra $ℋ(G,U,M)= EndℂG (IndUG(M)).$ If ${e}_{M}\in ℂU$ is an idempotent such that $M\cong ℂU{e}_{M},$ then $IndUG(M)= ℂG⊗ℂU ℂUeM=ℂG ⊗ℂUeM ≅ℂGeM$ and the map $θM: eMℂGeM ⟶∼ ℋ(G,U,M) eMgeM ⟼ ϕg where ϕg: ℂGeM ⟶ ℂGeM keM ⟼ keMgeM, (2.2)$ is an algebra anti-isomorphism (i.e. ${\theta }_{M}\left(ab\right)={\theta }_{M}\left(b\right){\theta }_{M}\left(a\right)\text{).}$

The following theorem connects the representation theory of $G$ to the representation theory of $ℋ\left(G,U,M\right)\text{.}$ Theorem 2.3 and the Corollary are in [CRe1981, Theorem 11.25].

(Double Centralizer Theorem). Let $V$ be a $G\text{-module}$ and let $ℋ={\text{End}}_{ℂG}\left(V\right)\text{.}$ Then, as a $G\text{-module,}$ $V≅⨁γ∈Gˆ dim(ℋγ)Gγ$ if and only if, as an $ℋ\text{-module,}$ $V≅⨁γ∈Gˆ dim(Gγ)ℋγ$ where $\left\{{ℋ}^{\gamma } | \gamma \in \stackrel{ˆ}{G},{ℋ}^{\gamma }\ne 0\right\}$ is the set of irreducible $ℋ\text{-modules.}$

Suppose $U$ is a subgroup of $G\text{.}$ Let $M\cong ℂU{e}_{M}$ be an irreducible $U\text{-module.}$ Write $ℋ=ℋ\left(G,U,M\right)\text{.}$ Then the map ${G-submodules of ℂGeM} ⟶ {ℋ-modules} V ⟼ eMV$ is a bijection that sends ${G}^{\gamma }↦{ℋ}^{\gamma }$ for every irreducible ${G}^{\gamma }$ that is isomorphic to a submodule of ${\text{Ind}}_{U}^{G}\left(M\right)$ $\text{(}{G}^{\gamma }↪{\text{Ind}}_{U}^{G}\left(M\right)\text{).}$

### Chevalley Groups

There are two common approaches used to define finite Chevalley groups. One strategy considers the subgroup of elements in an algebraic group fixed under a Frobenius map (see [Car1985]). The approach here, however, begins with a pair $\left(𝔤,V\right)$ of a Lie algebra $𝔤$ and a $𝔤\text{-module}$ $V,$ and constructs the Chevalley group from a variant of the exponential map. This perspective gives an explicit construction of the elements, which will prove useful in the computations that follow (see also [Ste1967]).

#### Lie algebra set-up

A finite dimensional Lie algebra $𝔤$ is a finite dimensional vector space over $ℂ$ with a $ℂ\text{-bilinear}$ map $[·,·]: 𝔤×𝔤 ⟶ 𝔤 (X,Y) ⟼ [X,Y]$ such that (a) $\left[X,X\right]=0,$ for all $X\in 𝔤,$ (b) $\left[X,\left[Y,Z\right]\right]+\left[Y,\left[Z,X\right]\right]+\left[Z,\left[X,Y\right]\right]=0,$ for $X,Y,Z\in 𝔤\text{.}$ Note that if $A$ is any algebra, then the bracket $\left[a,b\right]=ab-ba$ for $a,b\in A$ gives a Lie algebra structure to $A\text{.}$

A $𝔤\text{-module}$ is a vector space $V$ with a map $𝔤×V ⟶ V (X,v) ⟼ Xv$ such that $(aX+bY)v = aXv+bYv, for all a,b∈ℂ, X,Y∈𝔤,v∈V, X(av1+bv2) = aXv1+ bXv2, for all a,b∈ℂ, X∈𝔤,v1,v2∈V, [X,Y]v = X(Yv)- Y(Xv), for all X,Y∈𝔤,v∈V.$ A Lie algebra $𝔤$ acts diagonally on $V$ if there exists a basis $\left\{{v}_{1},\dots ,{v}_{r}\right\}$ of $V$ such that $Xvi∈ℂvi, for all X∈𝔤 and i=1,2,…,r.$

The center of $𝔤$ is $Z(𝔤)= {X∈𝔤 | [X,Y]=0 for all Y∈𝔤}.$ Let $\gamma \in \stackrel{ˆ}{𝔤}$ index the irreducible $𝔤\text{-modules}$ ${𝔤}^{\gamma }\text{.}$ A Lie algebra $𝔤$ is reductive if for every finite-dimensional module $V$ on which $Z\left(𝔤\right)$ acts diagonally, $V=⨁γ∈𝔤ˆ mγ(V)𝔤γ, where mγ(V)∈ ℤ≥0.$ If $𝔤$ is reductive, then $𝔤=Z(𝔤)⊕𝔤s where 𝔤s=[𝔤,𝔤] is semisimple.$

Let $𝔤$ be a reductive Lie algebra. A Cartan subalgebra $𝔥$ of $𝔤$ is a subalgebra satisfying (a) ${𝔥}^{k}=\left[{𝔥}^{k-1},𝔥\right]=0$ for some $k\ge 1$ $\text{(}𝔥$ is nilpotent), (b) $𝔥=\left\{X\in 𝔤 | \left[X,H\right]\in 𝔥,H\in 𝔥\right\}$ $\text{(}𝔥$ is its own normalizer). If ${𝔥}_{s}$ is a Cartan subalgebra of ${𝔤}_{s},$ then $𝔥=Z\left(𝔤\right)\oplus {𝔥}_{s}$ is a Cartan subalgebra of $𝔤\text{.}$ Let $𝔥*=Homℂ (𝔥,ℂ)and 𝔥s*= Homℂ(𝔥s,ℂ).$

As an ${𝔥}_{s}\text{-module,}$ ${𝔤}_{s}$ decomposes $𝔤s≅𝔥s⊕ ⨁0≠α∈𝔥s* (𝔤s)α,where (𝔤s)α= ⟨X∈𝔤s | [H,X]=α(H)X,H∈𝔥s⟩.$ The set of roots of ${𝔤}_{s}$ is $R=\left\{\alpha \in {𝔥}^{*} | \alpha \ne 0,{\left({𝔤}_{s}\right)}_{\alpha }\ne 0\right\}\text{.}$ A set of simple roots is a subset $\left\{{\alpha }_{1},{\alpha }_{2},\dots ,{\alpha }_{\ell }\right\}\subseteq R$ of the roots such that (a) $ℚ{\otimes }_{ℂ}{𝔥}_{s}^{*}=ℚ\text{-span}\left\{{\alpha }_{1},{\alpha }_{2},\dots ,{\alpha }_{\ell }\right\}$ with $\left\{{\alpha }_{1},\dots ,{\alpha }_{\ell }\right\}$ linearly independent, (b) Every root $\beta \in R$ can be written as $\beta ={c}_{1}{\alpha }_{1}+{c}_{2}{\alpha }_{2}+\cdots +{c}_{\ell }{\alpha }_{\ell }$ with either $\left\{{c}_{1},\dots ,{c}_{\ell }\right\}\subseteq {ℤ}_{\ge 0}$ or $\left\{{c}_{1},\dots ,{c}_{\ell }\right\}\subseteq {ℤ}_{\le 0}\text{.}$ Every choice of simple roots splits the set of roots $R$ into positive roots $R+= {β∈R | β=c1α1+c2α2+⋯+cℓαℓ,ci∈ℤ≥0}$ and negative roots $R-= {β∈R | β=c1α1+c2α2+⋯+cℓαℓ,ci∈ℤ≤0} .$ In fact, ${R}^{-}=-{R}^{+}\text{.}$

Example. Consider the Lie algebra ${𝔤𝔩}_{2}={𝔤𝔩}_{2}\left(ℂ\right)=\left\{2×2 \text{matrices with entries in} ℂ\right\},$ and bracket $\left[·,·\right]$ given by $\left[X,Y\right]=XY-YX\text{.}$ Write $𝔤𝔩2=Z(𝔤𝔩2) ⊕𝔰𝔩2,$ where $Z\left({𝔤𝔩}_{2}\right)=\left\{\left(\begin{array}{cc}c& 0\\ 0& c\end{array}\right) | c\in ℂ\right\}$ and ${𝔰𝔩}_{2}=\left\{X\in {𝔤𝔩}_{2} | \text{tr}\left(X\right)=0\right\}\text{.}$ Also, $𝔰𝔩2= {(a00-a) | a∈ℂ}⊕ {(00c0) | c∈ℂ}⊕ {(0c00) | c∈ℂ}.$ Let $\alpha \in {𝔥}^{*}={\left\{\left(\begin{array}{cc}a& 0\\ 0& b\end{array}\right) | a,b\in ℂ\right\}}^{*}$ be the simple root given by $\alpha \left(\begin{array}{cc}a& 0\\ 0& b\end{array}\right)=a-b,$ so that ${R}^{+}=\left\{\alpha \right\}$ and ${R}^{-}=\left\{-\alpha \right\}\text{.}$

#### From a Chevalley basis of ${𝔤}_{s}$ to a Chevalley group

For every pair of roots $\alpha ,-\alpha ,$ there exists a Lie algebra isomorphism ${\varphi }_{a}:{𝔰𝔩}_{2}\to ⟨{𝔤}_{\alpha },{𝔤}_{-\alpha }⟩\text{.}$ Under this isomorphism, let $Xα=ϕa (0100) ∈(𝔤s)α, Hα=ϕα (100-1) ∈𝔥s, X-α=ϕα (0010) ∈(𝔤s)-α.$ Note that $\left[{X}_{\alpha },{X}_{-\alpha }\right]={H}_{\alpha }\text{.}$ The following classical result can be found in [Hum1972, Theorem 25.2].

(Chevalley Basis). There is a choice of the ${\varphi }_{\alpha }$ such that the set $\left\{{X}_{\alpha },{H}_{{\alpha }_{i}} | \alpha \in R,1\le i\le \ell \right\}$ is a basis of ${𝔤}_{s}$ satisfying (a) ${H}_{\alpha }$ is a $ℤ\text{-linear}$ combination of ${H}_{{\alpha }_{1}},{H}_{{\alpha }_{2}},\dots ,{H}_{{\alpha }_{\ell }}\text{.}$ (b) Let $\alpha ,\beta \in R$ such that $\beta \ne ±\alpha ,$ and suppose $l,r\in {ℤ}_{\ge 0}$ are maximal such ${β-lα,…,β-α,β,β+α,…,β+rα} ⊆R.$ Then $[Xα,Xβ]= { ±(l+1) Xα+β, if r≥1, 0 otherwise.$

A basis as in Theorem 2.5 is a Chevalley basis of ${𝔤}_{s}$ (For an analysis of the choices involved see [Sam1969] and [Tit1966]).

Let $V$ be a finite dimensional $𝔤\text{-module}$ such that $V$ has a $ℂ\text{-basis}$ $\left\{{v}_{1},{v}_{2},\dots ,{v}_{r}\right\}$ that satisfies (a) There exists a $ℂ\text{-basis}$ $\left\{{H}_{1},\dots ,{H}_{n}\right\}$ of $𝔥$ such that (1) ${H}_{{\alpha }_{i}}\in {ℤ}_{\ge 0}\text{-span}\left\{{H}_{1},\dots ,{H}_{n}\right\},$ (2) ${H}_{i}{v}_{j}\in ℤ{v}_{j}$ for all $i=1,2,\dots ,n$ and $j=1,2,\dots ,r\text{.}$ (3) ${\text{dim}}_{ℤ}\left(ℤ\text{-span}\left\{{H}_{1},{H}_{2},\dots ,{H}_{n}\right\}\right)\le {\text{dim}}_{ℂ}\left(𝔥\right)\text{.}$ (b) $\frac{{X}_{\alpha }^{n}}{n!}{v}_{i}\in ℤ\text{-span}\left\{{v}_{1},{v}_{2},\dots ,{v}_{r}\right\}$ for $\alpha \in R,$ $n\in {ℤ}_{\ge 0}$ and $i=1,2,\dots ,r\text{.}$ (c) ${\text{dim}}_{ℤ}\left(ℤ\text{-span}\left\{{v}_{1},{v}_{2},\dots ,{v}_{r}\right\}\right)\le {\text{dim}}_{ℂ}\left(V\right)\text{.}$ (Condition (a) guarantees that $Z\left(𝔤\right)$ acts diagonally. If $Z\left(𝔤\right)=0,$ then the existence of such a basis is guaranteed by a theorem of Kostant [Hum1972, Theorem 27.1]).

Let $V$ be a finite dimensional $𝔤\text{-module}$ that satisfies (a)-(c) above. For $H\in 𝔥,$ let $(Hn)= (H-1)(H-2)⋯(H-(n+1))n! ∈End(V).$ As a transformation of the basis ${v}_{1},{v}_{2},\dots ,{v}_{r},$ the element ${H}_{i}=\text{diag}\left({h}_{1},{h}_{2},\dots ,{h}_{r}\right)\in \text{End}\left(V\right)$ with ${h}_{j}\in ℤ\text{.}$ Let $y\in {ℂ}^{*}\text{.}$ Temporarily abandon precision (i.e. allow infinite sums) to obtain $∑n≥0 (y-1)n (Hin) = diag ( ∑n≥0(y-1)n (h1n), ∑n≥0(y-1)n (h2n),…, ∑n≥0(y-1)n (hrn), ) = diag(yh1,yh2,…,yhr) ∈End(V)(by the binomial theorem).$ This computation motivates some of the definitions below.

Let $𝔥ℤ=ℤ-span {H1,H2,…,Hn}. (2.3)$ The finite field ${𝔽}_{q}$ with $q$ elements has a multiplicative group ${𝔽}_{q}^{*}$ and an additive group ${𝔽}_{q}^{+}\text{.}$ Let $Vq=𝔽q-span {v1,v2,…,vr}. (2.4)$

The finite reductive Chevalley group ${G}_{V}\subseteq GL\left({V}_{q}\right)$ is $GV= ⟨ xα(a),hH(b) | α∈R,H∈𝔥ℤ,α ∈𝔽q,b∈𝔽q* ⟩ ,$ where $xα(a) = ∑n≥0 anXαnn!, and (2.5) hH(b) = diag(bλ1(H),bλ2(H),…,bλr(H)), where Hvi=λi(H)vi. (2.6)$

Remarks. 1. If we “allow” infinite sums, then $hHi(b)= ∑n≥0 (b-1)n (Hin).$ 2. If $𝔤={𝔤}_{s},$ then ${G}_{V}=⟨{x}_{\alpha }\left(t\right)⟩\text{.}$

Example. Suppose (as before) $𝔤={𝔤𝔩}_{2}$ and let $V=ℂ-span {(10),(01)}$ be the natural $𝔤\text{-module}$ given by matrix multiplication. Then $𝔥$ has a basis $𝔥={(a00b) | a,b∈ℂ}= ℂ-span{(1000),(0001)}.$ By direct computation, $xα(t)= (1t01) andh(a00b) (t)=(ta00tb) for a,b∈ℤ,$ and ${G}_{V}={GL}_{2}\left({𝔽}_{q}\right)$ (the general linear group).

### Some combinatorics of the symmetric group

This section describes some of the pertinent combinatorial objects and techniques.

#### A pictorial version of the symmetric group ${S}_{n}$

Let ${s}_{i}\in {S}_{n}$ be the simple reflection that switches $i$ and $i+1,$ and fixes everything else. The group ${S}_{n}$ can be presented by generators ${s}_{1},{s}_{2},\dots ,{s}_{n-1}$ and relations $si2=1, sisi+1si= si+1sisi+1, sisj=sjsi, for ∣i-j∣>1.$ Using two rows of $n$ vertices and strands between the top and bottom vertices, we may pictorially describe permutations in the following way. View $sias \cdots \cdots i .$ Multiplication in ${S}_{n}$ corresponds to concatenation of diagrams, so for example, ${s}_{1} {s}_{2} = = =s2s1.$ Therefore, ${S}_{n}$ is generated by ${s}_{1},{s}_{2},\dots ,{s}_{n-1}$ with relations $= , = , = .$

#### Compositions, partitions, and tableaux

A composition $\mu =\left({\mu }_{1},{\mu }_{2},\dots ,{\mu }_{r}\right)$ is a sequence of positive integers. The size of $\mu$ is $\mid \mu \mid ={\mu }_{1}+{\mu }_{2}+\cdots +{\mu }_{r},$ the length of $\mu$ is $\ell \left(\mu \right)=r$ and $μ≤= {μ≤1,μ≤2,…,μ≤r} ,where μ≤i= μ1+μ2+⋯+μi. (2.7)$ If $\mid \mu \mid =n,$ then $\mu$ is a composition of $n$ and we write $\mu \models n\text{.}$ View $\mu$ as a collection of boxes aligned to the left. If a box $x$ is in the $i\text{th}$ row and $j\text{th}$ column of $\mu ,$ then the content of $x$ is $c\left(x\right)=i-j\text{.}$ For example, if $μ=(2,5,3,4)= ,$ then $\mid \mu \mid =14,$ $\ell \left(\mu \right)=4,$ ${\mu }_{\le }=\left(2,7,10,14\right),$ and the contents of the boxes are $0 1 -1 0 1 2 3 -2 -1 0 -3 -2 -1 0 .$ Alternatively, ${\mu }_{\le }$ coincides with the numbers in the boxes at the end of the rows in the diagram $1 2 3 4 5 6 7 8 9 10 11 12 13 14 .$

A partition $\nu =\left({\nu }_{1},{\nu }_{2},\dots ,{\nu }_{r}\right)$ is a composition where ${\nu }_{1}\ge {\nu }_{2}\ge \cdots \ge {\nu }_{r}>0\text{.}$ If $\mid \nu \mid =n,$ then $\nu$ is a partition of $n$ and we write $\nu ⊢n\text{.}$ Let $𝒫={partitions} and𝒫n= {ν⊢n}. (2.8)$ Suppose $\nu \in 𝒫\text{.}$ The conjugate partition $\nu \prime =\left({\nu }_{1}^{\prime },{\nu }_{2}^{\prime },\dots ,{\nu }_{\ell }^{\prime }\right)$ is given by $νi′=Card {j | νj≥i}.$ In terms of diagrams, $\nu \prime$ is the collection of boxes obtained by flipping $\nu$ across its main diagonal. For example, $ifν= ,thenν′= .$

Suppose $\nu ,\mu$ are partitions. If ${\nu }_{i}\ge {\mu }_{i}$ for all $1\le i\le \ell \left(\mu \right),$ then the skew partition $\nu /\mu$ is the collection of boxes obtained by removing the boxes in $\mu$ from the upper left-hand corner of the diagram $\lambda \text{.}$ For example, if $ν= andμ= ,thenν/μ= .$ A horizontal strip $\nu /\mu$ is a skew shape such that no column contains more than one box. Note that if $\mu =\varnothing ,$ then $\nu /\mu$ is a partition.

A column strict tableau $Q$ of shape $\nu /\mu$ is a filling of the boxes of $\nu /\mu$ by positive integers such that (a) the entries strictly increase along columns, (b) the entries weakly increase along rows. The weight of $Q$ is the composition $\text{wt}\left(Q\right)=\left(\text{wt}{\left(Q\right)}_{1},\text{wt}{\left(Q\right)}_{2},\dots \right)$ given by $wt(Q)i=number of i in Q.$ For example, $Q= 1 1 3 1 2 3 3 5 haswt(Q)= (3,1,3,0,1).$

#### Symmetric functions

The symmetric group ${S}_{n}$ acts on the set of variables $\left\{{x}_{1},{x}_{2},\dots ,{x}_{n}\right\}$ by permuting the indices. The ring of symmetric polynomials in the variables $\left\{{x}_{1},{x}_{2},\dots ,{x}_{n}\right\}$ is $Λn(x)= {f∈ℤ[x1,x2,…,xn] | w(f)=f,w∈Sn}.$ For $r\in {ℤ}_{\ge 0},$ the $r\text{th}$ elementary symmetric polynomial is $er(x:n)= ∑1≤i1n,$ and the $r\text{th}$ power sum symmetric polynomial is $pr(x:n)= x1r+x2r+ ⋯+xnr.$ For any partition $\nu \in 𝒫,$ let $ev(x:n) = eν1(x:n) eν2(x:n)⋯ eνℓ(x:n) pv(x:n) = pν1(x:n) pν2(x:n)⋯ pνℓ(x:n).$ The Schur polynomial corresponding to $\nu$ is $sν(x:n)= det(eνi′-i+j(x:n)), (2.9)$ for which Pieri’s rule gives $sν(x:n) s(n)(x:n)= ∑horizontal strip γ/ν∣γ/ν∣=n sγ(x:n) [Mac1995, I.5.16]. (2.10)$

For each $t\in ℂ,$ the Hall-Littlewood symmetric function is $Pν(x:n;t) = ∑wν∈Snνw ( x1ν1 x2ν2⋯ xnνn ∏νi>νj xi-txjxi-xj ) = 1vν(t) ∑w∈Snw ( x1ν1 x2ν2⋯ xnνn ∏i where ${v}_{\nu }\left(t\right)\in ℂ$ is a constant as in [Mac1995, III.2]; and they satisfy $Pν(x:n;0)= sν(x:n), P(1n) (x:n;t)= en(x:n).$ For $t\in ℂ,$ $Λn(x)=ℤ-span {eν(x:n)}= ℤ-span{sν(x:n)} =ℤ-span{Pν(x:n;t)}, (2.11)$ and if we extend coefficients to $ℚ,$ then $ℚ⊗Λn(x)= ℚ-span{pν(x:n)}.$

Note that for $n>m$ there is a map $Λn(x) ⟶ Λm(x) f(x1,x2,…,xn) ⟼ f(x1,…,xm,0,…,0)$ which sends ${s}_{\nu }\left(x:n\right)↦{s}_{\nu }\left(x:m\right),$ ${e}_{\nu }\left(x:n\right)↦{e}_{\nu }\left(x:m\right),$ etc. Let $\left\{{x}_{1},{x}_{2},\dots \right\}$ be an infinite set of variables. The Schur function ${s}_{\nu }\left(x\right)$ is the infinite sequence $sν(x)= ( sν(x:1), sν(x:2), sν(x:3),… ) ,$ and one can define elementary symmetric functions ${e}_{r}\left(x\right),$ power sum symmetric functions ${p}_{r}\left(x\right),$ and Hall-Littlewood symmetric functions ${P}_{\nu }\left(x;t\right),$ analogously. The ring of symmetric functions in the variables $\left\{{x}_{1},{x}_{2},\dots \right\}$ is $Λ(x)=ℤ-span {sν(x) | ν∈𝒫},$ and let $Λℂ(x)=ℂ -span{sν(x) | ν∈𝒫}.$

#### RSK correspondence

The classical RSK correspondence provides a combinatorial proof of the identity $∏i,j>0 11-xiyj =∑ν⊢nn≥0 sν(x)sν(y) [Knu1970]$ by constructing for each $\ell \ge 0$ a bijection between the matrices $b\in {M}_{\ell }\left({ℤ}_{\ge 0}\right)$ and the set of pairs $\left(P\left(b\right),Q\left(b\right)\right)$ of column strict tableaux with the same shape. The bijection is as follows.

If $P$ is a column strict tableau and $j\in {ℤ}_{>0},$ let $P←j$ be the column strict tableau given by the following algorithm (a) Insert $j$ into the the first column of $P$ by displacing the smallest number $\ge j\text{.}$ If all numbers are $ then place $j$ at the bottom of the first column. (b) Iterate this insertion by inserting the displaced entry into the next column. (c) Stop when the insertion does not displace an entry.

A two-line array $\left(\begin{array}{cccc}{i}_{1}& {i}_{2}& \cdots & {i}_{n}\\ {j}_{1}& {j}_{2}& \cdots & {j}_{n}\end{array}\right)$ is a two-rowed array with ${i}_{1}\le {i}_{2}\le \cdots \le {i}_{n}$ and ${j}_{k}\ge {j}_{k+1}$ if ${i}_{k}={i}_{k+1}\text{.}$ If $b\in {M}_{\ell }\left({ℤ}_{\ge 0}\right),$ then let $\stackrel{\to }{b}$ be the two-line array with ${b}_{ij}$ pairs $\left(\genfrac{}{}{0}{}{i}{j}\right)\text{.}$

For $b\in {M}_{\ell }\left({ℤ}_{\ge 0}\right),$ suppose $b→= (i1i2⋯inj1j2⋯jn).$ Then the pair $\left(P\left(b\right),Q\left(b\right)\right)$ is the final pair in the sequence $(∅,∅)= (P0,Q0), (P1,Q1), (P2,Q2),…, (Pn,Qn),= (P(b),Q(b)),$ where $\left({P}_{k},{Q}_{k}\right)$ is a pair of column strict tableaux with the same shape given by $Pk=Pk-1←jk and Qk is defined by sh(Qk)=sh(Pk) with ik in the new box sh(Qk)/sh(Qk-1).$ For example, $b=(110002010) corresponds tob→= (1122321332)$ and provides the sequence $(∅,∅), ( 2 , 1 ) , ( 1 2 , 1 1 ) , ( 1 2 3 , 1 1 2 ) , ( 1 2 3 3 , 1 1 2 2 ) , ( 1 2 3 2 3 , 1 1 3 2 2 )$ so that $(P(b),Q(b))= ( 1 2 3 2 3 , 1 1 3 2 2 ) .$

## 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