search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.47k stars 486 forks source link

Implement symplectic and orthogonal bases of Sym #15536

Closed tscrim closed 9 years ago

tscrim commented 10 years ago

Following a paper of Chari and Kleber: Symmetric functions and representations of quantum affine algebras, arxiv:0011161v1. We implement the symplectic and orthogonal (filtered) bases of Sym.

Depends on #17096

CC: @sagetrac-sage-combinat @darijgr @simon-king-jena @nthiery

Component: combinatorics

Keywords: days54, sym

Author: Travis Scrimshaw

Branch/Commit: 5b492f3

Reviewer: Mike Zabrocki

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

tscrim commented 10 years ago
comment:1

Darij (or anyone else who wants to review this),

Nicolas said it's fine being in GradedHopfAlgebrasWithBasis since Sym does admit a graded basis, even if the given basis itself is not graded.

darijgr commented 10 years ago
comment:2

I fear Nicolas is wrong here:

sage: o = Sym.o()
sage: TestSuite(o).run()
Failure in _test_antipode:
Traceback (most recent call last):
  File "/home/darij/gitsage/sage-5.13.beta1/local/lib/python2.7/site-packages/sage/misc/sage_unittest.py", line 282, in run
    test_method(tester = tester)
  File "/home/darij/gitsage/sage-5.13.beta1/local/lib/python2.7/site-packages/sage/categories/hopf_algebras_with_basis.py", line 263, in _test_antipode
    tester.assert_(SI(x) == self.counit(x) * self.one())
  File "/home/darij/gitsage/sage-5.13.beta1/local/lib/python/unittest/case.py", line 424, in assertTrue
    raise self.failureException(msg)
AssertionError: False is not true
------------------------------------------------------------
The following tests failed: _test_antipode

The problem is that the counit is still defined as the constant coefficient, but that's only true for graded bases. Concrete example:

sage: o[2].counit()
0
sage: s(o[2]).counit()
-1

The same issue would be happening with antipode and degree_negation if not for the fact that the o and sp bases happen to be graded w.r.t. the induced ZZ/2ZZ-grading.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 9536f54 to 223b11b

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

223b11bFix the counit in sp/o bases.
4933218Merge branch 'develop' into public/combinat/sf/sp_orth
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

9ea2a2cAdded comment about ZZ / 2ZZ grading.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 223b11b to 9ea2a2c

tscrim commented 10 years ago
comment:5

Replying to @darijgr:

I fear Nicolas is wrong here

...

The problem is that the counit is still defined as the constant coefficient, but that's only true for graded bases.

Yep, but that's technically a fault with the generic symmetric function code, not the category (which I think does it via coercion by default). Fixed.

The same issue would be happening with antipode and degree_negation if not for the fact that the o and sp bases happen to be graded w.r.t. the induced ZZ/2ZZ-grading.

Again, not the category, but it's nice to know these things.

New commits:

9ea2a2cAdded comment about ZZ / 2ZZ grading.
darijgr commented 10 years ago
comment:6

I see. Can it be that the SymmetricFunctionsBases class should be split into SymmetricFunctionsBases and SymmetricFunctionsConnectedGradedBases or else we risk running into this whenever other new methods are implemented? If so, I'd suggest doing this (I can do it myself), although I'd wait for #15473 to be merged beforehand.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

fd17c25Documentation tweaks/typo fixes.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 9ea2a2c to fd17c25

tscrim commented 10 years ago
comment:8

I doubt there will be too many new methods which a general implementation does not involve coercing to a basis where we can do the computation explicitly, so I don't think it's necessary. Nevertheless, something for another ticket (possibly after a sage-combinat-devel discussion).

fchapoton commented 10 years ago
comment:10

There is a typo "Scirmshaw"

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

de32f11Merge branch 'public/combinat/sf/sp_orth' of trac.sagemath.org:sage into public/combinat/sf/sp_orth
db8a17cLearning to spell my name...
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from fd17c25 to db8a17c

tscrim commented 10 years ago
comment:12

XP

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from db8a17c to 523c023

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

523c023Merge branch 'public/combinat/sf/sp_orth' of trac.sagemath.org:sage into public/combinat/sf/sp_orth
6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago
comment:16

Please do not use abbreviations like "lps" in the name of functions.

Nathann

fchapoton commented 9 years ago
comment:17

missing doctests in sf.py, see patchbot report

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 523c023 to 9bfd9e4

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

