Opened 5 years ago

Closed 4 years ago

Last modified 4 years ago

#14261 closed enhancement (fixed)

Iwahori-Hecke algebra with several bases

Reported by: brant Owned by: sage-combinat
Priority: major Milestone: sage-5.13
Component: combinatorics Keywords: Iwahori Hecke algebra, days45
Cc: sage-combinat, aschilling, andrew.mathas, sam, zabrocki Merged in: sage-5.13.beta1
Authors: Brant Jones, Travis Scrimshaw, Andrew Mathas Reviewers: Andrew Mathas, Brant Jones, Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #13735 #14014 #14678 #14516 #15257 Stopgaps:

Description (last modified by tscrim)

Set up the algebra to handle multiple bases; implemented the Kazhdan--Lusztig basis.

This is a follow up to ticket #7729.

See http://wiki.sagemath.org/HeckeAlgebras for some design discussion.


Apply:

Attachments (7)

trac_14261_iwahori_hecke.patch (31.0 KB) - added by brant 5 years ago.
trac_14261_a_few_fixes_dg.patch (3.1 KB) - added by darij 4 years ago.
not a review
trac_14261-alt_interface-ts.patch (28.5 KB) - added by tscrim 4 years ago.
trac_14261-term_cmp-ts.patch (2.8 KB) - added by tscrim 4 years ago.
trac_14261-alt_interface-review--am.patch (115.0 KB) - added by andrew.mathas 4 years ago.
Fixing a typo
trac_14261-iwahori_hecke-review--am.patch (10.6 KB) - added by andrew.mathas 4 years ago.
Fixes some documentaton and some issues in nil_coxeter and new_kschur
trac_14261-iwahori_hecke-ts.patch (122.1 KB) - added by tscrim 4 years ago.
With fixed long time tests

Download all attachments as: .zip

Change History (90)

Changed 5 years ago by brant

comment:1 follow-up: Changed 5 years ago by tscrim

  • Authors changed from Brant Jones to Brant Jones, Travis Scrimshaw
  • Cc aschilling andrew.mathas added
  • Status changed from new to needs_review

Hey Brant,

I've uploaded a new version of the patch which reworks the implementation to follow the WithRealizations API and deprecates the IwahoriHeckeAlgebraT class. If it wasn't ready for review, I think it now is.

Best,
Travis

comment:2 Changed 5 years ago by tscrim

  • Description modified (diff)

I should also state that I had to upload a new version of the patch because Brant's patch did not apply on 5.9 due to the changes in the doc. Also for got this.

For patchbot:

Apply: trac_14261-iwahori_hecke-ts.patch

comment:3 Changed 5 years ago by tscrim

New version which also adds bar involution on the T_basis and some tweaks to the documentation.

For patchbot:

Apply: trac_14261-iwahori_hecke-ts.patch

comment:4 Changed 5 years ago by andrew.mathas

A few comments:

  • I think that it is a little dangerous implementing the Kazhdan-Lusztig C'-basis and calling it the C-basis. The documentation says clearly that this is the C'-basis but these names have been in use for 30+ years at this point so I think at the minimum you need to warn people about this. (This is even though I agree that KL got the names of these two bases "wrong":)
  • As the code is essentially the same, it would be good to implement both KL C-basis and the KL C'-basis. This would solve the problem above but it also runs into the issue of what to call the C'-basis. Perhaps use C_basis and Cp_basis?
  • Having just said that the code is 'the same' in terms of caching it would be better to implement the C'-basis using the observation that C_x' = \alpha(C_x), where \alpha is the Z-linear ring automorphism of the Hecke algebra which sends q1/2} to -q-1/2 and Tx to (-1)\ell(x)q-1/2\ell(x)Tx.
Last edited 5 years ago by andrew.mathas (previous) (diff)

comment:5 Changed 5 years ago by tscrim

So which would you call the KL basis, C or C' (I believe calling [one of these] the KL is fairly standard)? I think the best name should be C_prime_basis since it is explicit, but we can have Cp and C_prime as shortcuts.

I'll also implement the ring automorphism \alpha and implement the C basis in the next version. Thanks for looking at this Andrew.

comment:6 Changed 5 years ago by nthiery

It's probably not necessary to put the _basis suffix. Elsewhere, we use Sym.s, Sym.p and so on and not Sym.s_basis.

Cheers,

Nicolas

comment:7 Changed 5 years ago by tscrim

  • Status changed from needs_review to needs_work
  • Work issues set to T <-> C basis map

New version which implements both the C and C' bases, removed the _basis suffix, and implements the Hecke involution Andrew described above as hecke_involution() to elements in the T basis. I choose the call the C' basis the Kazhdan-Lusztig since this is the bar invariant basis. However going between the C and T currently has a problem which I'm trying to work out; in particular, I believe the T -> C is wrong but the C -> T is correct.

comment:8 Changed 5 years ago by tscrim

  • Status changed from needs_work to needs_review

I fixed the problem and added some more doctests and added hecke_involution() and bar() to elements in the C and C' bases. Ready for review again.

comment:9 Changed 5 years ago by tscrim

  • Work issues T <-> C basis map deleted

comment:10 Changed 5 years ago by tscrim

This might need rebasing over #14014 since I believe that changes the order of the elements in the Weyl group which might affect the output order of our expressions. Also it seems like #14014 is almost done.

comment:11 Changed 4 years ago by tscrim

  • Dependencies set to #14014

Rebased over #14014.

For patchbot:

Apply: trac_14261-iwahori_hecke-ts.patch

comment:12 Changed 4 years ago by tscrim

  • Dependencies changed from #14014 to #13735 #14014

Also rebased over #13735.

comment:13 Changed 4 years ago by tscrim

  • Dependencies changed from #13735 #14014 to #13735 #14014 #14678

Rebased over #14678 (trivial: some fuzz).

For patchbot:

Apply: trac_14261-iwahori_hecke-ts.patch

Last edited 4 years ago by tscrim (previous) (diff)

comment:14 Changed 4 years ago by nthiery

Hi!

I got a time out yesterday while running all long tests. It's likely that the associativity tests in the TestSuite? are pretty expensive; maybe those should be skipped and run separately on some explicitly passed elements; something like:

    sage: TestSuite(C).run(skip=["_test_associativity"])
    sage: C._test_associativity(elements=[...])

comment:15 Changed 4 years ago by tscrim

They (also distributivity and prod) took so long because the an_element() was quite big. I factored it out.

Apply: trac_14261-iwahori_hecke-ts.patch

comment:16 Changed 4 years ago by tscrim

  • Dependencies changed from #13735 #14014 #14678 to #13735 #14014 #14678 #14516

Change in index_set() due to #14516.

Apply: trac_14261-iwahori_hecke-ts.patch

comment:17 Changed 4 years ago by sam

  • Cc sam added

comment:18 Changed 4 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

Changed 4 years ago by darij

not a review

comment:19 Changed 4 years ago by darij

I've just looked into the patch to see how algebras with multiple bases are implemented; I don't really know (or care much, by now) about Hecke algebras. I've uploaded a few superficial docstring fixes.

An issue I'm not fixing but you might want to ponder about are the docstrings of bar(self) and hecke_involution(self). They pretend that these methods send the deformation variable q to q^(-1) (or q^(1/2) to q^(-1/2), which is more or less the same). But what they actually invert is not the deformation variable, but rather the indeterminates generating the Laurent polynomial ring in which the deformation variable resides. So if the deformation variable is, say, 2t, then t is sent to t^(-1), not 2t to (2t)^(-1). I don't know in how far this issue will pop up in real life, but here's an example:

sage: W.<t> = LaurentPolynomialRing(QQ)
sage: H = IwahoriHeckeAlgebra(['A',3], 2*t)
sage: T = H.T()                            
sage: T1,T2,T3 = T.algebra_generators()    
sage: T1.bar()                             
(1/2*t^-1)*T1 + (-1+1/2*t^-1)
sage: (t*T1).bar()
(1/2*t^-2)*T1 + (-t^-1+1/2*t^-2)

comment:20 follow-up: Changed 4 years ago by tscrim

Hey Darij,

Thanks for looking over the documentation. As for the q, in order to do what you're suggesting means we have to do all computations in a formal variable and then specialize. However I don't think this is the correct behavior, especially when q is a root of unity, but I don't know if the bar involution is still useful at specialized q. The problem in my mind is take q = 2 and consider the element 2, what is the bar of this, does it matter if it's 1 + 1 or 2 in ZZ or suppose to be the q?

Andrew, Dan, Brant, or someone who understands Hecke algebras better than myself, do you have any thoughts on this? Also would any of you have time to do the last (math) review of this patch?

Best,
Travis

comment:21 Changed 4 years ago by darij

Hi Travis,

You're right, the only thing we can do with 2 is leave it fixed. So the implementation is right and the docstring is wrong: the only thing we can do is invert the indeterminates; inverting the deformation parameter doesn't in general work.

Best regards,
Darij

comment:22 Changed 4 years ago by tscrim

Here's the new version of the patch with the review patch folded in which fixes errors in the basis conversions and reworks the code using the bases category to avoid some redundancy.

For patchbot:

Apply: trac_14261-iwahori_hecke-ts.patch

comment:23 follow-ups: Changed 4 years ago by andrew.mathas

Given the issues that we're having in computing the KL bases I think that we need some basic tests like:

    sage: T(Cp(1))
    v^-1*Cp1 + v^-1
    sage: T(C(1))
    v^-1*Cp1 - v
    sage: C(Cp(1))
    C1 + (v+v^-1)
    sage: Cp(C(1))
    Cp1 + (-v-v^-1)

I think that there also should be long tests like:

    sage: forall( C(x)==C(T(x)) for x in W )
    true
    sage: forall( C(x)==C(Cp(x)) for x in W )
    true
    sage: forall( Cp(x)==Cp(T(x)) for x in W )
    true
    sage: forall( Cp(x)==Cp(C(x)) for x in W )
    true

where W is at least Sym(4) or of type B2 or ...

As there is an independent implementation of the KL-polys inside sage (I think???) it should also be possible to do something like:

    sage: T(Cp(x)) == v^-x.length()*sum( KLPoly(y,x)*T(y) for y in W)

Apologies but I don't know the right syntax here.

comment:24 in reply to: ↑ 20 Changed 4 years ago by andrew.mathas

Replying to tscrim:

Hey Darij,

Thanks for looking over the documentation. As for the q, in order to do what you're suggesting means we have to do all computations in a formal variable and then specialize. However I don't think this is the correct behavior, especially when q is a root of unity, but I don't know if the bar involution is still useful at specialized q. The problem in my mind is take q = 2 and consider the element 2, what is the bar of this, does it matter if it's 1 + 1 or 2 in ZZ or suppose to be the q?

Andrew, Dan, Brant, or someone who understands Hecke algebras better than myself, do you have any thoughts on this? Also would any of you have time to do the last (math) review of this patch?

Best,
Travis

The correct way of doing this is to work with an indeterminant/formal variable to compute the KL-basis elements and then specialise. The bar involution really only makes sense when q is generic.

Andrew

comment:25 in reply to: ↑ 23 Changed 4 years ago by aschilling

Once you install coxeter3 with

sage -i http://sage.math.washington.edu/home/nthiery/coxeter3-1.1.spkg

you can get KL polynomials via

    sage: from sage.libs.coxeter3.coxeter import get_CoxGroup as CoxGroup
    sage: W = CoxGroup(['A',2])
    sage: W([]).kazhdan_lusztig_polynomial([1,2,1])

Anne

comment:26 in reply to: ↑ 23 Changed 4 years ago by andrew.mathas

..and I guess there should also be some tests

