#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 )
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)
Change History (90)
Changed 8 years ago by
comment:1 follow-up: ↓ 75 Changed 8 years ago by
- Cc aschilling andrew.mathas added
- Status changed from new to needs_review
comment:2 Changed 8 years ago by
- 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 8 years ago by
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 8 years ago by
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 q^{1/2} }to -q^{-1/2} and T_{x} to (-1)^{\ell(x)}q^{-1/2\ell(x)}T_{x}.
comment:5 Changed 8 years ago by
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 8 years ago by
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 8 years ago by
- 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 8 years ago by
- 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 8 years ago by
- Work issues T <-> C basis map deleted
comment:10 Changed 8 years ago by
comment:11 Changed 8 years ago by
- Dependencies set to #14014
comment:12 Changed 8 years ago by
- Dependencies changed from #14014 to #13735 #14014
Also rebased over #13735.
comment:13 Changed 8 years ago by
- Dependencies changed from #13735 #14014 to #13735 #14014 #14678
comment:14 Changed 8 years ago by
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 8 years ago by
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 8 years ago by
- 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 8 years ago by
- Cc sam added
comment:18 Changed 8 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:19 Changed 8 years ago by
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: ↓ 24 Changed 8 years ago by
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 8 years ago by
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 8 years ago by
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: ↓ 25 ↓ 26 Changed 8 years ago by
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 8 years ago by
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 whenq
is a root of unity, but I don't know if the bar involution is still useful at specializedq
. The problem in my mind is takeq = 2
and consider the element2
, what is the bar of this, does it matter if it's1 + 1
or2 in ZZ
or suppose to be theq
?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 8 years ago by
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 8 years ago by
..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 8 years ago by
- 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: ↓ 29 Changed 8 years ago by
- 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: ↓ 31 Changed 8 years ago by
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 8 years ago by
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 8 years ago by
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 8 years ago by
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 8 years ago by
comment:33 Changed 8 years ago by
- 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: ↓ 35 ↓ 38 Changed 8 years ago by
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: ↓ 36 Changed 8 years ago by
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
andq2
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 specialisev^2
toq
. In particular, the KL bases make sense for the integral groups ringsZW
.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.
comment:36 in reply to: ↑ 35 ; follow-up: ↓ 37 Changed 8 years ago by
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 forCombinatorialFreeModule
(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. Thein the X basis
part is a standard paradigm from otherWithRealization
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 8 years ago by
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 ringR
, however, you can't "see" the KL bases ofRW
inside the group ring. The only way to compute the KL bases orRW
is to do it inside the generic Hecke algebra and then specialise. Notice also that even though the KL bases are defined forRW
the bar involution is NOT defined onRW
, 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 forCombinatorialFreeModule
(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 likeT(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. Thein the X basis
part is a standard paradigm from otherWithRealization
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: ↓ 42 Changed 8 years ago by
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: ↓ 40 Changed 8 years ago by
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)=x^{k) 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: ↓ 41 ↓ 44 Changed 8 years ago by
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
comment:41 in reply to: ↑ 40 ; follow-up: ↓ 48 Changed 8 years ago by
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
comment:42 in reply to: ↑ 38 ; follow-up: ↓ 43 Changed 8 years ago by
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 8 years ago by
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 8 years ago by
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 onZW
. The point is that you can't detect the KL-bases insideZW
: 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 8 years ago by
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.
comment:46 follow-up: ↓ 47 Changed 8 years ago by
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).
comment:47 in reply to: ↑ 46 Changed 8 years ago by
Replying to andrew.mathas:
Default parameters for the Hecke algebras
We are implementing Hecke algebras with two parameters
q1
andq2
. 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 groupAll 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: ↓ 49 Changed 8 years ago by
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_primeas 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" classC_prime
and then proceed to use the shortened nameCp
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: ↓ 50 Changed 8 years ago by
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
.
comment:50 in reply to: ↑ 49 Changed 8 years ago by
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
andWeylGroup
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 ofCoxeterGroup
.
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 8 years ago by
comment:51 Changed 8 years ago by
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.
comment:52 Changed 8 years ago by
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.
comment:53 follow-up: ↓ 54 Changed 8 years ago by
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
toGenericIwahoriHeckeAlgebra
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 didreturn 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: ↓ 55 Changed 8 years ago by
Thanks for doing this Travis and, in particular, for fixing my mistakes!
- changed
_AGenericIwahoriHeckeAlgebra
toGenericIwahoriHeckeAlgebra
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 followQSym
) since the category should be behind the scene as far asIwahoriHeckeAlgebra
is concerned and I would expectBases
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
comment:55 in reply to: ↑ 54 ; follow-up: ↓ 56 Changed 8 years ago by
Replying to andrew.mathas:
Thanks for doing this Travis and, in particular, for fixing my mistakes!
- changed
_AGenericIwahoriHeckeAlgebra
toGenericIwahoriHeckeAlgebra
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 A
GenenericIwahoriHeckeAlgebra
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 parametersu
andv
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 classGenericIwahoriHeckeAlgebra
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 followQSym
) since the category should be behind the scene as far asIwahoriHeckeAlgebra
is concerned and I would expectBases
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 toIwahoriHeckeAlegbra
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: ↓ 57 ↓ 58 Changed 8 years ago by
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
andNCSF
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 8 years ago by
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: ↓ 60 Changed 8 years ago by
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: ↓ 61 Changed 8 years ago by
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: ↓ 62 Changed 8 years ago by
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 8 years ago by
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: ↓ 63 Changed 8 years ago by
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 8 years ago by
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: ↓ 65 Changed 8 years ago by
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 8 years ago by
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 besum_of_terms()
withdistinct=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.
comment:66 follow-up: ↓ 69 Changed 8 years ago by
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: ↓ 68 Changed 8 years ago by
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 8 years ago by
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 8 years ago by
- 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
comment:70 Changed 8 years ago by
- 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 q^{2} 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 8 years ago by
- 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 8 years ago by
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 8 years ago by
- 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 8 years ago by
- 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: ↓ 78 Changed 8 years ago by
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
comment:76 Changed 8 years ago by
- Keywords days45 added
comment:77 Changed 8 years ago by
- Status changed from positive_review to needs_work
comment:78 in reply to: ↑ 75 ; follow-up: ↓ 79 Changed 8 years ago by
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
.
comment:79 in reply to: ↑ 78 Changed 8 years ago by
Replying to jdemeyer:
Replying to andrew.mathas:
I seem to remember that even
#long tests
should be limited to about 3-5sThere 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
orboxen.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
comment:80 follow-up: ↓ 81 Changed 8 years ago by
- 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 8 years ago by
- Status changed from needs_review to positive_review
Replying to tscrim:
Okay, I made the group smaller (
B_2
instead ofB_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: ↓ 83 Changed 8 years ago by
- 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 8 years ago by
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!
Hey Brant,
I've uploaded a new version of the patch which reworks the implementation to follow the
WithRealizations
API and deprecates theIwahoriHeckeAlgebraT
class. If it wasn't ready for review, I think it now is.Best,
Travis