Implement k-bounded quotient space

[sagetrac-chrisjamesberg]

This will implement the k-bounded quotient space, whose basis is indexed by monomial symmetric functions indexed by k-bounded partitions. It is the dual Hopf algebra to the k-bounded subspace where the k-Schur functions live. In doing so, I have also fixed the bug from Ticket #13743.

CC: @sagetrac-sage-combinat @saliola @zabrocki @anneschilling @tscrim

Component: combinatorics

Keywords: symmetric functions, partitions

Author: Chris Berg, Mike Zabrocki

Reviewer: Anne Schilling

Merged: sage-5.6.beta2

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

[sagetrac-chrisjamesberg]

comment:8

Apply: trac_13762_k_quotient.patch

[tscrim]

comment:9

cc'ed since this conflicts with #13605.

[sagetrac-chrisjamesberg]

comment:10

Apply: trac_13762_k_quotient.patch

[anneschilling]

comment:11

Hi Chris,

Thanks for the new patch. I assume this fixes the coercion bug? Did you also fold

• trac_13762_addthis.patch
• trac_13762_possiblefix.patch

that were passed around by e-mail, or should they go after this patch still?

Anne

[anneschilling]

Reviewer: Anne Schilling

[anneschilling]

Changed author from Chris Berg to Chris Berg, Mike Zabrocki

[anneschilling]

Changed keywords from none to symmetric functions, partitions

[anneschilling]

comment:13

This patch implements the K-k-Schur functions and their duals. I tested this code my old private code and it gives the correct answers in the cases I checked.

Chris and Mike, here are a couple more comments I have:

• When building the documentation I get an error

sage/combinat/sf/new_kschur                                                                  
Sphinx error:
'ascii' codec can't decode byte 0xe2 in position 34698: ordinal not in range(128)

• Line 549 of the patch "Returns the symmetric functions. Needed to make TestSuite work" probably needs to be changed.

• You need an extra line after 650.

• In line 883 of new_kschur (in the patch) the dash is strange

.. [LamSchillingShimozono2010] T. Lam, A. Schilling, M.Shimozono, K-theory Schubert calculus of the affine Grassmannian, 
 	883	        Compositio Math. 146 (2010), 811�852. 

Also, this reference should probably appear in def K_kschur(self) as well.

• Line 887 """r should read r""" (or remove the r)

So much for now!

Anne

[sagetrac-chrisjamesberg]

comment:14

Anne,

Aren't the documentation error and the dash error related? I replaced the dash and the documentation builds fine on my machine.

Because the patch had changed so much, I didn't know where to put a line after 650, because line 650 had probably changed.

Everything else is fixed. Yes, all the other patches are folded into this.

Apply: trac_13762_k_quotient.patch

[anneschilling]

comment:15

Hi Chris,

Thanks for the changes. The line that should be added is after line 807 in the current version.
Other than that it looks good to me. If Mike is also happy, I'll let him set a positive review!

Anne

[zabrocki]

comment:16

Hi,
I am happy with this version of the patch. Chris, thanks for all the work and Anne thanks for the review.
-Mike

[anneschilling]

comment:17

There is a problem with the building of the documentation introduced by this patch

reading sources... [100%] structure                                                                                                                                    
/Applications/sage-5.5.rc0/local/lib/python2.7/site-packages/sage/combinat/sf/new_kschur.py:docstring of sage.combinat.sf.new_kschur.K_kSchur:9: WARNING: Duplicate explicit target name: "lamschillingshimozono2010".
/Applications/sage-5.5.rc0/local/lib/python2.7/site-packages/sage/combinat/sf/new_kschur.py:docstring of sage.combinat.sf.new_kschur.K_kSchur:9: WARNING: duplicate citation LamSchillingShimozono2010, other instance in /Applications/sage-5.5.rc0/devel/sage/doc/en/reference/sage/combinat/sf/new_kschur.rst

I think this needs to be fixed!

Anne

[zabrocki]

comment:18

There was a repeated reference. It should be fixed now.

Apply: trac_13762_k_quotient-2.patch

[anneschilling]

comment:19

Replying to @zabrocki:

