Opened 8 years ago
Closed 7 years ago
#15536 closed enhancement (fixed)
Implement symplectic and orthogonal bases of Sym
Reported by:  tscrim  Owned by:  sagecombinat 

Priority:  major  Milestone:  sage6.10 
Component:  combinatorics  Keywords:  days54, sym 
Cc:  sagecombinat, 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: 
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
 Status changed from new to needs_review
comment:2 followup: ↓ 5 Changed 8 years ago by
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/sage5.13.beta1/local/lib/python2.7/sitepackages/sage/misc/sage_unittest.py", line 282, in run test_method(tester = tester) File "/home/darij/gitsage/sage5.13.beta1/local/lib/python2.7/sitepackages/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/sage5.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/2ZZgrading.
comment:3 Changed 8 years ago by
 Commit changed from 9536f54a96401a5bdabdaa56dc65640f8bb1bfda to 223b11b19d050597267d29150fa1e2cb12a3861b
comment:4 Changed 8 years ago by
 Commit changed from 223b11b19d050597267d29150fa1e2cb12a3861b to 9ea2a2c1eafde6abc39d819002cff6ea43984108
Branch pushed to git repo; I updated commit sha1. New commits:
9ea2a2c  Added comment about ZZ / 2ZZ grading.

comment:5 in reply to: ↑ 2 Changed 8 years ago by
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/2ZZgrading.
Again, not the category, but it's nice to know these things.
New commits:
9ea2a2c  Added comment about ZZ / 2ZZ grading.

comment:6 Changed 8 years ago by
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.
comment:7 Changed 8 years ago by
 Commit changed from 9ea2a2c1eafde6abc39d819002cff6ea43984108 to fd17c25145d136e2fc342b450d38f6441ff09d24
Branch pushed to git repo; I updated commit sha1. New commits:
fd17c25  Documentation tweaks/typo fixes.

comment:8 Changed 8 years ago by
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 sagecombinatdevel discussion).
comment:9 Changed 8 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:10 Changed 8 years ago by
There is a typo "Scirmshaw"
comment:11 Changed 8 years ago by
 Commit changed from fd17c25145d136e2fc342b450d38f6441ff09d24 to db8a17c1fbe046c00ddfcb4b477ef22642ae6a37
comment:12 Changed 8 years ago by
XP
comment:13 Changed 8 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:14 Changed 8 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:15 Changed 7 years ago by
 Commit changed from db8a17c1fbe046c00ddfcb4b477ef22642ae6a37 to 523c023369bcf6f4c0fa2631b09e95b3637fba2c
Branch pushed to git repo; I updated commit sha1. New commits:
523c023  Merge branch 'public/combinat/sf/sp_orth' of trac.sagemath.org:sage into public/combinat/sf/sp_orth

comment:16 Changed 7 years ago by
Please do not use abbreviations like "lps" in the name of functions.
Nathann
comment:17 Changed 7 years ago by
 Status changed from needs_review to needs_work
missing doctests in sf.py, see patchbot report
comment:18 Changed 7 years ago by
 Commit changed from 523c023369bcf6f4c0fa2631b09e95b3637fba2c to 9bfd9e49ddda9fb8e1984b914b21921dc1050c03
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
570bc49  Merge branch 'public/categories/super_categories18044' into 6.9.b1

b91cd82  trac #18044 correct one typo in the doc

7fd1df2  Merge branch 'public/categories/super_categories18044' of trac.sagemath.org:sage into public/categories/super_categories18044

0579337  Some reviewer tweaks and doc additions.

aec22cc  Added one more test.

4b2046f  Merge branch 'public/categories/super_categories18044' into public/categories/filtered_algebras17096

3f67b6b  Fixing trivial doctest due to changes in category heirarchy.

fa476dd  Fixing doublecolon in INPUT block.

6cc8b84  Reviewer changes with Darij.

9bfd9e4  Merge branch 'public/categories/filtered_algebras17096' into public/combinat/sf/sp_orth

comment:19 Changed 7 years ago by
 Dependencies set to #17096
 Milestone changed from sage6.4 to sage6.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
 Commit changed from 9bfd9e49ddda9fb8e1984b914b21921dc1050c03 to 57f92dd1a206bb5af2ed00e4135ded0c586e99db
Branch pushed to git repo; I updated commit sha1. New commits:
57f92dd  Adding some doctests and making things use the filtered basis.

comment:21 Changed 7 years ago by
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
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
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. 3361" (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
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
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
 Commit changed from 57f92dd1a206bb5af2ed00e4135ded0c586e99db to bd49490b1b6c006ee43eb5dbdb98aa5d98ae541f
Branch pushed to git repo; I updated commit sha1. New commits:
bd49490  Changes from Mike and some added tests.

comment:27 Changed 7 years ago by
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
 Commit changed from bd49490b1b6c006ee43eb5dbdb98aa5d98ae541f to a7ee8574e639366db30427852671b0ee1bfb0cf3
Branch pushed to git repo; I updated commit sha1. New commits:
a7ee857  Adding the ShimozonoZabrocki paper as a reference.

comment:29 Changed 7 years ago by
At some point in the future, we should implement the single box version and the HallLittlewood analogs given in your paper with Mark.
comment:30 Changed 7 years ago by
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
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 oddsymplectic 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
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 topdegree 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
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
 Commit changed from a7ee8574e639366db30427852671b0ee1bfb0cf3 to c968782e777fe17f42c5d316412e15feba1255cd
Branch pushed to git repo; I updated commit sha1. New commits:
c968782  add Koike and Terada as a reference, link to full documentation for the bases in the top level

comment:35 Changed 7 years ago by
 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:
cac1d88  Doing some surgery on the categories.

comment:36 Changed 7 years ago by
 Status changed from needs_review to needs_info
comment:37 Changed 7 years ago by
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
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
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
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 followup: ↓ 42 Changed 7 years ago by
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
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()
andBialgebras(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
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
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
 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 categoryrefinement/MRO/C3 issues on a separate ticket.
New commits:
8263b10  Merge branch 'develop' into public/combinat/sf/sp_orth

b151195  Merge branch 'develop' into public/combinat/sf/sp_orth

8e690e2  Some hacks and FIXMEs.

comment:46 Changed 7 years ago by
 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 finitedimensional 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
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
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
 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
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
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
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
 Commit changed from 8e690e2a13b8c266f0d6a46c7c9b01a01aa48933 to d8d3eda712c9b8eba85fed818ef385e56ddb16b3
Branch pushed to git repo; I updated commit sha1. New commits:
d8d3eda  additions to NCSF/QSym/Sym/NCSym/NCSymD to ensure that MRO errors are not triggered

comment:54 Changed 7 years ago by
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 JeanBaptist'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
 Commit changed from d8d3eda712c9b8eba85fed818ef385e56ddb16b3 to 5b492f37fd2918dcc66e16ff446f5b30fe1bb9a4
comment:56 Changed 7 years ago by
 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
 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
Thanks Mike!
comment:59 Changed 7 years ago by
 Branch changed from public/combinat/sf/sp_orth to 5b492f37fd2918dcc66e16ff446f5b30fe1bb9a4
 Resolution set to fixed
 Status changed from positive_review to closed
Darij (or anyone else who wants to review this),
Nicolas said it's fine being in
GradedHopfAlgebrasWithBasis
sinceSym
does admit a graded basis, even if the given basis itself is not graded.