Opened 8 years ago

Closed 7 years ago

#15536 closed enhancement (fixed)

Implement symplectic and orthogonal bases of Sym

Reported by: tscrim Owned by: sage-combinat
Priority: major Milestone: sage-6.10
Component: combinatorics Keywords: days54, sym
Cc: sage-combinat, darij, SimonKing, nthiery Merged in:
Authors: Travis Scrimshaw Reviewers: Mike Zabrocki
Report Upstream: N/A Work issues:
Branch: 5b492f3 (Commits, GitHub, GitLab) Commit: 5b492f37fd2918dcc66e16ff446f5b30fe1bb9a4
Dependencies: #17096 Stopgaps:

Status badges

Description

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.

Change History (59)

comment:1 Changed 8 years ago by tscrim

  • Status changed from new to needs_review

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.

comment:2 follow-up: Changed 8 years ago by darij

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.

comment:3 Changed 8 years ago by git

  • Commit changed from 9536f54a96401a5bdabdaa56dc65640f8bb1bfda to 223b11b19d050597267d29150fa1e2cb12a3861b

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

comment:4 Changed 8 years ago by git

  • Commit changed from 223b11b19d050597267d29150fa1e2cb12a3861b to 9ea2a2c1eafde6abc39d819002cff6ea43984108

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

9ea2a2cAdded comment about ZZ / 2ZZ grading.

comment:5 in reply to: ↑ 2 Changed 8 years ago by tscrim

Replying to darij:

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.

comment:6 Changed 8 years ago by darij

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.

Last edited 8 years ago by darij (previous) (diff)

comment:7 Changed 8 years ago by git

  • Commit changed from 9ea2a2c1eafde6abc39d819002cff6ea43984108 to fd17c25145d136e2fc342b450d38f6441ff09d24

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

fd17c25Documentation tweaks/typo fixes.

comment:8 Changed 8 years ago by tscrim

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

comment:9 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:10 Changed 8 years ago by chapoton

There is a typo "Scirmshaw"

comment:11 Changed 8 years ago by git

  • Commit changed from fd17c25145d136e2fc342b450d38f6441ff09d24 to db8a17c1fbe046c00ddfcb4b477ef22642ae6a37

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

comment:12 Changed 8 years ago by tscrim

XP

comment:13 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:14 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:15 Changed 7 years ago by git

  • Commit changed from db8a17c1fbe046c00ddfcb4b477ef22642ae6a37 to 523c023369bcf6f4c0fa2631b09e95b3637fba2c

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

comment:16 Changed 7 years ago by ncohen

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

Nathann

comment:17 Changed 7 years ago by chapoton

  • Status changed from needs_review to needs_work

missing doctests in sf.py, see patchbot report

comment:18 Changed 7 years ago by git

  • Commit changed from 523c023369bcf6f4c0fa2631b09e95b3637fba2c to 9bfd9e49ddda9fb8e1984b914b21921dc1050c03

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

comment:19 Changed 7 years ago by tscrim

  • Dependencies set to #17096
  • Milestone changed from sage-6.4 to sage-6.10
  • Status changed from needs_work to needs_review

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.

comment:20 Changed 7 years ago by git

  • Commit changed from 9bfd9e49ddda9fb8e1984b914b21921dc1050c03 to 57f92dd1a206bb5af2ed00e4135ded0c586e99db

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

57f92ddAdding some doctests and making things use the filtered basis.

comment:21 Changed 7 years ago by zabrocki

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?

comment:22 Changed 7 years ago by tscrim

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?

comment:23 Changed 7 years ago by zabrocki

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.

comment:24 Changed 7 years ago by zabrocki

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

comment:25 Changed 7 years ago by zabrocki

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.

comment:26 Changed 7 years ago by git

  • Commit changed from 57f92dd1a206bb5af2ed00e4135ded0c586e99db to bd49490b1b6c006ee43eb5dbdb98aa5d98ae541f

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

bd49490Changes from Mike and some added tests.

comment:27 Changed 7 years ago by tscrim

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

comment:28 Changed 7 years ago by git

  • Commit changed from bd49490b1b6c006ee43eb5dbdb98aa5d98ae541f to a7ee8574e639366db30427852671b0ee1bfb0cf3

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

a7ee857Adding the Shimozono-Zabrocki paper as a reference.

comment:29 Changed 7 years ago by tscrim

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