sage: forall( C(x)==C(x).bar() for x in W)
true
sage: forall( Cp(x)==Cp(x).bar() for x in W)
true

comment:27 Changed 4 years ago by andrew.mathas

  • Reviewers changed from Andrew Mathas?, Dan Bump? to Andrew Mathas, Dan Bump?

I know I talked with Nicolas about this earlier, and he disagreed, but I think that the current syntax is not ideal. I'd rather have something like:

sage: H.C(1)
C1
sage: H.T(H.Cp(1))
v^-1T1+v^-1

The current extra layer of bracketting, together with the special use of [] verus () for indexes and algebra elements, I find counterintuititive. By making H.C() etc a hook to the actual basis class it maybe possible to do better than the current syntax?

(Btw, I tried using H.inject_shorhands() but this just gave an error message.)

The syntax for defining the Hecke algebra itself also strikes me as being a little OTT:

sage: H = IwahoriHeckeAlgebra(['A',3], v^2, -1, v, 1)

Is there a way of simplifying this? For example, from memory chevie computes the KL bases internally using an indeterminant and then specialised back to the square root of the Hecke parameter.

comment:28 follow-up: Changed 4 years ago by tscrim

  • Status changed from needs_review to needs_work
  • Work issues set to KL polynomials

Okay here's the version which has the correct bases, but I'm not getting the correct KL polynomials. The question becomes is this correct and KL polynomials in Sage and Coxeter3 wrong or vice versa. Hand computations are needed.

For patchbot:

Apply: trac_14261-iwahori_hecke-ts.patch

comment:29 in reply to: ↑ 28 ; follow-up: Changed 4 years ago by aschilling

Replying to tscrim:

Okay here's the version which has the correct bases, but I'm not getting the correct KL polynomials. The question becomes is this correct and KL polynomials in Sage and Coxeter3 wrong or vice versa. Hand computations are needed.

Sage has two KL polynomial implementations. The other one is by Dan Bump:

            sage: W = WeylGroup("B3",prefix="s")
            sage: [s1,s2,s3]=W.simple_reflections()
            sage: R.<q>=LaurentPolynomialRing(QQ)
            sage: KL=KazhdanLusztigPolynomial(W,q)
            sage: KL.P(s2,s3*s2*s3*s1*s2)
            q + 1

It is unlikely that both are wrong!

Anne

comment:30 Changed 4 years ago by tscrim

I'm also suspecting it's something with the code, but everything seems to be working code-wise...I'm going to run some more tests too.

Here's a second patch which changes the interface so that you can just input q1 and sqrt_q1 without having to worry about q2:

sage: R.<v> = LaurentPolynomialRing(QQ)
sage: H = IwahoriHeckeAlgebra(['A',3], v^2, v)

For patchbot:

Apply: trac_14261-iwahori_hecke-ts.patch, trac_14261-alt_interface-ts.patch

comment:31 in reply to: ↑ 29 Changed 4 years ago by andrew.mathas

Replying to aschilling:

Replying to tscrim :

Okay here's the version which has the correct bases, but I'm not getting the correct KL polynomials. The question becomes is this correct and KL polynomials in Sage and Coxeter3 wrong or vice versa. Hand computations are needed.

Sage has two KL polynomial implementations. The other one is by Dan Bump: sage: W = WeylGroup ("B3",prefix="s") sage: [s1,s2,s3]=W.simple_reflections() sage: R.<q>=LaurentPolynomialRing (QQ) sage: KL=KazhdanLusztigPolynomial (W,q) sage: KL.P(s2,s3*s2*s3*s1*s2) q + 1 It is unlikely that both are wrong! Anne

Hi Travis and Anne,

This is the first interesting KL-polynomial and the polynomial is 1+q=1+v^2. So the result being returned by the basis code is correct and the result being returned by the KL.poly sum is wrong. The problem is that KL.P is returning a polynomial in v whereas in the sum we want a polynomial in v^2. So all that needs to be done to fix this is make KL.P return a polynomial in v^2.

Andrew

comment:32 Changed 4 years ago by tscrim

And there's option C: I'm being an idiot. Thank you Andrew. Here's the patch with the corrected docstrings (and most of the all tests marked as # long time).

Next question, is anyone against my proposed interface? I don't think I can manage to get C(1) to return the same as C[1] due to the coercion model. IMO, I don't see this as confusing since the syntax is different, and since there is different syntax, we are okay with different output.

For patchbot:

Apply: trac_14261-iwahori_hecke-ts.patch, trac_14261-alt_interface-ts.patch

Changed 4 years ago by tscrim

comment:33 Changed 4 years ago by tscrim

  • Reviewers changed from Andrew Mathas, Dan Bump? to Andrew Mathas, Brant Jones, Travis Scrimshaw
  • Status changed from needs_work to needs_review
  • Work issues KL polynomials deleted

Here are the new versions of the patches with the changes Brant and I discussed via e-mail which changes the output of the C and Cp bases.

For patchbot:

Apply: trac_14261-iwahori_hecke-ts.patch, trac_14261-alt_interface-ts.patch

comment:34 follow-ups: Changed 4 years ago by andrew.mathas

I'm part way through writing a review patch. Mostly I have just been expanding on the documentation (and hopefully improving it). In particular, I have added Iwahori-Hecke algebras to the algebra chapter of the reference manual, as it didn't seem to exist anywhere else.

There is one significant issue that needs to be addressed: currently the code accepts two parameters q1 and q2 and defines the algebra with generators {T_s|s\in S} and relations (T_s-q1)(T_s-q2)=0 together with the braid relations. I am unsure how to define the bar involution for such parameters.

What the code currently does is invert all of the generators of the base ring. This is probably the right thing to do if q1 and q2 are powers of generators of the base ring -- although even this is not clear because we could have q1=v^2 and but be working with the Hecke algebra over Z[v,w], so that we would probably want \bar[w}=w. Of course, I can't image why one would ever want to do this...

A less extreme (and more natural), example is when q1=a^2, q2=b^2 and a and b are not algebraically independent. In this case, this bar involuton on the base ring will almost never extend to a ring involution on te Hecke algebra.

What is cool about the current implementation is that it works correctly with parameters (q1,q2) being either (v^2,-1) or (v,-v^-1). What is less cool is that it will be wrong in the senarious above and, more seriously, it gives incorrect answers when given parameters (1,-1) which corresponds to the group ring ZW:

sage: H = IwahoriHeckeAlgebra(['A',3], 1,1)  
sage: H.inject_shorthands()
Injecting C as shorthand for Iwahori-Hecke algebra of type A3 in 1,-1 over Integer Ring in the C basis
Injecting Cp as shorthand for Iwahori-Hecke algebra of type A3 in 1,-1 over Integer Ring in the Kazhdan-Lusztig basis
Injecting T as shorthand for Iwahori-Hecke algebra of type A3 in 1,-1 over Integer Ring in the standard basis
sage: T(Cp(1))
1

The underlying problem is that the bar involution really only makes sense in the generic case and currently there is no checking for this. On the other hand, the Kazhdan-Lusztig bases do make sense whenever the squre root of the prameters lives in the base ring as we can compute the KL bases over Z[v,v^-1] and then specialise v^2 to q. In particular, the KL bases make sense for the integral groups rings ZW.

I can think of a couple of solutions:

  • Leave everything as it is.
  • Only allow the KL bases to be implemenetd in the generic case.
  • Implement a generic Hecke algebra behind the scene and compute the KL basis here, together with transition matrices, and then specialise these results into the non-generic Hecke algebras whenever the square roots of the parameters are (testably) well-defined.

I don't like the first option because the current behaviour is mathematically incorrect in important examples. Nor do I like the second option because working with the KL bases of the group algebra is a natural thing to want to do. Therefore, I think that the last option is the way to go.

Please let me know what you think.

Here are a few other less important issues that I have come across:

  • I am confused by the one_basis method of all of the bases: why does this return the identity element of the corresponding Coxeter group? Initially I thought that this would return the identity element of the Hecke algebra with respet to the current basis (which is implemented asT.one()). If we really need a shorthand for the identity element of the group shouldn't the method be called something like group_identity?
  • Similarly, the method is_field strikes me as being strange: the Hecke algebra is a field if only if the Coxeter group has rank zero and the base ring is a field. Rather than being a method of the Hecke algebra this should be (and is) a method of the base ring of the Hecke algebra.
  • I think that the names for the bases are all too long to be useful and that something shorter like "X-basis of Iwahori-Hecke algebra" or "X-basis of Iwahori-Hecke algebra of type Y" feasible? Compare these with:
    Iwahori-Hecke algebra of type A3 in v^2,-1 over Univariate Laurent Polynomial Ring in v over Rational Field in the C basis
    Iwahori-Hecke algebra of type A3 in v^2,-1 over Univariate Laurent Polynomial Ring in v over Rational Field in the Kazhdan-Lusztig basis
    Iwahori-Hecke algebra of type A3 in v^2,-1 over Univariate Laurent Polynomial Ring in v over Rational Field in the standard basis
    

Unless anyone objects, in my review patch I will remove the is_field method, rename (or delete?) the one_basis method and shorten the basis names.

In the bsence of better suggesstions I will also have a go at implementing a generic algebra in the background.

comment:35 in reply to: ↑ 34 ; follow-up: Changed 4 years ago by tscrim

Thank you for reviewing this ticket Andrew.

Replying to andrew.mathas:

I'm part way through writing a review patch. Mostly I have just been expanding on the documentation (and hopefully improving it). In particular, I have added Iwahori-Hecke algebras to the algebra chapter of the reference manual, as it didn't seem to exist anywhere else.

Yes, this should be done.

There is one significant issue that needs to be addressed: currently the code accepts two parameters q1 and q2 and defines the algebra with generators {T_s|s\in S} and relations (T_s-q1)(T_s-q2)=0 together with the braid relations. I am unsure how to define the bar involution for such parameters.

...

The underlying problem is that the bar involution really only makes sense in the generic case and currently there is no checking for this. On the other hand, the Kazhdan-Lusztig bases do make sense whenever the squre root of the prameters lives in the base ring as we can compute the KL bases over Z[v,v^-1] and then specialise v^2 to q. In particular, the KL bases make sense for the integral groups rings ZW.

I can think of a couple of solutions:

  • Leave everything as it is.
  • Only allow the KL bases to be implemenetd in the generic case.
  • Implement a generic Hecke algebra behind the scene and compute the KL basis here, together with transition matrices, and then specialise these results into the non-generic Hecke algebras whenever the square roots of the parameters are (testably) well-defined.

I'm slightly hesitant about option 3 (implementing a generic Hecke algebra), and it's probably due to my lack of expertise, but does it always work for specializing to roots of unity? Or do problems just arise with the representation theory? If it's okay, then I'm for option 3.

Actually, that made me have another (scarier) thought, does anyone know if this works for fields of positive characteristic? If not or we don't know, I think we should put that in the documentation somewhere that we assume the base ring has characteristic 0.

Here are a few other less important issues that I have come across:

  • I am confused by the one_basis method of all of the bases: why does this return the identity element of the corresponding Coxeter group? Initially I thought that this would return the identity element of the Hecke algebra with respet to the current basis (which is implemented asT.one()). If we really need a shorthand for the identity element of the group shouldn't the method be called something like group_identity?

This is correct; it is suppose to return the index of basis element for the Hecke's algebra's (multiplicative) identity. It's something needed for CombinatorialFreeModule (at least, I'm pretty sure).

  • Similarly, the method is_field strikes me as being strange: the Hecke algebra is a field if only if the Coxeter group has rank zero and the base ring is a field. Rather than being a method of the Hecke algebra this should be (and is) a method of the base ring of the Hecke algebra.

