----------------------
Iwahori Hecke Algebras
----------------------

The Iwahori Hecke algebra is defined in:

Nagayoshi Iwahori, On the structure of a Hecke ring of a Chevalley group
over a finite field.  J. Fac. Sci. Univ. Tokyo Sect. I 10 1964 215--236
(1964).

In this original paper, the algebra occurs as the convolution
ring of functions on a p-adic group that are compactly supported
and invariant both left and right by the Iwahori subgroup.
However Iwahori determined its structure in terms of generators
and relations, and it turns out to be a deformation of the
group algebra of the affine Weyl group.

Once the presentation is found, the Iwahori Hecke algebra can be
defined for any Coxeter group. It depends on a parameter :math:`q`
which in Iwahori's paper is the cardinality of the residue field.
But it could just as easily be an indeterminate.

Then the Iwahori Hecke algebra has the following description.
Let :math:`W` be a Coxeter group, with generators (simple reflections)
:math:`s_1,\cdots,s_n`. They satisfy the relations :math:`s_i^2=1` and
the braid relations 

:math:`s_i s_j s_i s_j ... = s_j s_i s_j s_i ...`

where the number of terms on each side is the order
of :math:`s_i s_j`.

The Iwahori Hecke algebra has a basis :math:`T_1,\cdots,T_n` 
subject to relations that resemble those of the :math:`s_i`.
They satisfy the braid relations and the quadratic
relation

:math:`(T_i-q)(T_i+1)=0.`

This can be modified by letting :math:`q_1` and :math:`q_2` be two
indeterminates and letting

:math:`(T_i-q_1)(T_i-q_2) = 0.`

In this generality, Iwahori Hecke algebras have significance
far beyond their origin in the representation theory of
p-adic groups. For example, they appear in the geometry
of Schubert varieties, where they are used in the definition
of the Kazhdan-Lusztig polynomials. They appear in connection
with quantum groups, and in Jones's original paper on the
Jones polynomial.

Here is how to create an Iwahori Hecke algebra::

    sage: R.<q>=PolynomialRing(ZZ)
    sage: H=IwahoriHeckeAlgebraT("B3",q); H
    The Iwahori Hecke Algebra of Type B3 in q,-1 over Univariate
        Polynomial Ring in q over Integer Ring and prefix T
    sage: T1,T2,T3 = H.algebra_generators()
    sage: T1*T1
    (q-1)*T1 + q

If the Cartan type is affine, the generators will be numbered
starting with ``T0`` instead of ``T1``.

You may coerce a Weyl group element into the Iwahori Hecke algebra::

    sage: W = WeylGroup("G2",prefix="s")
    sage: [s1,s2]=W.simple_reflections()
    sage: P.<q>=LaurentPolynomialRing(QQ)
    sage: H = IwahoriHeckeAlgebraT(W,q)
    sage: H(s1*s2)
    T1*T2

Intertwining Operators
----------------------

The Iwahori Hecke operator can be used to study representations
of p-adic groups that have fixed vectors with respect to the
Iwahori subgroup. References:

 - Rogawski, On modules over the Hecke algebra of a :math:`p`-adic
   group, Invent. Math., Inventiones Mathematicae, 79, 1985, 3,
   443--465,

-  Reeder, On certain Iwahori invariants in the unramified principal
   series, Pacific J. Math., Pacific Journal of Mathematics, 153, 1992, 2,
   313--342,

-  Haines, Kottwitz and Parsad, Iwahori-Hecke Algebras,
   http://arxiv.org/abs/math/0309168.

-  Bump and Nakasuji, Casselman's basis of Iwahori vectors and the Bruhat order,
   http://arxiv.org/abs/1002.2996.

-  Casselman, The unramified principal series of :math:`\mathfrak{p}`-adic groups. I. The
   spherical function, Compositio Math., Compositio Mathematica, 40, 1980, 3,
   387--406.

A key feature of the theory are the intertwining operators between different
induced representations. We will show how to implement these intertwining
operators in Sage.

For simplicity we will work over :math:`G=SL(n,F)` where :math:`F=\mathbb{Q}_q`, 
with :math:`q` a prime number, but everything works for an arbitrary split reductive group over a
nonarchimedean local field. If :math:`\mathbf{z}=(z_1,\cdots,z_n)\in\mathbb{C}^n`,
define the following quasicharacters of :math:`T(F)`, the diagonal subgroup
in :math:`G`:

   :math:`\chi_{\mathbf{z}}\left(\begin{array}{ccc} t_1\\&\ddots\\&&t_n\end{array}\right)=\prod_{i=1}^n z_i^{\hbox{ord}(t_i)},\qquad
   \delta\left(\begin{array}{ccc} t_1\\&\ddots\\&&t_n\end{array}\right)=\prod_{i=1}^n |t_i|^{n+1-2i}`