comment:30 Changed 7 years ago by zabrocki

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.

comment:31 Changed 7 years ago by zabrocki

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.

comment:32 Changed 7 years ago by tscrim

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.

comment:33 Changed 7 years ago by zabrocki

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.

comment:34 Changed 7 years ago by git

  • Commit changed from a7ee8574e639366db30427852671b0ee1bfb0cf3 to c968782e777fe17f42c5d316412e15feba1255cd

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

comment:35 Changed 7 years ago by tscrim

  • Branch changed from public/combinat/sf/sp_orth to u/tscrim/sp_orth_broken
  • Cc SimonKing nthiery added
  • Commit changed from c968782e777fe17f42c5d316412e15feba1255cd to cac1d88d687705fa90de0edac1b472f6e2d623b4

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.

comment:36 Changed 7 years ago by tscrim

  • Status changed from needs_review to needs_info

comment:37 Changed 7 years ago by darij

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

comment:38 Changed 7 years ago by tscrim

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.

comment:39 Changed 7 years ago by zabrocki

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.

comment:40 Changed 7 years ago by tscrim

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.

comment:41 follow-up: Changed 7 years ago by nthiery

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() ?

comment:42 in reply to: ↑ 41 Changed 7 years ago by tscrim

Replying to nthiery:

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() ?

AFAIK we aren't mixing things like that. This is that wonderful category refinement issue that somehow was somehow magically working beforehand, but I think that was because the categories for the bases weren't quite correct.

comment:43 Changed 7 years ago by tscrim

I wonder if the problem stems from this line in __classcall_private__ of Modules:

if base_ring in _Fields or (isinstance(base_ring, Category)
                            and base_ring.is_subcategory(_Fields)):

or this line in extra_super_categories of FilteredAlgebras:

if base_ring in Fields:

and that one/both of these triggers the category refinement and breaks the MRO, which was in the process of being constructed when these were called.

sage: R = Integers(7)
sage: R.category()
Join of Category of finite commutative rings and Category of subquotients of monoids and Category of quotients of semigroups and Category of finite enumerated sets
sage: HopfAlgebras(R)
Category of hopf algebras over Ring of integers modulo 7
sage: R.category()
Join of Category of finite fields and Category of subquotients of monoids and Category of quotients of semigroups

Yet this still doesn't explain why this works for NCSF. I think that might be a key in figuring out what is going wrong.

comment:44 Changed 7 years ago by zabrocki

You could be on to something here. If I delete the following lines:

-        if dispatch:
-            if base_ring in _Fields or (isinstance(base_ring, Category)
-                                        and base_ring.is_subcategory(_Fields)):
-                from vector_spaces import VectorSpaces
-                return VectorSpaces(base_ring, check=False)

I find that your example in comment 40 does not raise an error.

comment:45 Changed 7 years ago by tscrim

  • Branch changed from u/tscrim/sp_orth_broken to public/combinat/sf/sp_orth
  • Commit changed from cac1d88d687705fa90de0edac1b472f6e2d623b4 to 8e690e2a13b8c266f0d6a46c7c9b01a01aa48933

However, I don't think that is the right solution. :/ The check is reasonable and necessary.

Granted, my current proposal is a major hack, but I don't think too many people will be creating many instances of Sym over various large finite fields (and there are more computationally intensive parts necessary for working with Sym). I'm tired of trying to deal with this here, so I just checked if the base ring was a field before any categories get created.

There is also another issue with C3 in that I get a KeyError if I make this change:

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

This is what it should be, but because everything commutative will come from the cat.Commutative().WithBasis(), I think we are okay for now.

I really would like to push this ticket in and later reach in and fix the category-refinement/MRO/C3 issues on a separate ticket.


New commits:

8263b10Merge branch 'develop' into public/combinat/sf/sp_orth
b151195Merge branch 'develop' into public/combinat/sf/sp_orth
8e690e2Some hacks and FIXMEs.

comment:46 Changed 7 years ago by tscrim

  • Status changed from needs_info to needs_review

I should also mention that there are other places where category refinement would make sense, such as for finite-dimensional algebras after doing an is_commutative or is_unital test, so IMO it could be useful beyond prime testing for finite fields.

comment:47 Changed 7 years ago by zabrocki

What does the line "R in Fields()" do? It looks to me like it returns True or False and goes on to the next line.