I'm not really opposed to removing it, but I'm thinking it should be in there for consistency (with perhaps modified behavior).

  • I think that the names for the bases are all too long to be useful and that something shorter like "X-basis of Iwahori-Hecke algebra" or "X-basis of Iwahori-Hecke algebra of type Y" feasible? Compare these with:
    Iwahori-Hecke algebra of type A3 in v^2,-1 over Univariate Laurent Polynomial Ring in v over Rational Field in the C basis
    Iwahori-Hecke algebra of type A3 in v^2,-1 over Univariate Laurent Polynomial Ring in v over Rational Field in the Kazhdan-Lusztig basis
    Iwahori-Hecke algebra of type A3 in v^2,-1 over Univariate Laurent Polynomial Ring in v over Rational Field in the standard basis
    

I don't like removing the base ring in the representation (the Univariate Laurent Polynomial Ring in v over Rational Field part) since it helps distinguish the Hecke algebras. The in the X basis part is a standard paradigm from other WithRealization objects such as symmetric functions.

Last edited 4 years ago by tscrim (previous) (diff)

comment:36 in reply to: ↑ 35 ; follow-up: Changed 4 years ago by andrew.mathas

Replying to tscrim:

Thank you for reviewing this ticket Andrew.

Well, I haven't actually finished a review yet! Thanks for getting back to me.

I'm slightly hesitant about option 3 (implementing a generic Hecke algebra), and it's probably due to my lack of expertise, but does it always work for specializing to roots of unity? Or do problems just arise with the representation theory? If it's okay, then I'm for option 3. Actually, that made me have another (scarier) thought, does anyone know if this works for fields of positive characteristic? If not or we don't know, I think we should put that in the documentation somewhere that we assume the base ring has characteristic 0.

The KL bases are defined over Z[q^{1/2},q^{-1/2}] so you can specialise them to ANY ring provided these square roost exist. You can't, however, compute these bases over any ring becaue the bar involution will not be defined in general. Therefore, one really SHOULD compute them generically and then specialise.

To be explicit, the group ring RW of the Coxeter group has a well-defined KL basis for any ring R, however, you can't "see" the KL bases of RW inside the group ring. The only way to compute the KL bases or RW is to do it inside the generic Hecke algebra and then specialise. Notice also that even though the KL bases are defined for RW the bar involution is NOT defined on RW, so non-generic Hecke algebras should not have a method for the bar involution either.

The KL bases also work in the root of unity cases...it is more that no one has found a good use for them yet.

This is correct [about one_basis]; it is suppose to return the index of basis element for the Hecke's algebra's (multiplicative) identity. It's something needed for CombinatorialFreeModule (at least, I'm pretty sure).

I don't believe this. Combinaorial modules can be indexed anything so it seems unlikely that they would require something in the index set to be a multiplicative identity. In the code one_basis is used as a shortcut to get to things like T(1).

I'm not really opposed to removing it, but I'm thinking it should be in there for consistency (with perhaps modified behavior).

Is is_field a default method for an algebra? Most algebras are not fields so this struck me as being a strange question to ask mathematically. If you accept this then you should agree that it is a strange method for an algebra. (But perhaps it is just me who is strange!:)

I don't like removing the base ring in the representation (the Univariate Laurent Polynomial Ring in v over Rational Field part) since it helps distinguish the Hecke algebras. The in the X basis part is a standard paradigm from other WithRealization objects such as symmetric functions.

I agree that this could be useful but I always err on the side of readabiltly and ease of use.

I will try and incorporate some or all of the above into the review patch and get it back to you tomorrow (possibly optimistic). Going via the generic algebra turns out to be a minor rearrangement of code (I think), so it shoudn't be too hard - I hope!

comment:37 in reply to: ↑ 36 Changed 4 years ago by tscrim

Replying to andrew.mathas:

Replying to tscrim:

Thank you for reviewing this ticket Andrew.

Well, I haven't actually finished a review yet! Thanks for getting back to me.

I note the tense of the verb :P

I'm slightly hesitant about option 3 (implementing a generic Hecke algebra), and it's probably due to my lack of expertise, but does it always work for specializing to roots of unity? Or do problems just arise with the representation theory? If it's okay, then I'm for option 3. Actually, that made me have another (scarier) thought, does anyone know if this works for fields of positive characteristic? If not or we don't know, I think we should put that in the documentation somewhere that we assume the base ring has characteristic 0.

The KL bases are defined over Z[q^{1/2},q^{-1/2}] so you can specialise them to ANY ring provided these square roost exist. You can't, however, compute these bases over any ring becaue the bar involution will not be defined in general. Therefore, one really SHOULD compute them generically and then specialise.

To be explicit, the group ring RW of the Coxeter group has a well-defined KL basis for any ring R, however, you can't "see" the KL bases of RW inside the group ring. The only way to compute the KL bases or RW is to do it inside the generic Hecke algebra and then specialise. Notice also that even though the KL bases are defined for RW the bar involution is NOT defined on RW, so non-generic Hecke algebras should not have a method for the bar involution either.

The KL bases also work in the root of unity cases...it is more that no one has found a good use for them yet.

Then I'm for it. I'm guessing we only would want the generic structure for the basis transitions and let the bar and Hecke involution methods fail as necessary (with proper documentation of course). I'd imagine that we shouldn't see too big (if any) of a speed penality doing it this way.

This is correct [about one_basis]; it is suppose to return the index of basis element for the Hecke's algebra's (multiplicative) identity. It's something needed for CombinatorialFreeModule (at least, I'm pretty sure).

I don't believe this. Combinaorial modules can be indexed anything so it seems unlikely that they would require something in the index set to be a multiplicative identity. In the code one_basis is used as a shortcut to get to things like T(1).

It's useful in the to_*_basis() methods because their argument is given in terms of an indexing element. Only at one place in the code did T(T.one_basis()) get used and could be turned into T.one(). If you're still thinking of changing this to one() (which you do need to implement otherwise), then we'll see if something else breaks (and you might consider asking Nicolas about it).

I'm not really opposed to removing it, but I'm thinking it should be in there for consistency (with perhaps modified behavior).

Is is_field a default method for an algebra? Most algebras are not fields so this struck me as being a strange question to ask mathematically. If you accept this then you should agree that it is a strange method for an algebra. (But perhaps it is just me who is strange!:)

Since the class Algebra inherits from Ring, it does have this method. However the category Rings, which is a super-category of (unital, associative) Algebras, does not have an is_field method (I think because you're suppose to test it like R in Fields(), but don't quote me on that), so it's okay to remove it.

Now down the rabbit hole: as to it being strange, I don't have the experience to say. I do agree that most algebras are not fields, but then again, so are most rings. However isn't the fraction field of an algebra also an algebra?

I don't like removing the base ring in the representation (the Univariate Laurent Polynomial Ring in v over Rational Field part) since it helps distinguish the Hecke algebras. The in the X basis part is a standard paradigm from other WithRealization objects such as symmetric functions.

I agree that this could be useful but I always err on the side of readabiltly and ease of use.

IMO the string representations of parents are mainly used to remind us what they are or to identify them. Leaving off the base ring makes it harder to achieve this. If you're still wanting more readability, perhaps a global option is in order with the default being the more descriptive string (although we might need to be careful about the hash...)?

I will try and incorporate some or all of the above into the review patch and get it back to you tomorrow (possibly optimistic). Going via the generic algebra turns out to be a minor rearrangement of code (I think), so it shoudn't be too hard - I hope!

I don't think it should be difficult. Thank you Andrew.

comment:38 in reply to: ↑ 34 ; follow-up: Changed 4 years ago by nthiery

Replying to andrew.mathas:

Here are a few other less important issues that I have come across:

  • I am confused by the one_basis method of all of the bases: why does this return the identity element of the corresponding Coxeter group? Initially I thought that this would return the identity element of the Hecke algebra with respet to the current basis (which is implemented asT.one()). If we really need a shorthand for the identity element of the group shouldn't the method be called something like group_identity?

From the documentation of one_basis in AlgebrasWithBasis? (now in Algebras.Unital.WithBasis?.ParentMethods?.one_basis):

                When the one of an algebra with basis is an element of
                this basis, this optional method can return the index of
                this element. This is used to provide a default
                implementation of :meth:`.one`, and an optimized default
                implementation of :meth:`.from_base_ring`.

So just a little standard shortcut which furthermore gives the system a bit of information that can be used for some optimizations.

comment:39 follow-up: Changed 4 years ago by nthiery

Just a tiny bit of food for thoughts: In symmetric functions, we are facing a similar issue when it comes to implementing the plethysm: one needs to know which parameters in the ground field are of rank 1 (in which case p_k(x)=xk) or of rank 0 (in which case p_k(x)=x). And of course specializing a rank 1 parameter to a complex number does not play well with plethysm.

The approach we took in MuPAD-Combinat for this particular issue (and, I think, should be implemented in Sage) is to have the user specify explicitly what the plethysm does on the ground field, and this worked pretty well.