570bc49Merge branch 'public/categories/super_categories-18044' into 6.9.b1
b91cd82trac #18044 correct one typo in the doc
7fd1df2Merge branch 'public/categories/super_categories-18044' of trac.sagemath.org:sage into public/categories/super_categories-18044
0579337Some reviewer tweaks and doc additions.
aec22ccAdded one more test.
4b2046fMerge branch 'public/categories/super_categories-18044' into public/categories/filtered_algebras-17096
3f67b6bFixing trivial doctest due to changes in category heirarchy.
fa476ddFixing double-colon in INPUT block.
6cc8b84Reviewer changes with Darij.
9bfd9e4Merge branch 'public/categories/filtered_algebras-17096' into public/combinat/sf/sp_orth
tscrim commented 9 years ago

Dependencies: #17096

tscrim commented 9 years ago
comment:19

I added the requisite doctests and I also implemented functionality for bases of Sym to be considered filtered (although we could make these bases be ZZ / 2ZZ-graded but the ZZ-filtration is more natural), which requires #17096.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 9bfd9e4 to 57f92dd

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

57f92ddAdding some doctests and making things use the filtered basis.
d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db commented 9 years ago
comment:21

Travis, thanks for pointing this out to me. The st basis in ticket #19327 is very similar and since the group of permutation matrices are orthogonal matrices, it will be that o(lambda) has a positive st expansion.

There is an explicit formula for the change of basis from sp and o to Schur basis (that is almost exactly the same as the _s_to_sp_on_basis and _s_to_o_on_basis that you have implemented, it just alternates in sign by degree and the set of partitions you sum over are transposed). Is it faster to use the triangularity like you have here? Are you aware of it and have you tried it?

tscrim commented 9 years ago
comment:22

No, I was not aware of it and haven't tried it. I'm guessing that just comes from a möbius inversion? I suspect it will be significantly faster than using triangularity. Just to make sure I understand the computation, I keep the same coefficient up to a sign (which is the size of mu) and then take mu.transpose() as the basis element? And/Or do I need to transpose inside the coefficients?

d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db commented 9 years ago
comment:23

What I said in my last comment isn't quite right. It is in my paper with Mark Shimozono "Deformed universal characters for classical and affine algebras, Journal of Algebra, 299 (2006), pp. 33-61" (arXiv:math.CO/0404288) but it probably goes back to Koike and Terada or maybe even Littlewood. It is equation (4.1)+(4.5) for the orthogonal and (4.1)+(4.4) for the symplectic in my paper.

d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db commented 9 years ago
comment:24