We extend both to characters of the Borel subgroup :math:`B(F)` of upper triangular
matrices by letting the subgroup :math:`N(F)` of upper triangular unipotent matrices
be in the kernels. Let :math:`V(\chi)` with :math:`\chi=\chi_{\mathbf{z}}` is defined to be
the space of locally constant functions :math:`f` on :math:`G` such that:

  :math:`f(b g) = (\delta^{1/2}\chi)(b)f(g),\qquad b\in B(F).`

We have a representation :math:`\pi:G\to\hbox{End}(V(\chi))` by right translation:
:math:`\pi(g)f(h)=f(h g)`. These are the *spherical principal series representations*.
Let :math:`K=SL(n,\mathbb{Z}_q)`. This is the standard maximal compact subgroup. It has a
homomorphism :math:`K\to SL(n,\mathbb{F}_q)` by reduction modulo :math:`q`. The subgroup :math:`J`
of elements of :math:`K` whose images are upper triangular is an open subgroup, the
*Iwahori subgroup*.

Suppose that the :math:`z_i` are all distinct. Then for each :math:`w\in W` there exists
an *intertwining integral* :math:`M_w:V(\chi)\to V({^w\chi})` where the Weyl group
acts on characters of :math:`T(F)` by conjugation. This integral is defined by the
formula

  :math:`M h(g)=\int_{N\cap w N_- w^{-1}} h(w^{-1}n g)\,d n`

where :math:`N` is the group of upper triangular unipotent matrices and :math:`N_-` is the
group of lower triangular matrices. The integral is convergent provided :math:`|z_i/z_{i+1}|<1`
and in general it may be defined by analytic continuation in the :math:`z_i` or another method. 
See Casselman *loc. cit.*.

The problem is how to model the intertwining operators in Sage.

Let :math:`W=N(F)/T(\mathbb{Z}_q)` and :math:`W'=N(F)/T(F)`. These are isomorphic
to the affine and finite Weyl groups, that is, the Weyl groups with
Cartan types ``[`A`,n-1,1]`` and ``[`A`,n-1]``, respectively. 

The *Iwahori Hecke algebra* :math:`\mathcal{H}` is the ring of compactly supported functions :math:`h`
on :math:`G` such that :math:`h(k g k')=h(g)` when :math:`k,k'\in J`. It is a ring under convolution.
:math:`V(\chi)` becomes a module over it by

   :math:`(h f)(g)=\int_G h(x) f(g x)\, d x`.

The subspace :math:`V(\chi)^J` of :math:`V(\chi)` consisting of elements that are fixed by
:math:`J` is invariant under :math:`\mathcal{H}`. This module is finite-dimensional: in
fact, its order is :math:`|W'|=n!`, whereas :math:`V(\chi)` itself is infinite dimensional.
However the finite-dimensional :math:`\mathcal{H}`-module :math:`V(\chi)^J` accurately reflects the
structure of the :math:`G`-module :math:`V(\chi)`. For example :math:`V(\chi)` is irreducible
as a :math:`G`-module if and only if :math:`V(\chi)^J` is irreducible as an :math:`\mathcal{H}`-module.

Normalizing the Haar measure so that :math:`J` has volume :math:`1`, let :math:`T_w` be the
characteristic function of :math:`J w J`, and if :math:`1 \le i \le r` let
:math:`T_i` denote :math:`T_{\sigma_i}`. The :math:`T_w` with :math:`w \in W` form a
basis, and the :math:`T_i` form a set of algebra generators The :math:`T_i` satisfy the
same braid relations as the :math:`s_i`, but the relation :math:`\sigma_i^2 = 1` is
replaced by :math:`T_i^2 = (q - 1) T_i + q`.

The subalgebra elements of :math:`\mathcal{H}` consisting of functions that are
supported in :math:`K` is the finite Iwahori Hecke algebra :math:`\mathcal{H}'`.  Thus
:math:`\dim (H) = |W|` but :math:`\mathcal{H}` is infinite-dimensional The subalgebra :math:`H`
has generators :math:`T_1, \cdots, T_r` but omits :math:`T_0`.

We see that :math:`W`, :math:`W'`, :math:`\mathcal{H}` and :math:`\mathcal{H'}` are all objects that
can be created in Sage.