In practice the user had to provide a glorified field with a plethysm method. This was typically "ExpressionField?" (roughly the equivalent of Sage's symbolic ring) glorified as the facade parent "ExpressionFieldWithDegreeOneElement?(variables)" that added a "plethysm" method which did an appropriate substitution on the variables. See e.g. p. 4 of [1].

So one could imagine a similar approach where: if the user wants the full featured Hecke algebra, (s)he would have to provide explicitly a method implementing the bar involution on the ground field (assuming of course it actually makes sense!). This would give the flexibility to handle several cases: free parameters without doing nonsense like inverting other variables in the ground field, parameters on the unit circle (taking complex conjugation as bar involution), ...

Of course, a default implementation of the bar involution could be automatically provided in the easy cases. One point to discuss would be the interface: do we want to create a glorified field with a bar method, or just provide the bar method separately.

Again, just some food for thoughts; I am not saying it's necessarily the right approach for the problem at hand.

Cheers,

Nicolas

[1] http://mupad-combinat.sourceforge.net/Papers/TutorialSymFcts.pdf

comment:40 in reply to: ↑ 39 ; follow-ups: Changed 4 years ago by andrew.mathas

Replying to nthiery:

So one could imagine a similar approach where: if the user wants the full featured Hecke algebra, (s)he would have to provide explicitly a method implementing the bar involution on the ground field (assuming of course it actually makes sense!).

Hi Nicolas,

Unfortunatey, having user supplied bar involution isn't going to work here. For example, it makes perfect sense to talk about the Kazhdan-Lusztig bases of the group ring ZW (by specialisation) BUT you can can't define an appropriate bar involution on ZW. The point is that you can't detect the KL-bases inside ZW: to find them you have to work generically and then specialise -- that is, you have to work in a completely different (but related) algebra to define these bases.

It turns out that if you have a Hecke algebra with quadratic relations of the form

(T_r-a)(T_r-b)=0

such that the square root of -ab is a well-defined element of the ground ring then this Hecke algebra has well-defined Kazhdan-Lusztig bases (not sure if this is written down anywhere but, nonetheless, it is true).

To define the KL-bases one has to go to a suitable generic suitation and then specialize. One way of doing this is to work with the Hecke algebra defined over the Laurent polynomial ring Z[u,u^-1,v,v^-1] which has quadratic relations

(T_r-u)(T_r+v^2u^-1)=0

and then specialize u to a and v to \sqrt{-ab} -- so that, -v^2/u maps to b. There is a bar involution on this "generic" Hecke algebra which sends u to u^-1, v to v^-1 and T_w to T_{w^{-1}}^{-1}. Moreover, there are bar invariant bases {C_w} and {C'_w} which are unique subject to a Kazhdan and Lusztig like property.

Implementing the KL-basis via this strange two parameter generic Hecke algebra behind the scenes means that the KL-bases will be defined for ZW. In addition, the KL-basis will automatically work correctly if I consider the Hecke algebra which has quadratric relations of the form (T_r-v^2)(T_r+1)=0 or of the form (T_r-v)(T_r+v^{-1})=0. From the user's point of view they will get the right bases in all of thesse cases, and more, without them needing to do anything special.

In principle I have a patch which impements this approach, but I am running into a strange inheritance issue which I don't understand. In the original patch we have an implementation of the Iwahori-Hecke algebra H, with parameters a=q1 and b=q2, using the standard structure:

class IwahoriHeckeAlgebra(Parent, UniqueRepresentation):
    class T(CombinatorialFreeModule, BindableClass):
        class Element(CombinatorialFreeModuleElement):
    class _KLHeckeBasis(CombinatorialFreeModule, BindableClass):
    class C_prime(_KLHeckeBasis):
        def to_T_basis(self, w):
            ....
    class C(_KLHeckeBasis):

Whenever the squareroot of -ab is well-defined I am attaching a "generic Hecke algebra" GH to H together with Kazhdan-Lusztig C and C' bases which are computed generically in GH then automatically specialised back to H. As the methods for converting between the KL-basis in the two H and GH are different I have created another class for the generic Hecke algebra which looks like:

class _AGenericIwahoriHeckeAlgebra(IwahoriHeckeAlgebra):
    class T(IwahoriHeckeAlgebra.T):
    class C_prime(IwahoriHeckeAlgebra.C_prime):
        def to_T_basis(self, w):
            ....
    class C(IwahoriHeckeAlgebra.C_prime):

In principle, what is supposed to happen is that everything inherits from IwahoriHeckeAlgebras and I just overwrite the basis conversion functions -- and a few other things. Everything is working exactly as I expect EXCEPT that when a "generic" method already exists in a "non-generic" basis class then it is NOT overriding the corresponding method in IwahoriHeckeAlgebra.

For example, as above, the 'C_prime' basis classes of H and GH both contain a method to_T_basis. The method in GH implicitly calls the corresponding method in GH and then specialises the result back to H. The corresponding generic method for GH implements the inductive construction of the C'-basis in terms of the T-basis. For some reason, however, both of these to_T_basis methods are the method defined in IwahoriHeckeAlegbras and the new method in _AGenericIahoriHeckeAlgebra is being ignored.

The categories etc of the various different Hecke algebras and bases all appear to be correct (and they are different for the generic and non-generic versions). I am just getting the wrong methods in the generic bases. Other "generic" methods which do not have "non-generic" counterparts, such as specialization, are working fine.

I suspect that I am running foul of the category framework somewhere and that it doesn't like the way that am trying to use inheritance above. Can anyone tell me what I am doing wrong and what I should be doing?

Andrew

Last edited 4 years ago by andrew.mathas (previous) (diff)

comment:41 in reply to: ↑ 40 ; follow-up: Changed 4 years ago by andrew.mathas

Please ignore my query above as I just worked out that my problems are all caused by the shortened versions of the class names for the bases:

    Cp = C_prime
    kazhdan_lusztig = C_prime

as defined in IwahoriHeckeAlgebras (and then inherited by my generic versions). For this reason, if nothing else, I'm inclined to delete these! I think that it s certainly a mistake to call the "real" class C_prime and then proceed to use the shortened name Cp throughout the code.

Now that I have worked out what the problem is I'll try and finalise the patch. I need to rewrite a lot of the documentation, however, so this might take some time.

As I have explained above what the patch is doing please let me know now if don't like this approach.

Andrew

Last edited 4 years ago by andrew.mathas (previous) (diff)

comment:42 in reply to: ↑ 38 ; follow-up: Changed 4 years ago by andrew.mathas

Replying to nthiery:

From the documentation of one_basis in AlgebrasWithBasis? (now in Algebras.Unital.WithBasis?.ParentMethods?.one_basis):

                When the one of an algebra with basis is an element of
                this basis, this optional method can return the index of
                this element. This is used to provide a default
                implementation of :meth:`.one`, and an optimized default
                implementation of :meth:`.from_base_ring`.

So just a little standard shortcut which furthermore gives the system a bit of information that can be used for some optimizations.

Thanks for the explanation. I think that the name one_basis is a little misleading...

comment:43 in reply to: ↑ 42 Changed 4 years ago by nthiery

Replying to andrew.mathas:

Thanks for the explanation. I think that the name one_basis is a little misleading...

Yup, that's not perfect, but it's consistent with the xxx_basis suffix of product_on_basis and all its friends: it's a way to implement "xxx" using the "basis". one_on_basis did not really make better sense, so that was reduced to one_basis.

Cheers,

Nicolas

comment:44 in reply to: ↑ 40 Changed 4 years ago by nthiery

Replying to andrew.mathas:

Unfortunatey, having user supplied bar involution isn't going to work here. For example, it makes perfect sense to talk about the Kazhdan-Lusztig bases of the group ring ZW (by specialisation) BUT you can can't define an appropriate bar involution on ZW. The point is that you can't detect the KL-bases inside ZW: to find them you have to work generically and then specialise -- that is, you have to work in a completely different (but related) algebra to define these bases.

Yes, that's what I meant above by "when it makes sense". When it does not you certainly have to go through generic/specialization.

My point is that, when it makes sense, it could be worthwhile making explicit (and customizable!) what the involution on the ground field does. In particular for potential use cases where the bar involution on the ground field is non trivial. In which case the user could provide an implementation of it to bypass the generic/specialization process.

Cheers,

Nicolas

comment:45 Changed 4 years ago by andrew.mathas

How should we print elements of the Hecke algebra?

Currently the Hecke algebra elements in different bases are printed differently:

sage: R<v> = LaurentPolynomialRing(QQ, 'v')
sage: H = IwahoriHeckeAlgebra(['A',2], v**2)
sage: H.T()[1,2,1]
T1*T2*T1
sage: H.C()[1,2,1]
C[s1*s2*s1]

I think that the default printing for the different bases should be consistent. We clearly cannot print the KL-bases as C1*C2*C1 as this is not equal to C[1,2,1].

I also think that it is good to have the (default) output being valid input so that you can cut and paste it directly back into sage. For these reasons I would prefer:

sage: H.T()[1,2,1]
T[1,2,1]
sage: H.C()[1,2,1]
C[1,2,1]

I also think this is more readable than the current output because it is easier to identify the permutation, as a Coxeter word, which indexes each basis element. Another advanatage is that it simplifies the code.

Please let me know what you think.

Last edited 4 years ago by andrew.mathas (previous) (diff)

comment:46 follow-up: Changed 4 years ago by andrew.mathas

Default parameters for the Hecke algebras

We are implementing Hecke algebras with two parameters q1 and q2. Should the corresponding quadratic relations be

(T_r-q1)(T_r-q2)=0,

as we currently have it, or should they be

(T_r-q1)(T_r+q2)=0?

There are advantages and disadvantages with both choices. I don't really care either way, but I thought that the question should be at least asked because the three "most common" choices for relations are:

(T_r-q)(T_r+1)=0           # Iwahori's original defintiion
(T_r-q)(T_r+q^-1)=0        # the best normalistion
(T_r-1)(T_r+1)=0           # the group ring of the Coxeter group

All of these are arguably more compatible with the second choice.

If no one has a strong preference either way then I will leave it as it is (choice 1).

Last edited 4 years ago by andrew.mathas (previous) (diff)

comment:47 in reply to: ↑ 46 Changed 4 years ago by nthiery

Replying to andrew.mathas:

Default parameters for the Hecke algebras

We are implementing Hecke algebras with two parameters q1 and q2. Should the corresponding quadratic relations be

(T_r-q1)(T_r-q2)=0,

as we currently have it, or should they be

(T_r-q1)(T_r+q2)=0?

There are advantages and disadvantages with both choices. I don't really care either way, but I thought that the question should be at least asked because the three "most common" choices for relations are:

(T_r-q)(T_r+1)=0           # Iwahori's original defintiion
(T_r-q)(T_r+q^-1)=0        # the best normalistion
(T_r-1)(T_r+1)=0           # the group ring of the Coxeter group

All of these are arguably more compatible with the second choice.

If no one has a strong preference either way then I will leave it as it is (choice 1).

Unsurprisingly, choice 1 is my preferred. It makes their description easy and symmetric: the two eigenvalues of the T's.

Thanks!

comment:48 in reply to: ↑ 41 ; follow-up: Changed 4 years ago by tscrim

Replying to andrew.mathas:

Please ignore my query above as I just worked out that my problems are all caused by the shortened versions of the class names for the bases:

    Cp = C_prime
    kazhdan_lusztig = C_prime

as defined in IwahoriHeckeAlgebras (and then inherited by my generic versions). For this reason, if nothing else, I'm inclined to delete these! I think that it s certainly a mistake to call the "real" class C_prime and then proceed to use the shortened name Cp throughout the code.

It shouldn't matter which one is the real class and which one is an alias. If it does, then that should be a bug with BindableClass. I'm fine with making Cp the "real" name, but I'd like at least C_prime to available since that is a natural python name (and perhaps deleting kazhdan_lusztig since it's ambiguous being the C and C' bases?).

I have no preference on the sign and the string representation. Just for the record, you can input C[s1*s2*s1].

comment:49 in reply to: ↑ 48 ; follow-up: Changed 4 years ago by andrew.mathas

Replying to tscrim:

It shouldn't matter which one is the real class and which one is an alias. If it does, then that should be a bug with BindableClass.

It was my bug rather than one in BindableClass. The problem was that I hadn't defined the shortcuts in the generic Hecke algebra class. As a result the non-generic shortcuts were being inherited and used instead of their generic replacements.

I have no preference on the sign and the string representation. Just for the record, you can input C[s1*s2*s1].

Well, only if s1 and friends have been defined:)

I have to try and finish a paper today, but hopefully I will manage to finalise this by the end of the week. Apologies for the delay.

Btw, I just noticed failing doc-test in the original patch (and in my "review"). The following is supposed to work but doesn't:

sage: G = CoxeterGroup("B2")
sage: T[G.simple_reflection(1)]

The problem is that CoxeterGroup and WeylGroup return different groups:

sage: CoxeterGroup("B2")
Permutation Group with generators [(1,3)(2,6)(5,7), (1,5)(2,4)(6,8)]
sage: WeylGroup("B2")
Weyl Group of type ['B', 2] (as a matrix group acting on the ambient space)

Does anyone know if this is fixed in some patch or reported as a bug somewhere?

We can fudge the failing doc-test by using WeylGroup instead of CoxeterGroup.

Last edited 4 years ago by andrew.mathas (previous) (diff)

comment:50 in reply to: ↑ 49 Changed 4 years ago by tscrim

Replying to andrew.mathas:

It was my bug rather than one in BindableClass. The problem was that I hadn't defined the shortcuts in the generic Hecke algebra class. As a result the non-generic shortcuts were being inherited and used instead of their generic replacements.

Ah, I see.

I have to try and finish a paper today, but hopefully I will manage to finalise this by the end of the week. Apologies for the delay.

No worries. Thanks for doing the refactoring with the generic algebras.

Btw, I just noticed failing doc-test in the original patch (and in my "review"). The following is supposed to work but doesn't:

sage: G = CoxeterGroup("B2")
sage: T[G.simple_reflection(1)]

The problem is that CoxeterGroup and WeylGroup return different groups:

sage: CoxeterGroup("B2")
Permutation Group with generators [(1,3)(2,6)(5,7), (1,5)(2,4)(6,8)]
sage: WeylGroup("B2")
Weyl Group of type ['B', 2] (as a matrix group acting on the ambient space)

Does anyone know if this is fixed in some patch or reported as a bug somewhere?

We can fudge the failing doc-test by using WeylGroup instead of CoxeterGroup.

I wouldn't necessarily call that the output is different a bug since the class of Coxeter groups is larger than the class of Weyl groups and they are constructed from different underlying spaces, and by using a different API, it's okay to expect a different output. However that the output from CoxeterGroup and WeylGroup behave differently is a bug. I'd guess that the permutation group from CoxeterGroup is not in the CoxeterGroups category is the root of the problem. I'll look into this.

Changed 4 years ago by tscrim

comment:51 Changed 4 years ago by tscrim

For the CoxeterGroup vs WeylGroup, you must have chevie installed so CoxeterGroup defaults to a permutation group implementation. Because of this, I can't test it, but it should be in the CoxeterGroups category and there should be a coercion between the different implementations of the same group.

Actually on that note, instead of passing a Cartan type to the Iwahori-Hecke algebra constructor, perhaps we should pass a Coxeter group instead.

A bug report on that note, this doesn't work for affine groups because the comparison of elements in the Coxeter groups does not always agree with the Bruhat order:

sage: G = CoxeterGroup(['A',2])
sage: s1,s2 = G.gens()
sage: G.one() < s1
False
sage: G.one() < s2
False
sage: G = CoxeterGroup(['A',2,1])
sage: s0,s1,s2 = G.gens()
sage: G.one() < s0
False
sage: G.one() < s1
True
sage: G.one() < s2
True

I've attached small patch which (crudely/proof of concept) fixes this by using the Bruhat ordering for you to fold into your review patch.

Last edited 4 years ago by tscrim (previous) (diff)

comment:52 Changed 4 years ago by andrew.mathas

  • Authors changed from Brant Jones, Travis Scrimshaw to Brant Jones, Travis Scrimshaw, Andrew Mathas

I've finally finished this "review". I had intended just to give the code a quick look over and then a positive review but the issues with computing the KL-bases in the non-generic cases changed that. For example, the previous version of the patch would have computed KL-bases for ZW which were not the expected bases. There were also some issues with documentation (both what was and wasn't written and the fact that it wasn't included in the reference manual) and places where Laurent polynomials were misbehaving badly...and I didn't like the way that it was necessary to specify the Hecke parameters and their square roots.

To fix all of these issues I ended up rewriting the patch completely (sorry!). As I foreshadowed above, the KL-bases are now done behind the scenes in a generic Hecke algebra. There is no longer any need to specify square roots as the code just figures out what to do. Here is an exerpt from the new documentation:

    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: Cp(T[1,2,1])
        q^3*Cp[1,2,1] + (-q^2)*Cp[1,2] + (-q^2)*Cp[2,1] + q*Cp[1] +
q*Cp[2] + (-1)
        sage: C(_)
        q^3*C[1,2,1] + q^4*C[1,2] + q^4*C[2,1] + 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: Cp(T[1,2,1])
        Cp[1,2,1] + (-q^-1)*Cp[1,2] + (-q^-1)*Cp[2,1] + (q^-2)*Cp[1] +
(q^-2)*Cp[2] + (-q^-3)
        sage: C(_)
        C[1,2,1] + q*C[1,2] + q*C[2,1] + 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[1,2] - Cp[2,1] + Cp[1] + Cp[2] - 1
        sage: C(_)
        C[1,2,1] + C[1,2] + C[2,1] + C[1] + C[2] + 1

    On the other hand, if the Kazhdan-Lusztig bases are not well-defined
(when
    ``-q_1q_2`` is not a square), attempting to use the Kazhdan-usztig
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_1q_2 is a square

In terms of the code there is now a new _AGenericIwahoriHeckeAlgebra class which is where all of the KL-basis calculations are really done. Elements of this class have a specialize_to method for getting back to the (possibly non-generic) Hecke algebra. The transition to the category framework is now complete with the previous element class IwahoriHeckeAlgebraElement? being subsumed into the IwahoriHeckeAlgebra? class. There is also a new normalized_laurent_polynomial function for making Laurent polynomials (and even integers) play more nicely...this seems like an awful hack, but it does seem to be necessary? (Perhaps Travis' Laurent polynomial patch removes the need for this, but things like 1/1 being rational may still cause problems?).

I have been through the documentation and tried to explain everything. I apologise for the many typos that I have no doubt introduced and I hope that what remains is passable.

One question/concern: if some one wants to work with what really is a generic Hecke algebra, say defined over Z[q,q^-1], I wonder whether the overhead in implementing the KL-bases via a hidden two variable Hecke algebra will end up being too costly. If I could see a way to detect when the parameters really are "generic" then perhaps a generic Hecke algebra could be returned in this case to avoid the duplication....but I can't for the life of me see how to detect this. Perhaps the special parameters (q_1,q_2)=(q1,-1) and (q_1,q_2)=(q,q^-1) should be treated separately?

Finally, I seem to have confused my local version of the combinat queue so I am unable to push the patch to the combinat server at the moment. Instead I'll upload the patch to trac and hope that it works -- it should be applied after the two patches currently in the queue. Two more points:

  • Nicolas suggested passing in the bar_involution as a parameter to the Hecke algebras. I haven't done this. I can't think of a case where this would be needed, but perhap it is? Whether or not this is done, the bar_involution should give an error/warning whenever the parameters are not generic as in such caes it ill return silly results. (As I said, however, I dont see how to test for "generic" parameters...perhaps just algebraic independence overhe ground ring?).
  • Travis, sorry, but I haven't looked at all at your term_cmp patch.

Andrew

ps. I should have mentioned that I renamed hecke_involution the hash_involution because I thought that hecke_involution sounded too intrinsic. It is often called the hash involution in the literature.

Last edited 4 years ago by andrew.mathas (previous) (diff)

Changed 4 years ago by andrew.mathas

Fixing a typo

comment:53 follow-up: Changed 4 years ago by tscrim

Hey Andrew,

Andrew, thank you for reworking this to handle KL basis in specializations.

Hey everyone,

Here's the new version of the patch with Andrew's review patch, the alt interface patch, and the term compare patch folded in. I've also done the following:

  • fixed some typos,
  • changed _AGenericIwahoriHeckeAlgebra to GenericIwahoriHeckeAlgebra since it is a more natural name and to allow it to be seen in the documentation,
  • removed the to_C[p]_basis() methods which did
    return sum(H._bar_on_coefficients(coeff) * (-1)^w.length()*C(w)  for (w,coeff) in self)
    
    since this looked like it was intended as an element method and it did not agree with going through the T basis.

I don't know of a way to test if the parameters are truly generic or not. I'm not completely in favor of having the bases category accessible from the IwahoriHeckeAlgebra instance (which does follow QSym) since the category should be behind the scene as far as IwahoriHeckeAlgebra is concerned and I would expect Bases to return a list of bases (up to the mismatch with convention). I'd prefer to have it as its own separate class, but I'd like to get opinions on the matter first.

Thanks,
Travis

comment:54 in reply to: ↑ 53 ; follow-up: Changed 4 years ago by andrew.mathas

Thanks for doing this Travis and, in particular, for fixing my mistakes!

  • changed _AGenericIwahoriHeckeAlgebra to GenericIwahoriHeckeAlgebra since it is a more natural name and to allow it to be seen in the documentation,

I strongly feel that this class should not be public and it should not be included in the documentation. My reason for this is that unless people really know what they are doing (and probably even if they do) they should not be calling this class directly because it will probably not behave as they expect.

By making this class public and advertising it in the documentation I think that we will only be encouraging people to make a mistake. I intentionally made this class a private class for precisely these reasons.

In terms of names, I called this AGenenericIwahoriHeckeAlgebra because it returns a generic Hecke algebra with a particularly idiosyncratic choice of parameters: u and -v^2/u. There is (currently) no way to change these parameters. Most people would expect the two variable generic Hecke algebra to have parameters u and v and to be defined over the Laurent polynomial ring in these indeterminates. This is not what this class returns. For these reasons, whether or not the class is private, I think that calling the class GenericIwahoriHeckeAlgebra is misleading and will cause confusion.

This class is intended as a helper class for the real Hecke algebras. It should not be used directly. By putting it in the documentation we will only confuse people because they will think that they should use the generic class when they want to work with a generic Hecke algebra. When they try to do this however they will get a rude surprise because they will not be able to work with their preferred parameters.

I'm not completely in favor of having the bases category accessible from the IwahoriHeckeAlgebra instance (which does follow QSym) since the category should be behind the scene as far as IwahoriHeckeAlgebra is concerned and I would expect Bases to return a list of bases (up to the mismatch with convention). I'd prefer to have it as its own separate class, but I'd like to get opinions on the matter first.

I prefer to have the category class as subclass of the algebra class. As you say this structure is already used in several places in sage so the idiom is established and will be familar to people. Rather than the category being "behind the scenes", I think that the element category is an integral part of specifying the algebra so it should be part of algebra's class - having to call a random external class for the category, and further poluting sage's namespace, just seems wrong to me.

If you want to rename the class something other than Bases I certainly won't object as I agree that the name is misleading. Still, I vote for keeping the category class internal to IwahoriHeckeAlegbra as it currently is.

If it is decided to change this then the CombinatorialFreeModule.__init__ call in _Basis will need to be changed as the category is different in the generic and non-generic cases. This makes the code slightly more awkward, but this awkwardness is already present in _KLHeckeBases.__init__.

Andrew

Last edited 4 years ago by andrew.mathas (previous) (diff)

comment:55 in reply to: ↑ 54 ; follow-up: Changed 4 years ago by tscrim

Replying to andrew.mathas:

Thanks for doing this Travis and, in particular, for fixing my mistakes!

  • changed _AGenericIwahoriHeckeAlgebra to GenericIwahoriHeckeAlgebra since it is a more natural name and to allow it to be seen in the documentation,

I strongly feel that this class should not be public and it should not be included in the documentation. My reason for this is that unless people really know what they are doing (and probably even if they do) they should not be calling this class directly because it will probably not behave as they expect.

By making this class public and advertising it in the documentation I think that we will only be encouraging people to make a mistake. I intentionally made this class a private class for precisely these reasons.

There are many instances of internal/helper classes being in the sage documentation. For example, the *Element classes. They are there for people to look at as a nice reference. Additionally this class should be faster than going through the specialization process; so the person who is using a generic Hecke algebra and needs to speed can know of this class's existence. Plus IMO all objects, including private functions/methods, should be in the reference manual. We only make it private to hide it from the casual user using tab-completion. Since the class is not imported into the global namespace but is key for the Hecke algebras, I'd rather see it in the documentation.

In terms of names, I called this AGenenericIwahoriHeckeAlgebra because it returns a generic Hecke algebra with a particularly idiosyncratic choice of parameters: u and -v^2/u. There is (currently) no way to change these parameters. Most people would expect the two variable generic Hecke algebra to have parameters u and v and to be defined over the Laurent polynomial ring in these indeterminates. This is not what this class returns. For these reasons, whether or not the class is private, I think that calling the class GenericIwahoriHeckeAlgebra is misleading and will cause confusion.

This class is intended as a helper class for the real Hecke algebras. It should not be used directly. By putting it in the documentation we will only confuse people because they will think that they should use the generic class when they want to work with a generic Hecke algebra. When they try to do this however they will get a rude surprise because they will not be able to work with their preferred parameters.

You've chosen a convention for the generic Hecke algebra that is convenient for the code here and is clearly documented. Being much closer to naming conventions seems better to me and less likely to cause confusion for anyone who wants/needs the generic code.

I'm not completely in favor of having the bases category accessible from the IwahoriHeckeAlgebra instance (which does follow QSym) since the category should be behind the scene as far as IwahoriHeckeAlgebra is concerned and I would expect Bases to return a list of bases (up to the mismatch with convention). I'd prefer to have it as its own separate class, but I'd like to get opinions on the matter first.

I prefer to have the category class as subclass of the algebra class. As you say this structure is already used in several places in sage so the idiom is established and will be familar to people. Rather than the category being "behind the scenes", I think that the element category is an integral part of specifying the algebra so it should be part of algebra's class - having to call a random external class for the category, and further poluting sage's namespace, just seems wrong to me.

If you want to rename the class something other than Bases I certainly won't object as I agree that the name is misleading. Still, I vote for keeping the category class internal to IwahoriHeckeAlegbra as it currently is.

It is only used in QSym and NCSF as far as I known, and they are tied together. In particular, it is not used for symmetric functions. However I was not importing it into the global namespace, but instead it was just in the module's namespace. How about a middle ground of calling it _BasesCategory or something else where it is private?

Best,
Travis

comment:56 in reply to: ↑ 55 ; follow-ups: Changed 4 years ago by andrew.mathas

Hi Travis,

I think that we disagree, which is fine:) However, this means that we need some one (Anne, Brant, Nicolas, ...) to express an opinion so that we can reach a decision! Replying to tscrim:

There are many instances of internal/helper classes being in the sage documentation.

I am sure that there are but the main reason that I gave against doing this is that thie generic Hecke algebra class is very likely to confuse people and encourage them to make mistakes. The term "generic Hecke algebra" is quite common in the literature but I hve NEVER seen it refer to this particular choice of parameters and base ring.

You've chosen a convention for the generic Hecke algebra that is convenient for the code here and is clearly documented. Being much closer to naming conventions seems better to me and less likely to cause confusion for anyone who wants/needs the generic code.

As some one who has worked with these algebras and with Kazhdan-Lusztig bases quite a lot, I doubt very much that any one will want to work with this particular choice of parameters. As far as I am aware this particular choice of parameters, and in fact this description of two variable KL-bases, does not appear in the literature. Because of this I do not think that any one will want or need this particular variation of "generic code".

On the other hand, people will almost certainly want to work with the "standard" generic Hecke algebras (with parameters (q^2,-1) or (q,q^-1)) and it is quite likely that they will think that this class provides that. I agee that the documentation explains what this class actually does, but not everyone reads the manual cover-to-cover.

To my mind making this class public is a lose-lose situation: we provide something that most people won't want and we risk confusing them because it ounds like, but isn't somrthing they do want. I don't see any gains.

It is only used in QSym and NCSF as far as I known, and they are tied together. In particular, it is not used for symmetric functions. However I was not importing it into the global namespace, but instead it was just in the module's namespace. How about a middle ground of calling it _BasesCategory or something else where it is private?

I didn't say we were poluting the global namespace, just the namespace:) Whether it is private or public it's still a name that must be reserved in sage and "maintained" further down the track - just like the current patch needs to depreciate, and define pickle override for, IwahoriHeckeAlgebraT.

I'm against creating the category class as a separate class - I don't care what it is called:) - so I don't see this as midde ground. Given that you are arguing for documenting the generic Hecke algebra code I am surprised that you're uggesting that this could be a private (and hence undocumented) class.

