Iwahori-Hecke Algebras¶
AUTHORS:
- Daniel Bump, Nicolas Thiery (2010): Initial version
- Brant Jones, Travis Scrimshaw, Andrew Mathas (2013): Moved into the category framework and implemented the Kazhdan-Lusztig \(C\) and \(C^{\prime}\) bases
-
sage.algebras.iwahori_hecke_algebra.
IwahoriHeckeAlgebra
¶ The Iwahori-Hecke algebra of the Coxeter group
W
with the specified parameters.INPUT:
W
– a Coxeter group or Cartan typeq1
– a parameter
OPTIONAL ARGUMENTS:
q2
– (default-1
) another parameterbase_ring
– (defaultq1.parent()
) a ring containingq1
andq2
The Iwahori-Hecke algebra [Iwa1964] is a deformation of the group algebra of a Weyl group or, more generally, a Coxeter group. These algebras are defined by generators and relations and they depend on a deformation parameter \(q\). Taking \(q = 1\), as in the following example, gives a ring isomorphic to the group algebra of the corresponding Coxeter group.
Let \((W, S)\) be a Coxeter system and let \(R\) be a commutative ring containing elements \(q_1\) and \(q_2\). Then the Iwahori-Hecke algebra \(H = H_{q_1,q_2}(W,S)\) of \((W,S)\) with parameters \(q_1\) and \(q_2\) is the unital associative algebra with generators \(\{T_s \mid s\in S\}\) and relations:
\[\begin{split}\begin{aligned} (T_s - q_1)(T_s - q_2) &= 0\\ T_r T_s T_r \cdots &= T_s T_r T_s \cdots, \end{aligned}\end{split}\]where the number of terms on either side of the second relations (the braid relations) is the order of \(rs\) in the Coxeter group \(W\), for \(r,s \in S\).
Iwahori-Hecke algebras are fundamental in many areas of mathematics, ranging from the representation theory of Lie groups and quantum groups, to knot theory and statistical mechanics. For more information see, for example, [KL1979], [HKP2010], [Jon1987] and Wikipedia article Iwahori-Hecke_algebra.
Bases
A reduced expression for an element \(w \in W\) is any minimal length word \(w = s_1 \cdots s_k\), with \(s_i \in S\). If \(w = s_1 \cdots s_k\) is a reduced expression for \(w\) then Matsumoto’s Monoid Lemma implies that \(T_w = T_{s_1} \cdots T_{s_k}\) depends on \(w\) and not on the choice of reduced expressions. Moreover, \(\{ T_w \mid w\in W \}\) is a basis for the Iwahori-Hecke algebra \(H\) and
\[\begin{split}T_s T_w = \begin{cases} T_{sw}, & \text{if } \ell(sw) = \ell(w)+1,\\ (q_1+q_2)T_w -q_1q_2 T_{sw}, & \text{if } \ell(sw) = \ell(w)-1. \end{cases}\end{split}\]The \(T\)-basis of \(H\) is implemented for any choice of parameters
q_1
andq_2
:sage: R.<u,v> = LaurentPolynomialRing(ZZ,2) sage: H = IwahoriHeckeAlgebra('A3', u,v) sage: T = H.T() sage: T[1] T[1] sage: T[1,2,1] + T[2] T[1,2,1] + T[2] sage: T[1] * T[1,2,1] (u+v)*T[1,2,1] + (-u*v)*T[2,1] sage: T[1]^-1 (-u^-1*v^-1)*T[1] + (v^-1+u^-1)
Working over the Laurent polynomial ring \(Z[q^{\pm 1/2}]\) Kazhdan and Lusztig proved that there exist two distinguished bases \(\{ C^{\prime}_w \mid w \in W \}\) and \(\{ C_w \mid w \in W \}\) of \(H\) which are uniquely determined by the properties that they are invariant under the bar involution on \(H\) and have triangular transitions matrices with polynomial entries of a certain form with the \(T\)-basis; see [KL1979] for a precise statement.
It turns out that the Kazhdan-Lusztig bases can be defined (by specialization) in \(H\) whenever \(-q_1 q_2\) is a square in the base ring. The Kazhdan-Lusztig bases are implemented inside \(H\) whenever \(-q_1 q_2\) has a square root:
sage: H = IwahoriHeckeAlgebra('A3', u^2,-v^2) sage: T=H.T(); Cp= H.Cp(); C=H.C() sage: T(Cp[1]) (u^-1*v^-1)*T[1] + (u^-1*v) sage: T(C[1]) (u^-1*v^-1)*T[1] + (-u*v^-1) sage: Cp(C[1]) Cp[1] + (-u*v^-1-u^-1*v) sage: elt = Cp[2]*Cp[3]+C[1]; elt Cp[2,3] + Cp[1] + (-u*v^-1-u^-1*v) sage: c = C(elt); c C[2,3] + C[1] + (u*v^-1+u^-1*v)*C[3] + (u*v^-1+u^-1*v)*C[2] + (u^2*v^-2+2+u^-2*v^2) sage: t = T(c); t (u^-2*v^-2)*T[2,3] + (u^-1*v^-1)*T[1] + (u^-2)*T[3] + (u^-2)*T[2] + (-u*v^-1+u^-2*v^2) sage: Cp(t) Cp[2,3] + Cp[1] + (-u*v^-1-u^-1*v) sage: Cp(c) Cp[2,3] + Cp[1] + (-u*v^-1-u^-1*v)
The conversions to and from the Kazhdan-Lusztig bases are done behind the scenes whenever the Kazhdan-Lusztig bases are well-defined. Once a suitable Iwahori-Hecke algebra is defined they will work without further intervention.
For example, with the “standard parameters”, so that \((T_r-q^2)(T_r+1) = 0\):
sage: R.<q> = LaurentPolynomialRing(ZZ) sage: H = IwahoriHeckeAlgebra('A3', q^2) sage: T=H.T(); Cp=H.Cp(); C=H.C() sage: C(T[1]) q*C[1] + q^2 sage: elt = Cp(T[1,2,1]); elt q^3*Cp[1,2,1] - q^2*Cp[2,1] - q^2*Cp[1,2] + q*Cp[1] + q*Cp[2] - 1 sage: C(elt) q^3*C[1,2,1] + q^4*C[2,1] + q^4*C[1,2] + q^5*C[1] + q^5*C[2] + q^6
With the “normalized presentation”, so that \((T_r-q)(T_r+q^{-1}) = 0\):
sage: R.<q> = LaurentPolynomialRing(ZZ) sage: H = IwahoriHeckeAlgebra('A3', q, -q^-1) sage: T=H.T(); Cp=H.Cp(); C=H.C() sage: C(T[1]) C[1] + q sage: elt = Cp(T[1,2,1]); elt Cp[1,2,1] - (q^-1)*Cp[2,1] - (q^-1)*Cp[1,2] + (q^-2)*Cp[1] + (q^-2)*Cp[2] - (q^-3) sage: C(elt) C[1,2,1] + q*C[2,1] + q*C[1,2] + q^2*C[1] + q^2*C[2] + q^3
In the group algebra, so that \((T_r-1)(T_r+1) = 0\):
sage: H = IwahoriHeckeAlgebra('A3', 1) sage: T=H.T(); Cp=H.Cp(); C=H.C() sage: C(T[1]) C[1] + 1 sage: Cp(T[1,2,1]) Cp[1,2,1] - Cp[2,1] - Cp[1,2] + Cp[1] + Cp[2] - 1 sage: C(_) C[1,2,1] + C[2,1] + C[1,2] + C[1] + C[2] + 1
On the other hand, if the Kazhdan-Lusztig bases are not well-defined (when \(-q_1 q_2\) is not a square), attempting to use the Kazhdan-Lusztig bases triggers an error:
sage: R.<q>=LaurentPolynomialRing(ZZ) sage: H = IwahoriHeckeAlgebra('A3', q) sage: C=H.C() Traceback (most recent call last): ... ValueError: The Kazhdan_Lusztig bases are defined only when -q_1*q_2 is a square
We give an example in affine type:
sage: R.<v> = LaurentPolynomialRing(ZZ) sage: H = IwahoriHeckeAlgebra(['A',2,1], v^2) sage: T=H.T(); Cp=H.Cp(); C=H.C() sage: C(T[1,0,2]) v^3*C[1,0,2] + v^4*C[1,0] + v^4*C[0,2] + v^4*C[1,2] + v^5*C[0] + v^5*C[2] + v^5*C[1] + v^6 sage: Cp(T[1,0,2]) v^3*Cp[1,0,2] - v^2*Cp[1,0] - v^2*Cp[0,2] - v^2*Cp[1,2] + v*Cp[0] + v*Cp[2] + v*Cp[1] - 1 sage: T(C[1,0,2]) (v^-3)*T[1,0,2] - (v^-1)*T[1,0] - (v^-1)*T[0,2] - (v^-1)*T[1,2] + v*T[0] + v*T[2] + v*T[1] - v^3 sage: T(Cp[1,0,2]) (v^-3)*T[1,0,2] + (v^-3)*T[1,0] + (v^-3)*T[0,2] + (v^-3)*T[1,2] + (v^-3)*T[0] + (v^-3)*T[2] + (v^-3)*T[1] + (v^-3)
EXAMPLES:
We start by creating a Iwahori-Hecke algebra together with the three bases for these algebras that are currently supported:
sage: R.<v> = LaurentPolynomialRing(QQ, 'v') sage: H = IwahoriHeckeAlgebra('A3', v**2) sage: T = H.T() sage: C = H.C() sage: Cp = H.Cp()
It is also possible to define these three bases quickly using the
inject_shorthands()
method.Next we create our generators for the \(T\)-basis and do some basic computations and conversions between the bases:
sage: T1,T2,T3 = T.algebra_generators() sage: T1 == T[1] True sage: T1*T2 == T[1,2] True sage: T1 + T2 T[1] + T[2] sage: T1*T1 -(1-v^2)*T[1] + v^2 sage: (T1 + T2)*T3 + T1*T1 - (v + v^-1)*T2 T[3,1] + T[2,3] - (1-v^2)*T[1] - (v^-1+v)*T[2] + v^2 sage: Cp(T1) v*Cp[1] - 1 sage: Cp((v^1 - 1)*T1*T2 - T3) -(v^2-v^3)*Cp[1,2] + (v-v^2)*Cp[1] - v*Cp[3] + (v-v^2)*Cp[2] + v sage: C(T1) v*C[1] + v^2 sage: p = C(T2*T3 - v*T1); p v^2*C[2,3] - v^2*C[1] + v^3*C[3] + v^3*C[2] - (v^3-v^4) sage: Cp(p) v^2*Cp[2,3] - v^2*Cp[1] - v*Cp[3] - v*Cp[2] + (1+v) sage: Cp(T2*T3 - v*T1) v^2*Cp[2,3] - v^2*Cp[1] - v*Cp[3] - v*Cp[2] + (1+v)
In addition to explicitly creating generators, we have two shortcuts to basis elements. The first is by using elements of the underlying Coxeter group, the other is by using reduced words:
sage: s1,s2,s3 = H.coxeter_group().gens() sage: T[s1*s2*s1*s3] == T[1,2,1,3] True sage: T[1,2,1,3] == T1*T2*T1*T3 True
Todo
Implement multi-parameter Iwahori-Hecke algebras together with their Kazhdan-Lusztig bases. That is, Iwahori-Hecke algebras with (possibly) different parameters for each conjugacy class of simple reflections in the underlying Coxeter group.
Todo
When given “generic parameters” we should return the generic Iwahori-Hecke algebra with these parameters and allow the user to work inside this algebra rather than doing calculations behind the scenes in a copy of the generic Iwahori-Hecke algebra. The main problem is that it is not clear how to recognise when the parameters are “generic”.
-
sage.algebras.iwahori_hecke_algebra.
IwahoriHeckeAlgebra_nonstandard
¶ This is a class which is used behind the scenes by
IwahoriHeckeAlgebra
to compute the Kazhdan-Lusztig bases. It is not meant to be used directly. It implements the slightly idiosyncratic (but convenient) Iwahori-Hecke algebra with two parameters which is defined over the Laurent polynomial ring \(\ZZ[u,u^{-1},v,v^{-1}]\) in two variables and has quadratic relations:\[(T_r - u)(T_r + v^2/u) = 0.\]The point of these relations is that the product of the two parameters is \(v^2\) which is a square in \(\ZZ[u,u^{-1},v,v^{-1}]\). Consequently, the Kazhdan-Lusztig bases are defined for this algebra.
More generally, if we have a Iwahori-Hecke algebra with two parameters which has quadratic relations of the form:
\[(T_r - q_1)(T_r - q_2) = 0\]where \(-q_1 q_2\) is a square then the Kazhdan-Lusztig bases are well-defined for this algebra. Moreover, these bases be computed by specialization from the generic Iwahori-Hecke algebra using the specialization which sends \(u \mapsto q_1\) and \(v \mapsto \sqrt{-q_1 q_2}\), so that \(v^2 / u \mapsto -q_2\).
For example, if \(q_1 = q = Q^2\) and \(q_2 = -1\) then \(u \mapsto q\) and \(v \mapsto \sqrt{q} = Q\); this is the standard presentation of the Iwahori-Hecke algebra with \((T_r - q)(T_r + 1) = 0\). On the other hand, when \(q_1 = q\) and \(q_2 = -q^{-1}\) then \(u \mapsto q\) and \(v \mapsto 1\). This is the normalized presentation with \((T_r - v)(T_r + v^{-1}) = 0\).
Warning
This class uses non-standard parameters for the Iwahori-Hecke algebra and are related to the standard parameters by an outer automorphism that is non-trivial on the \(T\)-basis.
-
sage.algebras.iwahori_hecke_algebra.
index_cmp
(x, y)¶ Compare two term indices
x
andy
by Bruhat order, then by word length, and then by the generic comparison.EXAMPLES:
sage: from sage.algebras.iwahori_hecke_algebra import index_cmp sage: W = WeylGroup(['A',2,1]) sage: x = W.from_reduced_word([0,1]) sage: y = W.from_reduced_word([0,2,1]) sage: x.bruhat_le(y) True sage: index_cmp(x, y) 1
-
sage.algebras.iwahori_hecke_algebra.
normalized_laurent_polynomial
(R, p)¶ Return a normalized version of the (Laurent polynomial)
p
in the ringR
.Various ring operations in
sage
return an element of the field of fractions of the parent ring even though the element is “known” to belong to the base ring. This function is a hack to recover from this. This occurs somewhat haphazardly with Laurent polynomial rings:sage: R.<q>=LaurentPolynomialRing(ZZ) sage: [type(c) for c in (q**-1).coefficients()] [<... 'sage.rings.integer.Integer'>]
It also happens in any ring when dividing by units:
sage: type ( 3/1 ) <... 'sage.rings.rational.Rational'> sage: type ( -1/-1 ) <... 'sage.rings.rational.Rational'>
This function is a variation on a suggested workaround of Nils Bruin.
EXAMPLES:
sage: from sage.algebras.iwahori_hecke_algebra import normalized_laurent_polynomial sage: type ( normalized_laurent_polynomial(ZZ, 3/1) ) <... 'sage.rings.integer.Integer'> sage: R.<q>=LaurentPolynomialRing(ZZ) sage: [type(c) for c in normalized_laurent_polynomial(R, q**-1).coefficients()] [<... 'sage.rings.integer.Integer'>] sage: R.<u,v>=LaurentPolynomialRing(ZZ,2) sage: p=normalized_laurent_polynomial(R, 2*u**-1*v**-1+u*v) sage: ui=normalized_laurent_polynomial(R, u^-1) sage: vi=normalized_laurent_polynomial(R, v^-1) sage: p(ui,vi) 2*u*v + u^-1*v^-1 sage: q= u+v+ui sage: q(ui,vi) u + v^-1 + u^-1