We define a vector space isomorphism :math:`\alpha = \alpha (\chi) : V (\chi)^J
\to H'` as follows. If :math:`F \in V (\chi)^J` then let :math:`\alpha (F) = f`
where :math:`f` is the function :math:`f (g) = F (g^{- 1})` if :math:`g \in K`, 0 if :math:`g \notin K`.
It may be checked that :math:`\alpha (F) \in H'`. This allows us to model the :math:`|W'|`-dimensional
:math:`\mathcal{H}`-module :math:`V(\chi)` by the :math:`|W'|`-dimensional subalgebra :math:`\mathcal{H}'`.
This idea, which appears in the paper of Rogawski cited above, is due to Joseph
Bernstein.

Let :math:`w\in W` and define a map :math:`\mathcal{M}_w:H\to H` by requiring that

   :math:`\alpha({^w\chi})\circ M_w = \mathcal{M}_w\circ\alpha(\chi)`

as maps from :math:`V(\chi)^J\to H`. Since :math:`M_w` and :math:`\alpha(\chi)`,
:math:`\alpha({^w\chi})` are all homomorphisms of left :math:`\mathcal{H}'`-modules,
:math:`\mathcal{M}_w` is a homomorphism of left :math:`\mathcal{H}'` modules. Now let
:math:`\mu_{\mathbf{z}}(w)= \mathcal{M}_w(1)` where :math:`1` denotes the identity element
of :math:`\mathcal{H}'`.

Because :math:`\mathcal{M}_w` is a :math:`\mathcal{H}'`-module homomorphism, we have

   :math:`\mathcal{M}_w(h) = \mathcal{M}_w(h\cdot 1)= h \mathcal{M}_w(1) = h\cdot\mu_{\mathbf{z}}(w)`.

In other words, the intertwining operator is modeled by multiplication
by :math:`\mu_{\mathbf{z}}(w)` when we identify :math:`V(\chi)^J` and :math:`V({^w\chi})^J` with
:math:`H` by means of the homomorphisms :math:`\alpha`. We are therefore left with the
problem of computing :math:`\mu_{\mathbf{z}}(w)`. If :math:`l(w_1w_2)=l(w_1)+l(w_2)`
then :math:`M_{w_1w_2}=M_{w_1}M_{w_2}` and it follows that

   :math:`\mu_{\mathbf{z}}(w_1w_2)=\mu_{\mathbf{z}}(w_2)\mu_{w_2\mathbf{z}}(w_1)`.

(Here :math:`w_2` acts on the spectral parameters :math:`\mathbf{z}` in the
obvious way.) Thus we are reduced to the determination of :math:`\mu_{\mathbf{z}}(w)`
when :math:`w=s_i` is a simple reflection, and this is accomplished by Theorem 3.4
in Casselman, *loc. cit.*:

   :math:`\mu_{\mathbf{z}}(s_i)=\frac{1}{q}T_i+\left(1-\frac{1}{q}\right)\frac{\mathbf{z}^{\alpha_i}}{1-\mathbf{z}^{\alpha_i}}.`

Here the simple root :math:`\alpha_i=(0,\cdots,0,1,-1,0,\cdots,0)` in the ambient lattice,
where the :math:`1` is in the :math:`i`-th position, so :math:`\mathbf{z}^\alpha_i=z_i/z_{i+1}`.

In addition to the intertwining operators, let us construct a basis :math:`\psi_w` of
:math:`V(\chi)^J` indexed by elements of :math:`W'`. Let

   :math:`\psi_w(b k)=\left\{\begin{array}{ll}\delta^{1/2}\chi(b) & \text{if $k\in J u^{-1} J$ with $u \ge w$},\\0&\text{otherwise,}\end{array}\right.`

where :math:`b\in B(F)` and :math:`k\in K`. In order to make sense of this definition,
bear in mind that every element of :math:`G` has a decomposition as a product :math:`b k` with
:math:`b\in B(F)` and :math:`k\in K`, and every :math:`k\in K` belongs to a unique double coset
:math:`J u^{-1} J` with :math:`u\in W'`.

The image of :math:`\psi_w` under the homomorphism :math:`\alpha` is just :math:`\sum_{u\ge w} T_u`,
and by abuse of notation we will denote this element of :math:`\mathcal{H}'` also
by :math:`\psi_w`. Now let us ask to evaluate :math:`m(u,v)=(\Lambda_v\psi_u)(1)`. It
may be shown that :math:`m(u,v)=0` unless :math:`u\le v`, and that :math:`m(u,u)=1`. In other
words, the "matrix" :math:`m` is upper triangular in the Bruhat order.