Ultimately, I don't see any benefits in making the class separate, but I htink it is semantcally better to define it as a subclass and, more importantly, doing this makes the code cleaner.

Anyways, I have stated my arguments, so I am happy to let some one wiser decide.

Andrew

comment:57 in reply to: ↑ 56 Changed 4 years ago by aschilling

I agree with Andrew on the issue of hiding GenericIwahoriHeckeAlgebra? for the reason he mentions, namely that this choice of parameters is not commonly used and would confuse people.

Anne

comment:58 in reply to: ↑ 56 ; follow-up: Changed 4 years ago by tscrim

Hey Andrew,

Replying to andrew.mathas:

I think that we disagree, which is fine:) However, this means that we need some one (Anne, Brant, Nicolas, ...) to express an opinion so that we can reach a decision!

I agree that we disagree. :P I would like to hear other's opinions as well.

I am sure that there are but the main reason that I gave against doing this is that thie generic Hecke algebra class is very likely to confuse people and encourage them to make mistakes.

...

On the other hand, people will almost certainly want to work with the "standard" generic Hecke algebras (with parameters (q^2,-1) or (q,q^-1)) and it is quite likely that they will think that this class provides that. I agree that the documentation explains what this class actually does, but not everyone reads the manual cover-to-cover.

Do you check which definition people use when reading a paper, i.e. is that the standard practice? (That is not a rhetorical question.) However I think someone has read the manual, at least the first few lines, if they found this class.

