Iwahori-Hecke algebra with several bases

[sagetrac-brant]

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

[sagetrac-brant]

Attachment: trac_14261_iwahori_hecke.patch.gz

[tscrim]

comment:1

Hey Brant,

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

Best,

Travis

[tscrim]

Changed author from Brant Jones to Brant Jones, Travis Scrimshaw

[tscrim]

comment:2

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

[tscrim]

comment:3

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

[AndrewMathas]

comment:4

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.

[tscrim]

comment:5

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.

[nthiery]

comment:6

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

[tscrim]

comment:7

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.

[tscrim]

Work Issues: T <-> C basis map

[tscrim]

comment:8

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.

[tscrim]

Changed work issues from T <-> C basis map to none

[tscrim]

comment:10

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

[tscrim]

Dependencies: #14014

[tscrim]

comment:11

Rebased over #14014.

For patchbot:

Apply: trac_14261-iwahori_hecke-ts.patch

[tscrim]

Changed dependencies from #14014 to #13735 #14014

[tscrim]

comment:12

Also rebased over #13735.

[tscrim]

comment:13

Rebased over #14678 (trivial: some fuzz).

For patchbot:

Apply: trac_14261-iwahori_hecke-ts.patch

[tscrim]

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

[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

[anneschilling]

comment:83

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!