Bump and Nakasuji used Sage to investigate this question and arrived at the
following conjecture. This is conjectured for more general groups than just
the :math:`SL(n)` that we are considering, but only for the simply-laced groups
(types A,D,E). It follows from the Deodhar conjecture that the set

    :math:`S(u,v)=\{\alpha\in\Phi^+|u\le v r_\alpha < v\}`

has cardinality :math:`\ge l(v)-l(u)`, where :math:`l` is the length function on :math:`W'`.
(Remember that :math:`r_\alpha` is the reflection in the positive root :math:`\alpha`.)
If the Kazhdan-Lusztig polynomial :math:`P_{w_0v,w_0u}=1`, then
:math:`|S(u,v)|=l(v)-l(u)`.

**Conjecture** (Bump and Nakasuji) If the Kazhdan-Lusztig polynomial :math:`P_{w_0v,w_0u}=1` then

    :math:`m(u,v)=\prod_{\alpha\in S(u,v)}\frac{1-q^{-1}\mathbf{z}^\alpha}{1-\mathbf{z}^\alpha}`

The following Sage code is capable of verifying this statement for ``['A',3]``, and of
course can be adapted to any root system.

Intertwining Operator Program
-----------------------------

This program can compute both the actual and conjectured values of :math:`m(u,v)`.

::

   import copy
   
   P1.<q>=PolynomialRing(QQ)
   W = WeylGroup("A3",prefix="s")
   KL = KazhdanLusztigPolynomial(W,q)
   
   P.<q,z1,z2,z3,z4>=PolynomialRing(QQ)
   F = Frac(P)
   H = IwahoriHeckeAlgebraT(W,q,base_ring=F)
   [s1,s2,s3]=W.simple_reflections()
   w0 = W.long_element()
   [T1,T2,T3]=H.algebra_generators()
   
   def mu(z,s):
       """
       Produces an element of the Hecke algebra that mimics
       the intertwining integral corresponding to a simple
       reflection.
       """
       [z1,z2,z3,z4] = z
       if s == s1:
           return q^(-1)*T1+(1-1/q)*(z1/(z2-z1))
       elif s == s2:
           return q^(-1)*T2+(1-1/q)*(z2/(z3-z2))
       elif s == s3:
           return q^(-1)*T3+(1-1/q)*(z3/(z4-z3))
   
   def reflect(s,z):
       """
       Applies the simple reflection s to the spectral data z.
       """
       return (Matrix(z)*s.matrix()).list()
   
   def intertwiner(w,debug=False):
       """
       This is mu_z(w) in general. The function mu(z,s) implemented
       above is only for simple reflections.

       Run with debug=True to see what it is really doing.
       """
       decomp = w.reduced_word()
       decomp.reverse()
       prod = H(1)
       if debug:
           clist = ""
       for i in range(len(decomp)):
           alist = copy.deepcopy(decomp[:i])
           z = [z1,z2,z3,z4]
           for j in alist:
               z = reflect(W.simple_reflection(j),z)
           s = W.simple_reflection(decomp[i])
           if debug:
               clist +="mu(%s,%s)"%(z.__repr__(),s.__repr__())
               if i < len(decomp)-1:
                   clist += "*"
           else:
               prod = prod*mu(z,s)
       if debug:
           return clist
       else:
           return prod
   
   def psi(u):
       """
       u is a permutation. This produces the sum of the f_v for v>=u.
       """
       u = H(u).support_of_term()
       return sum(H(v) for v in W if u.bruhat_le(v))
   
   def ev(f):
       """
       Evaluate the element of the space of Iwahori fixed vectors
       in the induced model at the identity.
       """
       return f.coefficient(W(1))
   
   def m(u,v):
       """
       It is assumed that u <= v. Apply the v intertwiner to
       psi(u) and evaluate at 1.
       """
       u = W(u)
       v = W(v)
       return ev(psi(u)*intertwiner(H(v)))
   
   def rfactor(alpha):
       """
       If alpha is a root, returns (1-q^(-1)*z^alpha)/(1-z^alpha).
       """
       z = [z1,z2,z3,z4]
       za = prod(z[i]**alpha[i] for i in range(4))
       return (1-q^(-1)*za)/(1-za)
   
   def conjectured_m(u,v):
       """
       This is the value conjectured for m(u,v) by Bump and Nakasuji
       if u and v satisfy a hypothesis.
       """
       refdict = W.reflections()
       S = [refdict[r] for r in refdict.keys() if u.bruhat_le(v*r) and (v*r).bruhat_le(v)]
       return prod(rfactor(alpha) for alpha in S)