To my mind making this class public is a lose-lose situation: we provide something that most people won't want and we risk confusing them because it sounds like, but isn't something they do want. I don't see any gains.

There are very few classes in Sage which are private, and they all inherit from object or SageObject and are small helper classes with no outside context. The reason why I made _KLHeckeBases a private nested class was because I was having difficulty with the inheritance with nested classes.

I didn't say we were poluting the global namespace, just the namespace:)

You said sage's namespace which to me implies the global namespace. However you're always adding it to some namespace, and pollution, as I think of it, occurs when using tab completion. So by having it accessible as an attribute, it's pollution.

Whether it is private or public it's still a name that must be reserved in sage and "maintained" further down the track - just like the current patch needs to depreciate, and define pickle override for, IwahoriHeckeAlgebraT.

I've been told we only need to do that for things imported into the global namespace, although that doesn't mean we shouldn't formally deprecate everything IMO. Yet we still have the same responsibilities with nested classes because we still need to properly handle those pickles (in essence it is in the global namespace).

I'm against creating the category class as a separate class - I don't care what it is called:) - so I don't see this as midde ground. Given that you are arguing for documenting the generic Hecke algebra code I am surprised that you're suggesting that this could be a private (and hence undocumented) class.

I was suggesting that as a private nested class; I'm sorry I wasn't very clear on that. It's a lesser of two evils to me, not being in the documentation versus being given to the user explicitly.

Ultimately, I don't see any benefits in making the class separate, but I think it is semantcally better to define it as a subclass and, more importantly, doing this makes the code cleaner.

For reference, these are called nested classes, subclasses are from inheritance. I think this makes the code harder to read since there's more levels of indentation to fight through.

Let me also ask you this, when should a utility class be nested? Specifically, why shouldn't the generic Iwahori-Hecke algebra be (privately) nested?

I'm also starting to worry this code is trying to be too generic instead of being explicit. In particular, we have two notions of abstract classes for the bases in _Basis and the category. You're also using reflection with the getattr which does incur a speed penality:

sage: class Foo:
....:     def bar(self):
....:         return 5
sage: F = Foo()
sage: %timeit F.bar()
1000000 loops, best of 3: 796 ns per loop
sage: %timeit F.bar()
100000 loops, best of 3: 757 ns per loop
sage: %timeit F.bar()
1000000 loops, best of 3: 787 ns per loop
sage: s = 'bar'
sage: %timeit getattr(F, s)()
1000000 loops, best of 3: 1.09 us per loop
sage: %timeit getattr(F, s)()
1000000 loops, best of 3: 1.1 us per loop
sage: %timeit getattr(F, s)()
1000000 loops, best of 3: 1.11 us per loop

With this I'm more split on what is best here since it costs CPU cycles and is less explicit, but it is more compact and an extendable idiom (i.e. works as we add other bases, but if we keep it, there should be a comment about what's needed for it to work).

I've probably given more than a nickle's worth, so I'll stop now before I go broke.

Best,
Travis

comment:59 follow-up: Changed 4 years ago by nthiery

Just some first feelings; I have only skimmed through the discussion, so please take them with a grain of salt!

About AGenericIwahoriHeckeAlgebra:

  • +1 on it should not be in the global name space
  • +1 on it should not be in the Hecke algebra name space (i.e. appear in the tab completion on Hecke algebra)
  • +1 on it appearing *somewhere* in the reference manual

With this in mind, I guess I would put it in the same module as it is now, but not as a nested class. And maybe change the class name to be explicit about the choice of parameters not being what people would call the generic ones?

Oh, and a stupid idea: would it make any sense for the Hecke algebra to have lift/retract maps to the "generic" one, and reference the later as "ambient" like we do for subquotients ?

See: http://combinat.sagemath.org/doc/reference/categories/sage/categories/subquotients.html

Cheers,

Nicolas

comment:60 in reply to: ↑ 58 ; follow-up: Changed 4 years ago by andrew.mathas

Replying to tscrim:

Do you check which definition people use when reading a paper, i.e. is that the standard practice? (That is not a rhetorical question.) However I think someone has read the manual, at least the first few lines, if they found this class.

Normally yes:). The problem in this cae is that changing the parameters isn't simply changing the definition it is changing the algebra. The two algebras are related by an outer automorphism, but this automorphism is non-trivial on the T-basis so it makes everything look and behave a little differently.

I was suggesting that as a private nested class; I'm sorry I wasn't very clear on that. It's a lesser of two evils to me, not being in the documentation versus being given to the user explicitly.

Sorry for misunderstanding. I'd be happy with this. I agree that _BasesCategory is a good name.

For reference, these are called nested classes, subclasses are from inheritance.

Thanks.

Let me also ask you this, when should a utility class be nested? Specifically, why shouldn't the generic Iwahori-Hecke algebra be (privately) nested?

To borrow a phrase from Nicolas, the code should do the talking. Having _BasesCategory nested makes the defininition of the basis classes easier, although there is not much in it. On the other hand, the generic Hecke algebras really are subclasses and it would be major pain, I think, to define them as nested classes.

I'm also starting to worry this code is trying to be too generic instead of being explicit. In particular, we have two notions of abstract classes for the bases in _Basis and the category.

Having the nested _Basis class together with the category was really in the initial patch: I simply moved some common methods out of the three basis classes into _Basis. All of the methods in _Basis really should be inside the category but as far as I can see this is not possible. Please correct me if I am wrong

You're also using reflection with the getattr which does incur a speed penality:

We should change this then. Minor conveniences in coding should not win over efficiency of execution I think. This use of reflection (again, I didn't know it was called that:), is also used in the specialize_to method, but I think this needed there...the alternative would be to specify the basis that is specialized to, rather than the Hecke algebra, but then you have to worry about converting to the correct basis before or after specialization and as far as I can see you would need to use reflection here instead so the problem doesn't go away.

Andrew

comment:61 in reply to: ↑ 59 Changed 4 years ago by andrew.mathas

Replying to nthiery:

About AGenericIwahoriHeckeAlgebra:

  • +1 on it should not be in the global name space
  • +1 on it should not be in the Hecke algebra name space (i.e. appear in the tab completion on Hecke algebra)
  • +1 on it appearing *somewhere* in the reference manual

With this in mind, I guess I would put it in the same module as it is now, but not as a nested class. And maybe change the class name to be explicit about the choice of parameters not being what people would call the generic ones?

OK, so Anne and I have voted against putting it in the manual, Travis has voted for and Nicolas for but with the caveat that it should (probably) have a different name. If the name suggests that this is an unusual generic Hecke algebra and we put a .. warning in the manual I guess I'd be happy. What about calling it AnUnusualGenericHeckeAlgebra or ANonStandardGenericHeckeAlgebra or ...?

Oh, and a stupid idea: would it make any sense for the Hecke algebra to have lift/retract maps to the "generic" one, and reference the later as "ambient" like we do for subquotients ?

Well, it is not a subquotient and mathematically I wouldn't describe it as an ambient space, so I don't think that this is very intuitive terminology.

On the other hand, there is already a map from the generic Hecke algebras to the non-generic one given by the specialize_to method:

sage: R.<a,b>=LaurentPolynomialRing(ZZ,2)
sage: H=IwahoriHeckeAlgebra("A3",a^2,-b^2)
sage: GH=H._generic_iwahori_hecke_algebra
sage: GH.T()(GH.C()[1])
(v^-1)*T[1] + (-u*v^-1)
sage: ( GH.T()(GH.C()[1]) ).specialize_to(H)
(a^-1*b^-1)*T[1] + (-a*b^-1)

Perhaps this could be defined explicitly as a map or coercion? Although since these classes are not supposed to be used directly I am not sure if this is really necessary. If there there isn't any overhead in doing this it wouldn't hurt. There isn't a well-defined retract map in the other direction.

Btw, the specialize_to map probably should be a normal method of the Iwahori-Hecke algebra elements. It won't always be well-defined, and it is not clear how to test for when it is well-defined, but the documentation for the method could have a warning to this effect and we could raise an exception when specialization fails. (Actually, we should add a similar warning for the bar involution bar).

Andrew

comment:62 in reply to: ↑ 60 ; follow-up: Changed 4 years ago by tscrim

Replying to andrew.mathas:

Normally yes:). The problem in this cae is that changing the parameters isn't simply changing the definition it is changing the algebra. The two algebras are related by an outer automorphism, but this automorphism is non-trivial on the T-basis so it makes everything look and behave a little differently.

Ah I see.

To borrow a phrase from Nicolas, the code should do the talking. Having _BasesCategory nested makes the defininition of the basis classes easier, although there is not much in it. On the other hand, the generic Hecke algebras really are subclasses and it would be major pain, I think, to define them as nested classes.

Having the nested _Basis class together with the category was really in the initial patch: I simply moved some common methods out of the three basis classes into _Basis. All of the methods in _Basis really should be inside the category but as far as I can see this is not possible. Please correct me if I am wrong.

You are correct, concrete methods can't be overwritten by the category, in particular the __init__() method.

... and as far as I can see you would need to use reflection here instead so the problem doesn't go away.

Let me see what I can do.

Replying to andrew.mathas:

OK, so Anne and I have voted against putting it in the manual, Travis has voted for and Nicolas for but with the caveat that it should (probably) have a different name. If the name suggests that this is an unusual generic Hecke algebra and we put a .. warning in the manual I guess I'd be happy. What about calling it AnUnusualGenericHeckeAlgebra? or ANonStandardGenericHeckeAlgebra or ...?

How about GenericHeckeAlgebra_nonstandard, following the convention for partitions/permutations?

Btw, the specialize_to map probably should be a normal method of the Iwahori-Hecke algebra elements. It won't always be well-defined, and it is not clear how to test for when it is well-defined, but the documentation for the method could have a warning to this effect and we could raise an exception when specialization fails. (Actually, we should add a similar warning for the bar involution bar).

Good point. I'll add something to this effect.

Best,
Travis

comment:63 in reply to: ↑ 62 Changed 4 years ago by andrew.mathas

Replying to tscrim:

How about GenericHeckeAlgebra_nonstandard, following the convention for partitions/permutations?

Btw, the specialize_to map probably should be a normal method of the Iwahori-Hecke algebra elements. It won't always be well-defined, and it is not clear how to test for when it is well-defined, but the documentation for the method could have a warning to this effect and we could raise an exception when specialization fails. (Actually, we should add a similar warning for the bar involution bar).

Good point. I'll add something to this effect.

Thanks Travis. This sounds good. Andrew

comment:64 follow-up: Changed 4 years ago by tscrim

Alright, done. Using reflection for the generic's specialize_to is the best way to go, but I did manage to a 10x speedup by calling _from_dict() instead of summing over the monomials (the "public" way would be sum_of_terms() with distinct=True but this just redirects after creating a dictionary).

Best,
Travis

For patchbot:

Apply: trac_14261-iwahori_hecke-ts.patch

comment:65 in reply to: ↑ 64 Changed 4 years ago by andrew.mathas

Replying to tscrim:

Alright, done. Using reflection for the generic's specialize_to is the best way to go, but I did manage to a 10x speedup by calling _from_dict() instead of summing over the monomials (the "public" way would be sum_of_terms() with distinct=True but this just redirects after creating a dictionary).

I'm in the process of compiling 5.12. When this is one I'll review the latest patch. A.

Changed 4 years ago by andrew.mathas

Fixes some documentaton and some issues in nil_coxeter and new_kschur

comment:66 follow-up: Changed 4 years ago by andrew.mathas

A new review patch is attached (and on the queue). It fixes some errors (which I may have introduced) in the documentation and some issues with nil_coxeter_algebra and new_kschur due to the new calling syntax and new output.

Brant: Could you please check the documentation for (mathematical) errors? I just fixed quite a few about the KL-bases, but it is likely that I missed some and not unlikely that I created others. As you are more familiar with the area than Travis it will be much easier for you to spot mistakes.

Travis: There is an error i the documentation on line 185:

:meth:`bar involution <IwahoriHeckeAlgebra._BasesCategory.ElementMethods.bar>`

The bar involution should presumably be a link to the corresponding method but the link i not showing up. I haven't seen this syntax before so I'm not sure of the best way to fix it. Could you please have a look?

I'm fairly happy with the patch now. As we (Brant, Travis and I) are now all listed as authors what is the protocol for giving this a positive review? Can we just agree amongst ourselves or should be lean on some one?

Andrew

comment:67 follow-up: Changed 4 years ago by brant

Sure, I would be happy to look at the documentation and submit a positive review (for whatever that is worth)...

I really appreciate all the work Andrew and Travis have done on this patch. I haven't worked much with the generic Hecke algebra but I am happy to see this functionality added to the patch!

comment:68 in reply to: ↑ 67 Changed 4 years ago by andrew.mathas

Replying to brant:

I haven't worked much with the generic Hecke algebra but I am happy to see this functionality added to the patch!

If you've worked with the KL-bases then you have worked with a generic Hecke algebra:) These more exotic two variable generic rings you probably haven't played with but they are just an sleight of hand so that the code works with the KL-bases no matter what normalization of the quadratic relations the user want to use: for example, (T_r-q)(T_r+1)=0 over Z[q^{\pm1/2}], or (T_r-v)(T_r^v^-1)=0 over Z[v^{\pm1}].

comment:69 in reply to: ↑ 66 Changed 4 years ago by tscrim

  • Description modified (diff)

Replying to andrew.mathas:

Travis: There is an error i the documentation on line 185:

:meth:`bar involution <IwahoriHeckeAlgebra._BasesCategory.ElementMethods.bar>`

The bar involution should presumably be a link to the corresponding method but the link i not showing up. I haven't seen this syntax before so I'm not sure of the best way to fix it. Could you please have a look?

The syntax is :meth:`this is the displayed text <link.to.method>`. However it's not working because the link is no longer there in the documentation, so you can simply remove the doc link.

I'm fairly happy with the patch now. As we (Brant, Travis and I) are now all listed as authors what is the protocol for giving this a positive review? Can we just agree amongst ourselves or should be lean on some one?

It would be a cross-review, we review the other's code (basically what we've been doing). It's a positive review on my part once Andrew makes the minor tweak to his review patch about the link.

Best,
Travis

For patchbot:

Apply: trac_14261-iwahori_hecke-ts.patch, trac_14261-iwahori_hecke-review--am.patch​

Last edited 4 years ago by tscrim (previous) (diff)

comment:70 Changed 4 years ago by brant

  • Status changed from needs_review to positive_review

Patch review: #14261

This patch began as a SageDays? project to implement the Kazhdan--Lusztig C' basis of the Iwahori--Hecke algebra under the "standard" 1-parameter specialization (described, for example, in Humphreys' book "Reflection groups and Coxeter groups"). Since this initial effort, the patch has been rewritten by Andrew Mathas to construct the algebra for any pair of parameters (rather than just q2 and -1), and to compute the Kazhdan--Lusztig C basis (when the negative product of the paramters is a square in the base ring). Travis Scrimshaw has made significant contributions to help design, code, and document these changes so that they conform to current Sage conventions used by other classes. Their work has dramatically improved the readability and utility of this class!

Andrew is a widely acknowledged expert in this area, having written a textbook and many papers involving computations in Iwahori--Hecke algebras. This patch implements useful mathematics and the documentation includes references to relevant mathematical literature.

Generally speaking, the documentation is exceptionally clear. I may have found a minor typo in the description of the C basis: I believe that the second defining property of the C basis should include a minus sign in the exponent of (-q)(\ell(v)) in the triangular expansion. Otherwise, the documentation is very helpful and includes many useful examples and consistency checks for conversions among the T, C, and C' bases. All of the doctests (with --long) passed. I have also tested some Kazhdan--Lusztig basis computations in types A and B and compared with the corresponding GAP/CHEVIE (version 3) output. All of the computations I performed agreed with this external software.

Many thanks again to Andrew and Travis for all of their improvements to this patch!

-- Brant Jones

comment:71 Changed 4 years ago by tscrim

  • Description modified (diff)

Thank you Brant for your initial version of this patch which contained the core functionality. Thank you Andrew for reworking the patch and your expertise. Thank you Nicolas and Darij for your help with this patch.

I've uploaded the (hopefully) final folded version which removes the dead link Andrew found and fixes the typo Brant found.

Thank you all for your work in this patch,
Travis

For patchbot:

Apply: trac_14261-iwahori_hecke-ts.patch

comment:72 Changed 4 years ago by jdemeyer

Some doctest failures:

sage -t devel/sage/doc/en/thematic_tutorials/lie/iwahori_hecke_algebra.rst
**********************************************************************
File "devel/sage/doc/en/thematic_tutorials/lie/iwahori_hecke_algebra.rst", line 54, in doc.en.thematic_tutorials.lie.iwahori_hecke_algebra
Failed example:
    H = IwahoriHeckeAlgebra("B3",q).T(); H
Expected:
    Iwahori-Hecke algebra of type B3 in q,-1 over Univariate Polynomial Ring
     in q over Integer Ring in the standard basis
Got:
    Iwahori-Hecke algebra of type B3 in q,-1 over Univariate Polynomial Ring in q over Integer Ring in the T-basis
**********************************************************************
File "devel/sage/doc/en/thematic_tutorials/lie/iwahori_hecke_algebra.rst", line 58, in doc.en.thematic_tutorials.lie.iwahori_hecke_algebra
Failed example:
    T1*T1
Expected:
    (q-1)*T1 + q
Got:
    (q-1)*T[1] + q
**********************************************************************
File "devel/sage/doc/en/thematic_tutorials/lie/iwahori_hecke_algebra.rst", line 70, in doc.en.thematic_tutorials.lie.iwahori_hecke_algebra
Failed example:
    H(s1*s2)
Expected:
    T1*T2
Got:
    T[1,2]
**********************************************************************

comment:73 Changed 4 years ago by jdemeyer

  • Status changed from positive_review to needs_work

Also

sage -t devel/sage/sage/tests/book_schilling_zabrocki_kschur_primer.py
**********************************************************************
File "devel/sage/sage/tests/book_schilling_zabrocki_kschur_primer.py", line 522, in sage.tests.book_schilling_zabrocki_kschur_primer
Failed example:
    A.homogeneous_noncommutative_variables([2])
Expected:
    A1*A0 + A2*A0 + A0*A3 + A3*A2 + A3*A1 + A2*A1
Got:
    A[1,0] + A[2,0] + A[0,3] + A[3,2] + A[3,1] + A[2,1]