I'm sorry, but I can't compile anything new right now so I am afraid to push anything. I can write functions on a working version of sage and I am pretty sure the following is right (following the model of _s_to_o_on_basis):

    def _o_to_s_on_basis(self, lam):
        import sage.libs.lrcalc.lrcalc as lrcalc
        from sage.combinat.partition import Partitions
        R = self.base_ring()
        return self._from_dict({ mu: R.sum(
            (-1)**j*lrcalc.lrcoef_unsafe(lam, mu, nu)
            for nu in Partitions(2*j)
              if all(nu.arm_length(i,i)==nu.leg_length(i,i)+1
                for i in range(nu.frobenius_rank())) )
            for j in range(sum(lam)//2+1)
            for mu in Partitions(sum(lam)-2*j) })

Moreover, if you switch arm and leg then that is the _sp_to_s_on_basis.

Your _s_to_o_on_basis has lots of extra looping going on that is not necessary. Because |lam|==|mu|+|nu| you can remove one sum. Because nu has to be an even partition, you don't need to run over j odd. Here is a suggested modification:

def _s_to_o_on_basis(self, lam):
    import sage.libs.lrcalc.lrcalc as lrcalc
    from sage.combinat.partition import Partitions
    R = self.base_ring()
    return self._from_dict({ mu: R.sum( lrcalc.lrcoef_unsafe(lam, mu, nu)
                                 for nu in Partitions(2*j)
                                     if all(x % 2 == 0 for x in nu))
                                 for j in range(sum(lam)//2+1)
                                 for mu in Partitions(sum(lam)-2*j) })
d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db commented 9 years ago
comment:25

I just thought about it and it would probably be better in _s_to_o_on_basis to loop over partitions of j and double the lengths of the parts of the partition.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

bd49490Changes from Mike and some added tests.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 57f92dd to bd49490

tscrim commented 9 years ago
comment:27

Thank you for those suggestions Mike. I implemented all of them, and they resulted in orders of magnitude speedups (including the inverse basis transformations).

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

a7ee857Adding the Shimozono-Zabrocki paper as a reference.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from bd49490 to a7ee857

tscrim commented 9 years ago
comment:29

At some point in the future, we should implement the single box version and the Hall-Littlewood analogs given in your paper with Mark.

d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db commented 9 years ago
comment:30

Here is an important question to resolve we can set to positive review. Is the following right?

sage: s(o.an_element().homogeneous_component(0))
2*s[]
sage: s(o.an_element()).homogeneous_component(0)
-s[]

I think the answer is no but I don't want to change it before I get full opinions. I think that we should look carefully to see if there other methods that are also filter dependent.

d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db commented 9 years ago
comment:31

Lets look carefully:

sage: o[2].is_homogeneous()
True
sage: s(o[2]).is_homogeneous()
False
sage: o.an_element().degree_zero_coefficient()
2
sage: s(o.an_element()).degree_zero_coefficient()
-1

degree_negation seems to work fine but that is special for these bases (and would not say work for the odd-symplectic basis or irreducible S_n character basis). It would be better if on filtered bases that these methods were done by coercion.

tscrim commented 9 years ago
comment:32

I would say that is okay because the COB morphism is as filtered algebras, so we can't expect homogeneous components to go to homogeneous components. However this should still work for top-degree homogeneous components.

So do you want me to do some surgery on the category of Sym bases and make 2 basis categories, one for the filtered and one for the graded? We could then have some generic code for the filtered that uses coercion for those methods that implicitly rely on the basis being graded.

d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db commented 9 years ago
comment:33

To me, the degree of the symmetric function is well defined, even if the basis is filtered. Degree is what we use on the classical symmetric function bases (not the size of the indexing partition...that is different). That means homogeneous component, degree and counit are not computed by the size of the indexing partition.

I think that it would be a good idea to factor out those and have two basis categories as you suggest.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from a7ee857 to c968782

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

c968782add Koike and Terada as a reference, link to full documentation for the bases in the top level
tscrim commented 9 years ago

Changed branch from public/combinat/sf/sp_orth to u/tscrim/sp_orth_broken

tscrim commented 9 years ago

Changed commit from c968782 to cac1d88

tscrim commented 9 years ago
comment:35

Okay, I've done some reworking of things at the category level, including adding a counit_by_coercion for realizations.

However I get MRO issues when dealing with the finite fields that I don't know how to deal with. I've convinced myself that the categories are almost correct; I want to make this change

         cat = HopfAlgebras(self.base().base_ring())
         return [self.base().Realizations(),
                 cat.Commutative().WithBasis(),
-                cat.Graded().Realizations()]
+                cat.Commutative().Graded().Realizations()]

But if I do that, I get KeyError: (225536, 70) from the c3 controlled!

So I don't know what to do at this point. Nicolas, Simon, do you have any ideas?

New commits:

cac1d88Doing some surgery on the categories.
darijgr commented 9 years ago
comment:37

Could this be related to the error in #11979 ?

Also, a trifle:

+class FilteredSymmetricFunctionsBases(Category_realization_of_parent):
+    r"""
+    The category of graded bases of the ring of symmetric functions.

s/graded/filtered/

(Thanks for fixing the categorical hack that made filtered bases pretend to be graded -- IIRC that was the reason why I was skeptical about this ticket!)

tscrim commented 9 years ago
comment:38

Yes, I would say so, and also on #15475. The most annoying thing is that it works for NCSF! However the reason why I can't add the commutative is something I have no understanding of what fails.

d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db commented 9 years ago
comment:39

To be clear, I'm finding when testing the file sfa.py there are errors

    s = SymmetricFunctions(FiniteField(29)).s()
Exception raised:
    Traceback (most recent call last):
...
    TypeError: Cannot create a consistent method resolution
    order (MRO) for bases GradedAlgebras.subcategory_class, CommutativeAlgebras.subcategory_class, Bialgebras.subcategory_class

Are you able to trigger them outside of the testing environment? When I enter them by hand they work fine.

tscrim commented 9 years ago
comment:40

Yes, those are the errors I get when doctesting sfa.py.

You have to do (in a fresh startup of Sage):

sage: SymmetricFunctions(Integers(23))
sage: SymmetricFunctions(FiniteField(23))

It also fails if you do it in the other order as well.

nthiery commented 9 years ago
comment:41

Hi!

Could it be that we are mixing categories parametrized by a base ring, and categories parametrized by the category that base ring? Something like HopfAlgebras(Fields()).XXX() and Bialgebras(GF(3)).YYY() ?