#8899 closed enhancement (fixed)
Implement non commutative symmetric functions
Reported by: | nthiery | Owned by: | sage-combinat |
---|---|---|---|
Priority: | major | Milestone: | sage-5.4 |
Component: | combinatorics | Keywords: | sd40, days38 |
Cc: | sage-combinat, chrisjamesberg, zabrocki, aschilling | Merged in: | sage-5.4.beta1 |
Authors: | Jason Bandlow, Chris Berg, Franco Saliola, Nicolas M. Thiéry | Reviewers: | Mike Zabrocki, Franco Saliola, Mike Hansen |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #12953, #12956, #12959, #13238, #13243, #5457 | Stopgaps: |
Description (last modified by )
This patch includes quasi symmetric functions as well (see #11929).
Each algebra is implemented as a Hopf algebra with realizations (the realizations being the various bases of the algebras).
- Bases implemented for NCSF, and change of bases between them:
- Complete
- Ribbon
- Elementary
- Psi (power sums)
- Phi (power sums)
- Bases implemented for QSym, and change of bases between them:
- Monomial
- Fundamental
There is also a method a_realization that returns a particular realization of the algebra. Computations that are not yet implemented in basis are performed by converting to a_realization(). Current implementation:
- NCSF.a_realization() returns the Complete basis
- QSym.a_realization() returns the Monomial basis
Dependencies:
- #12959 : provides the machinery for converting to a_realization for default implementations
- #13238 : integer matrices (required for the internal product in NCSF)
- #13243 : new methods for compositions
Apply:
Attachments (17)
Change History (71)
comment:1 Changed 8 years ago by
- Status changed from new to needs_work
comment:2 Changed 8 years ago by
- Type changed from defect to enhancement
comment:3 Changed 6 years ago by
- Dependencies set to #12953, #12956
- Description modified (diff)
comment:4 Changed 6 years ago by
- Cc chrisjamesberg added
- Keywords sd40 added
- Status changed from needs_work to needs_review
comment:5 Changed 6 years ago by
- Dependencies changed from #12953, #12956 to #12953, #12956, #12959, #13238, #13243
- Description modified (diff)
comment:6 Changed 6 years ago by
A note on the patch coproduct_with_realizations-fs.patch: an earlier version of this patch was folded into the patch at #5457. So this patch is not needed if that ticket gets merged before this ticket. (I've included it here so that the patchbot can run all doctests.)
If this ticket gets merged before #5457, then an easy rebase of #5457 will be required.
comment:7 Changed 6 years ago by
- Cc zabrocki added
I put the author names in alphabetical order. I don't know the policy on this. I hope this is okay.
comment:8 Changed 6 years ago by
(I think I learned something new about the patchbot: it ignores the order of the patches specified in the Apply directive and applies the patches in the order in which they get attached/updated.)
comment:9 follow-up: ↓ 10 Changed 6 years ago by
- Cc aschilling added
comment:10 in reply to: ↑ 9 ; follow-ups: ↓ 11 ↓ 12 Changed 6 years ago by
I think you guys need to add an entry in
doc/en/reference/combinat
so that NSym and QSym are included in the documentation!
Also, I spotted an OUTPUT without the : behind it. Aren't we supposed to use
INPUT:
x
-- explanation
i.e. a double dash after the variable to be explained?
Anne
comment:11 in reply to: ↑ 10 Changed 6 years ago by
- Status changed from needs_review to needs_work
- Work issues set to include new files in documentation ; clean up ReST markup
Thanks for catching these, Anne. We'll have to correct them.
Changed 6 years ago by
comment:12 in reply to: ↑ 10 Changed 6 years ago by
I rebased trac_11929_8899-ncsf-qsym-fs.patch on #12959.
Chris, can you fix the documentation as explained by Anne:
- Add an entry in
doc/en/reference/combinat
so that NSym and QSym are included in the documentation!
- Also, I spotted an OUTPUT without the : behind it.
- Proper syntax for INPUT blocks:
INPUT: - ``x`` -- explanation
i.e. a double dash after the variable to be explained [and a space after the initial dash]
Changed 6 years ago by
comment:13 follow-up: ↓ 14 Changed 6 years ago by
Two new small patches.
trac_11929_8899-fix_skewby-fs.patch:
Fixes things so that the following raises an error:F([2,1]).skew_by([1])
trac_11929_8899-add_degree_to_elementmethods-fs.patch:
addesElementMethods.degree
andElementMethods.is_homogeneous
toGradedAlgebrasWithBasis
(I extracted these from a separate patch on the sage-combinat queue).
Outstanding question about the degree of an element: what do we want as the default behaviour? Should it:
- raise an error if the element is not homogeneous; or
- return the maximum of the degrees of the homogeneous summands?
Changed 6 years ago by
comment:14 in reply to: ↑ 13 Changed 6 years ago by
Replying to saliola:
Two new small patches.
trac_11929_8899-fix_skewby-fs.patch:
Fixes things so that the following raises an error:F([2,1]).skew_by([1])
trac_11929_8899-add_degree_to_elementmethods-fs.patch:
addesElementMethods.degree
andElementMethods.is_homogeneous
toGradedAlgebrasWithBasis
(I extracted these from a separate patch on the sage-combinat queue).Outstanding question about the degree of an element: what do we want as the default behaviour? Should it:
- raise an error if the element is not homogeneous; or
- return the maximum of the degrees of the homogeneous summands?
Based on the discussion on sage-combinat-devel, I updated trac_11929_8899-add_degree_to_elementmethods-fs.patch:
- add methods
maximal_degree
andhomogeneous_degree
inGradedAlgebrasWithBasis
- as a default in
GradedAlgebrasWithBasis
, setdegree = homogeneous_degree
- for NCSF/QSym,
degree
is redefined to bemaximal_degree
comment:15 Changed 6 years ago by
trac_11929_8899-include_doc_in_reference_manual-fs.patch deals with documentation:
- added entries in reference manual
- fixed markup to adhere to Sage standards and to build correctly without warnings
comment:16 Changed 6 years ago by
- Status changed from needs_work to needs_review
- Work issues include new files in documentation ; clean up ReST markup deleted
Changed 6 years ago by
Changed 6 years ago by
comment:17 Changed 6 years ago by
The patch trac_11929_8899-modify_duality_method_names-fs.patch modifies the duality method names to conform to #13372. Namely:
object.dual
returns the dual object:sage: N.dual() Quasisymmetric functions over the Rational Field sage: S.dual() Quasisymmetric functions over the Rational Field on the Monomial basis sage: R.dual() Quasisymmetric functions over the Rational Field on the Fundamental basis
dual_pairing
becameduality_pairing
comment:18 Changed 6 years ago by
- Description modified (diff)
Changed 6 years ago by
comment:19 Changed 6 years ago by
- Description modified (diff)
trac_11929_8899-is_symmetric-fs.patch : fixes a bug Mike found in is_symmetric
and renames to_sym
to to_symmetric_function
.
Changed 6 years ago by
comment:20 Changed 6 years ago by
trac_11929_8899-internal_product_fix-fs.patch fixes an issue with categories since we haven't defined an internal product for QSym.
comment:21 Changed 6 years ago by
- Description modified (diff)
comment:22 Changed 6 years ago by
- Description modified (diff)
Minor changes to documentation plus the addition of a tutorial for quasi-symmetric function and additional doc tests and examples. The doc tests added use functionality that is in sage-5.3.beta2.
comment:23 Changed 6 years ago by
- Description modified (diff)
comment:24 Changed 6 years ago by
For the patchbot
Apply: trac_11929_8899-ncsf-qsym-folded-fs.patch, trac_11929_8899-additional_documentation-fs.patch
Changed 6 years ago by
comment:25 Changed 6 years ago by
Hello Mike,
Thank you very much for your review, and your improvements to the documentation!
I folded all the patches that you've seen, including your patch. And I created one more that makes changes to the documentation, adds some doctests, etc.
So please review this last patch: trac_11929_8899-additional_documentation-fs.patch.
Here is a summary of the changes:
- I noticed that some of the bases of NCSF and QSym had no documentation when one asks for the documentation using the command:
NCSF.Ribbon?
So I fixed that for all the bases.
- In a few places, you used the letter F to refer to an arbitrary quasi-symmetric function. Since this is the prefix for the Fundamental basis, I decided to change this to another letter (I used H).
- I made a some changes to your tutorial that I hope improve the exposition.
Changed 6 years ago by
Changed 6 years ago by
Changed 6 years ago by
comment:26 Changed 6 years ago by
- Description modified (diff)
I folded the additional documentation patches (mine and Mike's) into the main patch since Mike gave mine a positive review and I positively reviewed Mike's changes.
And I posted one more patch that adds a new method from_polynomial
to QSym.
Only the patch trac_11929_8899-from_polynomial-fs.patch needs review.
comment:27 Changed 6 years ago by
Patchbot, please apply the following patches and tell me all tests pass!
Apply: trac_11929_8899-ncsf-qsym-folded-fs.patch, trac_11929_8899-from_polynomial-fs.patch
comment:28 Changed 6 years ago by
- Reviewers set to Mike Zabrocki, Franco Saliola, Mike Hansen
- Status changed from needs_review to positive_review
trac_11929_8899-from_polynomial-fs.patch looks good to me
comment:29 Changed 6 years ago by
- Status changed from positive_review to needs_work
I have an issue with missing documentation. For example, the method is_symmetric is not appearing in the documentation for qsym.py. Can someone explain why?
comment:30 follow-up: ↓ 31 Changed 6 years ago by
comment:31 in reply to: ↑ 30 ; follow-up: ↓ 33 Changed 6 years ago by
Replying to mhansen:
Thanks Mike! I just tested and confirm that when I apply the patch that is attached to #9107 and then recompile, the missing documentation for methods appears. I will post a few more corrections to the documentation shortly (e.g. coproduct_on_generators() in ncsf.py is weird and that probably was one of the missing methods before).
Changed 6 years ago by
comment:32 Changed 6 years ago by
- Description modified (diff)
- Status changed from needs_work to positive_review
comment:33 in reply to: ↑ 31 ; follow-up: ↓ 34 Changed 6 years ago by
comment:34 in reply to: ↑ 33 ; follow-up: ↓ 36 Changed 6 years ago by
Replying to SimonKing:
Does that mean #9107 should be a dependency?
I would not bother. There are already plenty of spots in Sage where the documentation does not build properly because of improper support for nested classes; this just adds another occurence. And everything will be fixed at once when #9107 will be merged, with no action to be taken on those spots.
Cheers,
Nicolas
comment:35 Changed 6 years ago by
- Description modified (diff)
I folded these three patches together and cleaned up the commit message (so that that patchbot doesn't complain):
comment:36 in reply to: ↑ 34 Changed 6 years ago by
Replying to nthiery:
Replying to SimonKing:
Does that mean #9107 should be a dependency?
I would not bother. There are already plenty of spots in Sage where the documentation does not build properly because of improper support for nested classes; this just adds another occurence. And everything will be fixed at once when #9107 will be merged, with no action to be taken on those spots.
Another reason not to: the docstrings for QSym / NCSF are detailed and most of the functionality is demonstrated in the examples there.
comment:37 Changed 6 years ago by
- Milestone changed from sage-wishlist to sage-5.3
This patch is ready to go, so I'm setting the milestone to sage-5.3 (instead of sage-wishlist).
An unrelated test failed on one of the patchbots, but I think this is just a glitch. I tried kicking it, so we'll see what happens. Is it necessary that all patchbots be happy before the patch is merged?
comment:38 Changed 5 years ago by
- Milestone changed from sage-5.3 to sage-5.4
Changed 5 years ago by
comment:39 Changed 5 years ago by
- Description modified (diff)
- Status changed from positive_review to needs_info
trac_11929_8899-ncsf-qsym-repr-fix-fs.patch modifies _repr_
to conform to the standards set out in #13404.
Note: this patch does not depend on #13404.
Apply: trac_11929_8899-ncsf-qsym-final.patch, trac_11929_8899-ncsf-qsym-repr-fix-fs.patch
comment:40 Changed 5 years ago by
- Status changed from needs_info to needs_review
comment:41 Changed 5 years ago by
- Status changed from needs_review to needs_work
comment:42 Changed 5 years ago by
- Status changed from needs_work to needs_review
comment:43 Changed 5 years ago by
I checked the patch, and am ok with it. Thanks Franco!
Assuming that all tests pass (the failures currently reported by the patchbot seem unrelated), you can set it back to positive review on my behalf!
Cheers,
Nicolas
comment:44 Changed 5 years ago by
- Status changed from needs_review to positive_review
comment:45 Changed 5 years ago by
- Dependencies changed from #12953, #12956, #12959, #13238, #13243 to #12953, #12956, #12959, #13238, #13243, #5457
comment:46 Changed 5 years ago by
- Merged in set to sage-5.4.beta1
- Resolution set to fixed
- Status changed from positive_review to closed
comment:47 Changed 5 years ago by
- Merged in sage-5.4.beta1 deleted
- Resolution fixed deleted
- Status changed from closed to new
With the new version, but I'm seeing failures which didn't happen with earlier versions:
sage -t -force_lib devel/sage/sage/combinat/ncsf_qsym/ncsf.py ********************************************************************** File "/release/merger/sage-5.4.beta1/devel/sage-main/sage/combinat/ncsf_qsym/ncsf.py", line 493: sage: R.to_symmetric_function Expected: Generic morphism: From: Non-Commutative Symmetric Functions over the Rational Field in the Ribbon basis To: Symmetric Function Algebra over Rational Field, Schur symmetric functions as basis Got: Generic morphism: From: Non-Commutative Symmetric Functions over the Rational Field in the Ribbon basis To: Symmetric Functions over Rational Field in the Schur basis **********************************************************************
comment:48 follow-ups: ↓ 49 ↓ 50 Changed 5 years ago by
I double-checked, and the phrase "in the Schur basis" does not appear in the patches on this ticket.
I know that #13404 claims not to have been merged yet, but did you happen to merge it in sage-5.4.beta1? I think that ticket would have caused this change in the _repr_
.
comment:49 in reply to: ↑ 48 Changed 5 years ago by
Replying to saliola:
I double-checked, and the phrase "in the Schur basis" does not appear in the patches on this ticket.
I know that #13404 claims not to have been merged yet, but did you happen to merge it in sage-5.4.beta1? I think that ticket would have caused this change in the
_repr_
.
Franco is right. I will fix this in 13404 and put a dependency on 8899 there.
Best,
Anne
comment:50 in reply to: ↑ 48 Changed 5 years ago by
- Merged in set to sage-5.4.beta1
- Resolution set to fixed
- Status changed from new to closed
Replying to saliola:
I double-checked, and the phrase "in the Schur basis" does not appear in the patches on this ticket.
I know that #13404 claims not to have been merged yet, but did you happen to merge it in sage-5.4.beta1? I think that ticket would have caused this change in the
_repr_
.
I always test a bunch of tickets together, and in this case I included indeed #13404. So I will remove #13404 for now.
comment:51 follow-up: ↓ 52 Changed 5 years ago by
This patch abuses assert
and AssertionError
. assert
should not be used for control flow. An assert
checks something which should always be true, a failed assertion is always a bug in the program.
For example:
sage: R = NonCommutativeSymmetricFunctions(QQ).R() sage: R.skew([2,1], [1]) Traceback (most recent call last): ... AssertionError: x must be an element of Non-Commutative Symmetric Functions over the Rational Field
This is a simple user mistake, for which assert
is not right.
I think this must be fixed.
comment:52 in reply to: ↑ 51 Changed 5 years ago by
Replying to jdemeyer:
This patch abuses
assert
andAssertionError
.assert
should not be used for control flow. Anassert
checks something which should always be true, a failed assertion is always a bug in the program.For example:
sage: R = NonCommutativeSymmetricFunctions(QQ).R() sage: R.skew([2,1], [1]) Traceback (most recent call last): ... AssertionError: x must be an element of Non-Commutative Symmetric Functions over the Rational FieldThis is a simple user mistake, for which
assert
is not right.I think this must be fixed.
I guess that's ok after all. See the same comment on #5457.
comment:53 Changed 5 years ago by
This is a better example from this patch on how not to use assert:
try: assert self.is_homogeneous() return self.parent().degree_on_basis(self.leading_support()) except AssertionError: raise ValueError("Element is not homogeneous.")
And this is an easily made mistake, it should give a TypeError
:
def from_polynomial(self, f, check=True): ... assert self.base_ring() == f.base_ring()
You could even do:
if check and self.base_ring() != f.base_ring(): raise TypeError(...)
comment:54 Changed 5 years ago by
- Keywords days38 added
Apply: trac_11929_8899-ncsf-qsym-folded-fs.patch, trac_11929_8899-additional_documentation-fs.patch
(for the patchbot)