**********************************************************************
File "devel/sage/sage/tests/book_schilling_zabrocki_kschur_primer.py", line 527, in sage.tests.book_schilling_zabrocki_kschur_primer
Failed example:
    A.k_schur_noncommutative_variables([2,2])
Expected:
    A0*A3*A1*A0 + A3*A1*A2*A0 + A1*A2*A0*A1 + A3*A2*A0*A3 + A2*A0*A3*A1
    + A2*A3*A1*A2
Got:
    A[0,3,1,0] + A[3,1,2,0] + A[1,2,0,1] + A[3,2,0,3] + A[2,0,3,1] + A[2,3,1,2]

comment:74 Changed 4 years ago by tscrim

  • Cc zabrocki added
  • Dependencies changed from #13735 #14014 #14678 #14516 to #13735 #14014 #14678 #14516 #15257
  • Status changed from needs_work to positive_review

Fixed. I've added #15257 as a dependency for (likely) fuzz.

Mike (and Anne), I've cc-ed you to note the above changes to the k-Schur book's doctests.

Best,
Travis

comment:75 in reply to: ↑ 1 ; follow-up: Changed 4 years ago by andrew.mathas

Hi Travis,

Thanks for fixing this so quickly! I have checked and the new patch fixes the problems that Jeroen found, however, I found another issue:

sage -t --long iwahori_hecke_algebra.py

takes forever.

I seem to remember that even #long tests should be limited to about 3-5s - which always struck me as not being very long, but rules are rules. As far as I can tell the existence of such a limit, and what the upper bound is, does not seem to be documented in the developers guide, or anywhere else, but I am sure that it exists. (As the time that a test takes to execute is machine dependent it probably does not make any sense to have an official time limit, but the developers guide really ought to mention this somewhere and give some guidance:)

Anyway, using --warn-long 5 identifies the problem tests (there are many more in the 3-5s range):

sage -t --long --warn-long 5.0 iwahori_hecke_algebra.py
**********************************************************************
File "iwahori_hecke_algebra.py", line 91, in sage.algebras.iwahori_hecke_algebra.index_cmp
Failed example:
    W = WeylGroup(['A',2,1])
Test ran for 9.25 s
**********************************************************************
File "iwahori_hecke_algebra.py", line 369, in sage.algebras.iwahori_hecke_algebra.IwahoriHeckeAlgebra
Failed example:
    all(T(C[x]).bar() == T(C[x]) for x in W) # long time
Test ran for 30.79 s
**********************************************************************
File "iwahori_hecke_algebra.py", line 375, in sage.algebras.iwahori_hecke_algebra.IwahoriHeckeAlgebra
Failed example:
    all(T(C[x]) == (-v)^x.length()*sum(term(x,y) for y in W) for x in W) # long time
Test ran for 7.49 s
**********************************************************************
File "iwahori_hecke_algebra.py", line 388, in sage.algebras.iwahori_hecke_algebra.IwahoriHeckeAlgebra
Failed example:
    all(T[x] == T(C(T[x])) for x in W) # long time
Test ran for 401.56 s
**********************************************************************
File "iwahori_hecke_algebra.py", line 394, in sage.algebras.iwahori_hecke_algebra.IwahoriHeckeAlgebra
Failed example:
    all(C[x] == C(Cp(C[x])) for x in W) # long time
Test ran for 7.78 s
**********************************************************************
File "iwahori_hecke_algebra.py", line 398, in sage.algebras.iwahori_hecke_algebra.IwahoriHeckeAlgebra
Failed example:
    all(Cp[x] == Cp(C(Cp[x])) for x in W) # long time
Test ran for 7.87 s
**********************************************************************
File "iwahori_hecke_algebra.py", line 400, in sage.algebras.iwahori_hecke_algebra.IwahoriHeckeAlgebra
Failed example:
    all(T(C[x]).bar() == T(C[x]) for x in W) # long time
Test ran for 35.21 s
**********************************************************************
File "iwahori_hecke_algebra.py", line 402, in sage.algebras.iwahori_hecke_algebra.IwahoriHeckeAlgebra
Failed example:
    all(T(Cp[x]).bar() == T(Cp[x]) for x in W) # long time
Test ran for 36.77 s
**********************************************************************
File "iwahori_hecke_algebra.py", line 406, in sage.algebras.iwahori_hecke_algebra.IwahoriHeckeAlgebra
Failed example:
    all(T(C[x]) == (-v)^x.length()*sum(term(x,y) for y in W) for x in W) # long time
Test ran for 28.09 s
**********************************************************************
2 items had failures:
   8 of 100 in sage.algebras.iwahori_hecke_algebra.IwahoriHeckeAlgebra
   1 of   7 in sage.algebras.iwahori_hecke_algebra.index_cmp
    [567 tests, 9 failures, 601.88 s]
----------------------------------------------------------------------
sage -t --long --warn-long 5.0 iwahori_hecke_algebra.py  # 9 doctests failed
----------------------------------------------------------------------
Total time for all tests: 602.2 seconds
    cpu time: 595.9 seconds
    cumulative wall time: 601.9 seconds

The longest test is on line 388 -- but this whole block is problematic because if we took out the first test then one or more of the subsequent tests would take longer as they all (should) benefit from caching.

As I don't know what the official upper limit is for a long test I am not sure which ones we need to disable. Still, taking out the block on lines 383-409 would be a good start. If 30s is too long then we have a few more to worry about.

To remove a test I guess that we just replace #long time with #not tested? Hopefully, there is a more efficient way to take out an entire block?

Andrew

Last edited 4 years ago by andrew.mathas (previous) (diff)

comment:76 Changed 4 years ago by andrew.mathas

  • Keywords days45 added

comment:77 Changed 4 years ago by andrew.mathas

  • Status changed from positive_review to needs_work

comment:78 in reply to: ↑ 75 ; follow-up: Changed 4 years ago by jdemeyer

Replying to andrew.mathas:

I seem to remember that even #long tests should be limited to about 3-5s

There is certainly no such rule as far as I know. The basic rules are: normal short tests should be less than 1s. Long tests should be less than 30s, although exceptionally (if there is a good reason) up to 60s is acceptable.

The benchmark system is sage.math or boxen.math.

Last edited 4 years ago by jdemeyer (previous) (diff)

comment:79 in reply to: ↑ 78 Changed 4 years ago by andrew.mathas

Replying to jdemeyer:

Replying to andrew.mathas:

I seem to remember that even #long tests should be limited to about 3-5s

There is certainly no such rule as far as I know. The basic rules are: normal short tests should be less than 1s. Long tests should be less than 30s, although exceptionally (if there is a good reason) up to 60s is acceptable.

The benchmark system is sage.math or boxen.math.

Thanks for the correction/clarification.

Travis: I've just uploaded a new version of the patch to the combinat queue which disables the long doc-tests in the block of lines 380-410 (no other changes). I don't have permission to replace your patch on trac so can you please do this and put the patch back to a positive review if you think it's OK.

Andrew

Changed 4 years ago by tscrim

With fixed long time tests

comment:80 follow-up: Changed 4 years ago by tscrim

  • Status changed from needs_work to needs_review

Okay, I made the group smaller (B_2 instead of B_3) which gets rid of the 400+ seconds. I think we should leave the tests in there. The first one will always be slow due to making the cache, but is not horribly long (like 400 seconds!) and allows the other tests to be much faster. And in case anybody is curious, the Weyl group creation is slow due to loading (lib)Gap and must be done.

travis@Kristine-Desktop:~/sage-5.12.beta5/devel/sage-combinat/sage/categories$ sage -t --long --warn-long 5.0 ../algebras/iwahori_hecke_algebra.py 
Running doctests with ID 2013-10-17-08-56-37-bf72d26b.
Doctesting 1 file.
sage -t --long --warn-long 5.0 ../algebras/iwahori_hecke_algebra.py
**********************************************************************
File "../algebras/iwahori_hecke_algebra.py", line 91, in sage.algebras.iwahori_hecke_algebra.index_cmp
Failed example:
    W = WeylGroup(['A',2,1])
Test ran for 19.09 s
**********************************************************************
File "../algebras/iwahori_hecke_algebra.py", line 369, in sage.algebras.iwahori_hecke_algebra.IwahoriHeckeAlgebra
Failed example:
    all(T(C[x]).bar() == T(C[x]) for x in W) # long time
Test ran for 60.60 s
**********************************************************************
File "../algebras/iwahori_hecke_algebra.py", line 371, in sage.algebras.iwahori_hecke_algebra.IwahoriHeckeAlgebra
Failed example:
    all(T(Cp[x]).bar() == T(Cp[x]) for x in W) # long time
Test ran for 7.61 s
**********************************************************************
File "../algebras/iwahori_hecke_algebra.py", line 375, in sage.algebras.iwahori_hecke_algebra.IwahoriHeckeAlgebra
Failed example:
    all(T(C[x]) == (-v)^x.length()*sum(term(x,y) for y in W) for x in W) # long time
Test ran for 16.40 s
**********************************************************************
File "../algebras/iwahori_hecke_algebra.py", line 1222, in sage.algebras.iwahori_hecke_algebra.IwahoriHeckeAlgebra.T
Failed example:
    all(T(C(T[x])) == T[x] for x in W) # long time
Test ran for 7.62 s
**********************************************************************
File "../algebras/iwahori_hecke_algebra.py", line 1230, in sage.algebras.iwahori_hecke_algebra.IwahoriHeckeAlgebra.T
Failed example:
    all(T[x].bar() == sum(v^(-2*y.length()) * KL.R(y, x).substitute(v=v^-2) * T[y] for y in W) for x in W) # long time
Test ran for 9.60 s
**********************************************************************
3 items had failures:
   3 of 100 in sage.algebras.iwahori_hecke_algebra.IwahoriHeckeAlgebra
   2 of  19 in sage.algebras.iwahori_hecke_algebra.IwahoriHeckeAlgebra.T
   1 of   7 in sage.algebras.iwahori_hecke_algebra.index_cmp
    [567 tests, 6 failures, 153.52 s]
----------------------------------------------------------------------
sage -t --long --warn-long 5.0 ../algebras/iwahori_hecke_algebra.py  # 6 doctests failed
----------------------------------------------------------------------
Total time for all tests: 154.2 seconds
    cpu time: 133.7 seconds
    cumulative wall time: 153.5 seconds

If you're okay with this, then go ahead and set it to positive review.

For patchbot:

Apply: trac_14261-iwahori_hecke-ts.patch

comment:81 in reply to: ↑ 80 Changed 4 years ago by andrew.mathas

  • Status changed from needs_review to positive_review

Replying to tscrim:

Okay, I made the group smaller (B_2 instead of B_3) which gets rid of the 400+ seconds. I think we should leave the tests in there. The first one will always be slow due to making the cache, but is not horribly long (like 400 seconds!) and allows the other tests to be much faster. And in case anybody is curious, the Weyl group creation is slow due to loading (lib)Gap and must be done.

Hi Travis,

I agree, this is better than what I was proposing. Thanks!

I am happy with the changes,

Andrew

comment:82 follow-up: Changed 4 years ago by jdemeyer

  • Merged in set to sage-5.13.beta1
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:83 in reply to: ↑ 82 Changed 4 years ago by aschilling

Travis: I thought we discussed this before, but you cannot just make changes in the doctests for the book on k-Schur functions without telling Mike or myself. The file is there so that it matches with what is in the book!

PS: Ok, I see that you mentioned this earlier, but unfortunately, I am not getting any more e-mails from trac due to the spam settings!

Last edited 4 years ago by aschilling (previous) (diff)
Note: See TracTickets for help on using tickets.