There was a repeated reference. It should be fixed now.

Apply: trac_13762_k_quotient-2.patch

Looks good now! I leave the positive review.

Anne

[jdemeyer]

Work Issues: don't use assert

[jdemeyer]

comment:20

There has been a discussion about the usage of "assert" and you should not use "assert" for bad user input, only to check for actual bugs. Bad input should probably give a ValueError instead.

If there is any way at all to reproduce an AssertionError using documented public functions, that is by definition a bug.

[jdemeyer]

comment:21

Also, the commit message should not be one long line. You should wrap the message in multiple lines, but make sure the first line (which appears in hg log) makes sense by itself.

[zabrocki]

comment:22

Hi Jeroen,
There are a few 'assert' lines that we can clearly remove and change to ValueError, but there is one I am unsure about. Around line 599 in k_dual.py we have

if isinstance(c, Partition_class): 
      assert len(rest) == 0 

I don't see how to trigger this. Is it ok to leave it as is?

Some of our assertion errors that appear are triggered in code in free_module.py. Should I change that code here or open a new ticket?

[jdemeyer]

comment:23

Replying to @zabrocki:

if isinstance(c, Partition_class): 
      assert len(rest) == 0 

I don't see how to trigger this. Is it ok to leave it as is?

Absolutely. This is how assert should be used: to say "this condition is always true, without any further assumptions".

Some of our assertion errors that appear are triggered in code in free_module.py. Should I change that code here or open a new ticket?

I don't think you have to change it here, but at least make sure you don't introduce any new wrongly-used asserts.

[zabrocki]

Attachment: trac_13762_k_quotient.2.patch.gz

[zabrocki]

comment:24

OK. Our doctests still raise two assertion errors for calling 'coefficient' in free_module.py.

[anneschilling]

comment:25

Apply: trac_13762_k_quotient.2.patch

[anneschilling]

comment:26

Looks good to me now! I set it back to positive review.

Anne

[anneschilling]

Changed work issues from don't use assert to none

[jdemeyer]

Merged: sage-5.6.beta2

[jdemeyer]

comment:30

Please read some comments from #12313, which apply to this code:

(tl;dr: your code is badly written and #12313 will make it much slower)

Had a quick look. To simplify and speed up the tests a little bit, you can concentrate on one of the tests that's slow:

sage: cmd='dks4._test_associativity()'
sage: import cProfile,pstats
sage: s=pstats.Stats(cProfile.Profile().runctx(cmd,globals(),{}))
sage: S=s.sort_stats('cumulative')
sage: S.print_stats()
...
sage: S.print_callers()
...

the latter one essentially gives you the call graph, weighted by time contributed.

In fact it shows you pretty quickly that ShurFunctions were apparently VERY heavily relying on parents being cached:

X=dks4[0]+ 2*dks4[1] + 3*dks4[2]
(X*X)*X #wait quite a long time

This mainly uses dks4.product and you can follow the code from there to see this has not been written with runtime optimization in mind. Probably if you make some things cached the way there, you'll regain the original performance.

My first impression is that this code indeed will make a concrete realization of some structure, perform the operation, and throw away the concrete realization. Elements on the way basically ARE homs, hence all the homsets.

I think the normal behaviour of a CAS should be that a structure S is considered garbage and can be collected, unless the user has constructed some object O and keeps a reference to it, and O keeps a chain of references to S. Sadly, that was not the case for Sage, but this ticket is part of an attempt to make Sage behave "normally" in that department.

Hence, if the same structure is needed repeatedly during a computation, then the programmer should keep a reference to it locally, rather than relying on an external cache. And if different methods of an object O will use the same structure S, then it makes sense to store S as an attribute of O, in order to prevent S from being garbage collected as long as O is alive (but not longer than that).

I think what Nils wanted to say is: If other parts of the Sage library do not obey the general rules formulated in the preceding paragraph, but rely on an infinite external cache, then they need to be fixed. But the need to fix them should not prevent us from changing the infinite external cache to a finite external cache, because that is of benefit for all parts in the Sage library that follow the general rules.

[jdemeyer]

comment:31

See #13991 for a follow-up.