Iwahori-Hecke algebra with several bases

[d06b82bc-eb37-48a6-9e6a-dbbee712c170]

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:

• attachment: trac_14261-iwahori_hecke-ts.patch

Depends on #13735 Depends on #14014 Depends on #14678 Depends on #14516 Depends on #15257

CC: @sagetrac-sage-combinat @anneschilling @AndrewAtLarge @samclearman @zabrocki

Component: combinatorics

Keywords: Iwahori Hecke algebra, days45

Author: Brant Jones, Travis Scrimshaw, Andrew Mathas

Reviewer: Andrew Mathas, Brant Jones, Travis Scrimshaw

Merged: sage-5.13.beta1

Issue created by migration from https://trac.sagemath.org/ticket/14261

[nthiery]

comment:39

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

[AndrewMathas]

comment:40

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<sup>-1,v,v</sup>-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<sup>{-1}}</sup>{-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

[AndrewMathas]

comment:41

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

[AndrewMathas]

comment:42

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

[nthiery]

comment:43

Replying to @AndrewAtLarge:

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

[nthiery]

comment:44

Replying to @AndrewAtLarge:

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

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

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

Cheers, Nicolas

[AndrewMathas]

comment:45

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.

[AndrewMathas]

comment:46

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).

[nthiery]

comment:47

Replying to @AndrewAtLarge:

Default parameters for the Hecke algebras

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

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

as we currently have it, or should they be

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

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

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

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

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

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

Thanks!

[tscrim]

comment:48

Replying to @AndrewAtLarge:

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

    Cp = C_prime
    kazhdan_lusztig = C_prime

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

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

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

[AndrewMathas]

comment:49

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.

[tscrim]

comment:50

Replying to @AndrewAtLarge:

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

Ah, I see.

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

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

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

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

The problem is that CoxeterGroup and WeylGroup return different groups:

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

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

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

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

[tscrim]

comment:51

Attachment: trac_14261-term_cmp-ts.patch.gz

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.

[AndrewMathas]

Changed author from Brant Jones, Travis Scrimshaw to Brant Jones, Travis Scrimshaw, Andrew Mathas

[AndrewMathas]

comment:52

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.

[AndrewMathas]

Attachment: trac_14261-alt_interface-review--am.patch.gz

Fixing a typo

[tscrim]

comment:53

Hey Andrew,

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

Hey everyone,

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

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

• removed the to_C[p]_basis() methods which did

  return sum(H._bar_on_coefficients(coeff) * (-1)^w.length()*C(w)  for (w,coeff) in self)

  since this looked like it was intended as an element method and it did not agree with going through the T basis.

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

Thanks,

Travis

[AndrewMathas]

comment:54

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

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

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

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

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

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

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

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

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

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

Andrew

[tscrim]

comment:55

Replying to @AndrewAtLarge:

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

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

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

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

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

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

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

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

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

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

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

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

Best,

Travis

[AndrewMathas]

comment:56

Hi Travis,

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

Replying to @tscrim:

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

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

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

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

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

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

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

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

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

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

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

Andrew

[anneschilling]

comment:57

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

[tscrim]

comment:58

Hey Andrew,

Replying to @AndrewAtLarge:

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

[nthiery]

comment:59

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

[AndrewMathas]

comment:60

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

[AndrewMathas]

comment:61

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

[tscrim]

comment:62

Replying to @AndrewAtLarge:

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 @AndrewAtLarge:

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

[AndrewMathas]

comment:63

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

[tscrim]

comment:64

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

[AndrewMathas]

comment:65

Replying to @tscrim:

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

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

[AndrewMathas]

Fixes some documentaton and some issues in nil_coxeter and new_kschur

[AndrewMathas]

comment:66

Attachment: trac_14261-iwahori_hecke-review--am.patch.gz

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

[d06b82bc-eb37-48a6-9e6a-dbbee712c170]

comment:67

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!

[AndrewMathas]

comment:68

Replying to @sagetrac-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<sup>v</sup>-1)=0 over Z[v^{\pm1}].

[tscrim]

Description changed:

--- 
+++ 
@@ -9,4 +9,4 @@
 Apply:

 * [attachment: trac_14261-iwahori_hecke-ts.patch](https://github.com/sagemath/sage-prod/files/10657354/trac_14261-iwahori_hecke-ts.patch.gz)
-
+* [attachment: trac_14261-iwahori_hecke-review--am.patch​](https://github.com/sagemath/sage/files/ticket14261/4a58c85ff4b66c8f44e874e1848e07d4.gz)

[tscrim]

comment:69

Replying to @AndrewAtLarge:

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 `. 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​

[d06b82bc-eb37-48a6-9e6a-dbbee712c170]

comment:70

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

[tscrim]

Description changed:

--- 
+++ 
@@ -9,4 +9,3 @@
 Apply:

 * [attachment: trac_14261-iwahori_hecke-ts.patch](https://github.com/sagemath/sage-prod/files/10657354/trac_14261-iwahori_hecke-ts.patch.gz)
-* [attachment: trac_14261-iwahori_hecke-review--am.patch​](https://github.com/sagemath/sage/files/ticket14261/4a58c85ff4b66c8f44e874e1848e07d4.gz)

[tscrim]

comment:71

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

[jdemeyer]

comment:72

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]
**********************************************************************

[jdemeyer]

comment:73

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]

[tscrim]

comment:74

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

[tscrim]

Changed dependencies from #13735 #14014 #14678 #14516 to #13735 #14014 #14678 #14516 #15257

[AndrewMathas]

comment:75

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

[AndrewMathas]

Changed keywords from Iwahori Hecke algebra to Iwahori Hecke algebra, days45

[jdemeyer]

comment:78

Replying to @AndrewAtLarge:

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.

[AndrewMathas]

comment:79

Replying to @jdemeyer:

Replying to @AndrewAtLarge:

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

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

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

Thanks for the correction/clarification.

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

Andrew

[tscrim]

Attachment: trac_14261-iwahori_hecke-ts.patch.gz

With fixed long time tests

[tscrim]

comment:80

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

[AndrewMathas]

comment:81

Replying to @tscrim:

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

Hi Travis,

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

I am happy with the changes,

Andrew

[jdemeyer]

Merged: sage-5.13.beta1