comment:48 Changed 7 years ago by tscrim

It makes sure that R has had its category refined (if it needs to). Thus this is not done in the process of building the MRO/category heirarchy for Sym.

comment:49 Changed 7 years ago by zabrocki

  • Status changed from needs_review to needs_work

I don't think that this is a bad way of resolving this, but it may be pushing the problem elsewhere. I am seeing:

File "combinat/ncsf_qsym/qsym.py", line 1873, in sage.combinat.ncsf_qsym.qsym.QuasiSymmetricFunctions.Monomial.lambda_of_monomial
Failed example:
    M = QuasiSymmetricFunctions(Integers(5)).Monomial()

Are ncsf/qsym going to require the same hack? Will every combinatorial Hopf algebra require it?

comment:50 Changed 7 years ago by tscrim

I've not been getting those errors, but Volker just posted on #19397 an issue that smells like the same thing. So right now I'm thinking, "*!@$, we have to deal with this now". :/ Nicolas, Simon, I will need you two to get involved now I think.

comment:51 Changed 7 years ago by zabrocki

One strange feature is that the error that you post in comment 40 is triggered on QSym and NCSymD but not on NCSF or NCSym (at least on my computer). That is,

sage: NCSymD = SymmetricFunctionsNonCommutingVariablesDual(FiniteField(23))
sage: NCSymD = SymmetricFunctionsNonCommutingVariablesDual(Integers(23))

triggers an error but

sage: NCSym = SymmetricFunctionsNonCommutingVariables(FiniteField(23))
sage: NCSym = SymmetricFunctionsNonCommutingVariables(Integers(23))

does not.

comment:52 Changed 7 years ago by tscrim

The NCSymD is caused by this part of the __init__:

        Sym = SymmetricFunctions(self.base_ring())
        Sym_h_to_w = Sym.h().module_morphism(w.sum_of_partitions,
                                             triangular='lower',
                                             inverse_on_support=w._set_par_to_par,
                                             codomain=w, category=category)

Ah...QSym fails for the same reason...

I think they all will need this hack for now. I know this is pushing the problem further down, but I don't know of a way to resolve it at present (or at least without forcing a prime check for finite rings).

Although there is the issue on comment:45 that is likely unrelated and needs a fix at some point too... I think there might be some issue(s) with join categories...

I also have been working on #19397 under the assumption that these are the same problem. However I am pretty sure this is not the case now and they are different problems (I would love to be wrong).

comment:53 Changed 7 years ago by git

  • Commit changed from 8e690e2a13b8c266f0d6a46c7c9b01a01aa48933 to d8d3eda712c9b8eba85fed818ef385e56ddb16b3

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

d8d3edaadditions to NCSF/QSym/Sym/NCSym/NCSymD to ensure that MRO errors are not triggered

comment:54 Changed 7 years ago by zabrocki

I agree. In the end this is a minor change as a hack. It doesn't locate the problem, but it does fix it from being triggered. I've pushed some changes which add doctests and replaced assert(R in Rings()) with assert(R in Fields() or R in Rings()) in in the __init__ method for all of these Hopf algebras. I'll get back to Jean-Baptist's Hopf algebra implementations after we resolve these issues and see if his code can be used to get around these problem.

comment:55 Changed 7 years ago by git

  • Commit changed from d8d3eda712c9b8eba85fed818ef385e56ddb16b3 to 5b492f37fd2918dcc66e16ff446f5b30fe1bb9a4

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

c4c1416Merge branch 'develop' into public/combinat/sf/sp_orth
0513f6aMerge branch 'public/combinat/sf/sp_orth' of trac.sagemath.org:sage into public/combinat/sf/sp_orth
5b492f3Fixing non-ascii character.

comment:56 Changed 7 years ago by tscrim

  • Status changed from needs_work to needs_review

I'm okay with things. So let's just leave this hack in there since it works for now. It is also documented for testing later on. Therefore I think we are back to needs review.

comment:57 Changed 7 years ago by zabrocki

  • Reviewers set to Mike Zabrocki
  • Status changed from needs_review to positive_review

I think it looks good and all tests pass. Positive review.

comment:58 Changed 7 years ago by tscrim

Thanks Mike!

comment:59 Changed 7 years ago by vbraun

  • Branch changed from public/combinat/sf/sp_orth to 5b492f37fd2918dcc66e16ff446f5b30fe1bb9a4
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.