Opened 8 years ago

Closed 5 years ago

Last modified 5 years ago

#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 saliola)

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)

trac_11929_8899-ncsf-qsym-fs.patch (126.5 KB) - added by saliola 5 years ago.
trac_11929_8899-fix_skewby-fs.patch (2.1 KB) - added by saliola 5 years ago.
trac_11929_8899-add_degree_to_elementmethods-fs.patch (7.1 KB) - added by saliola 5 years ago.
trac_11929_8899-include_doc_in_reference_manual-fs.patch (47.4 KB) - added by saliola 5 years ago.
trac_11929_8899-modify_duality_method_names-fs.patch (15.4 KB) - added by saliola 5 years ago.
trac_11929_8899-is_symmetric-fs.patch (4.8 KB) - added by saliola 5 years ago.
trac_11929_8899-internal_product_fix-fs.patch (2.6 KB) - added by saliola 5 years ago.
trac_11929_8899-additional_documentation-mz.patch (23.7 KB) - added by zabrocki 5 years ago.
minor doc fixes and a quasi-symmetric function tutorial
trac_11929_8899-antipode_by_coercion_in_category-fs.patch (3.6 KB) - added by saliola 5 years ago.
rebased to 5.3.beta2
coproduct_with_realizations-fs.patch (2.7 KB) - added by saliola 5 years ago.
extra doctests for coproduct and counit
trac_11929_8899-additional_documentation-fs.patch (32.0 KB) - added by saliola 5 years ago.
additional-addional-documentation-mz.patch (5.4 KB) - added by saliola 5 years ago.
trac_11929_8899-ncsf-qsym-folded-fs.patch (156.3 KB) - added by saliola 5 years ago.
trac_11929_8899-from_polynomial-fs.patch (6.2 KB) - added by saliola 5 years ago.
trac_11929_8899_minor_docfix-mz.patch (1.0 KB) - added by zabrocki 5 years ago.
trac_11929_8899-ncsf-qsym-final.patch (161.3 KB) - added by saliola 5 years ago.
APPLY ONLY THIS PATCH!
trac_11929_8899-ncsf-qsym-repr-fix-fs.patch (27.0 KB) - added by saliola 5 years ago.

Download all attachments as: .zip

Change History (71)

comment:1 Changed 8 years ago by nthiery

  • Status changed from new to needs_work

comment:2 Changed 8 years ago by nthiery

  • Type changed from defect to enhancement

comment:3 Changed 6 years ago by nthiery

  • Dependencies set to #12953, #12956
  • Description modified (diff)

comment:4 Changed 5 years ago by saliola

  • Authors changed from Nicolas M. Thiéry, ... to Jason Bandlow, Chris Berg, Franco Saliola, Nicolas M. Thiéry
  • Cc chrisjamesberg added
  • Keywords sd40 added
  • Status changed from needs_work to needs_review

Apply: trac_11929_8899-ncsf-qsym-folded-fs.patch, trac_11929_8899-additional_documentation-fs.patch

(for the patchbot)

Last edited 5 years ago by saliola (previous) (diff)

comment:5 Changed 5 years ago by saliola

  • Dependencies changed from #12953, #12956 to #12953, #12956, #12959, #13238, #13243
  • Description modified (diff)

comment:6 Changed 5 years ago by saliola

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 5 years ago by saliola

  • 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 5 years ago by saliola

(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: Changed 5 years ago by aschilling

  • Cc aschilling added

comment:10 in reply to: ↑ 9 ; follow-ups: Changed 5 years ago by aschilling

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 5 years ago by saliola

  • 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 5 years ago by saliola

comment:12 in reply to: ↑ 10 Changed 5 years ago by saliola

I rebased trac_11929_8899-ncsf-qsym-fs.patch on #12959.

Chris, can you fix the documentation as explained by Anne:

  1. Add an entry in

doc/en/reference/combinat

so that NSym and QSym are included in the documentation!

  1. Also, I spotted an OUTPUT without the : behind it.
  1. 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 5 years ago by saliola

comment:13 follow-up: Changed 5 years ago by saliola

Two new small patches.

  1. trac_11929_8899-fix_skewby-fs.patch: Fixes things so that the following raises an error:
    F([2,1]).skew_by([1])
    
  1. trac_11929_8899-add_degree_to_elementmethods-fs.patch: addes ElementMethods.degree and ElementMethods.is_homogeneous to GradedAlgebrasWithBasis (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:

  1. raise an error if the element is not homogeneous; or
  2. return the maximum of the degrees of the homogeneous summands?

comment:14 in reply to: ↑ 13 Changed 5 years ago by saliola

Replying to saliola:

Two new small patches.

  1. trac_11929_8899-fix_skewby-fs.patch: Fixes things so that the following raises an error:
    F([2,1]).skew_by([1])
    
  1. trac_11929_8899-add_degree_to_elementmethods-fs.patch: addes ElementMethods.degree and ElementMethods.is_homogeneous to GradedAlgebrasWithBasis (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:

  1. raise an error if the element is not homogeneous; or
  2. 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 and homogeneous_degree in GradedAlgebrasWithBasis
  • as a default in GradedAlgebrasWithBasis, set degree = homogeneous_degree
  • for NCSF/QSym, degree is redefined to be maximal_degree

comment:15 Changed 5 years ago by saliola

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 5 years ago by saliola

  • Status changed from needs_work to needs_review
  • Work issues include new files in documentation ; clean up ReST markup deleted

comment:17 Changed 5 years ago by saliola

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 became duality_pairing

comment:18 Changed 5 years ago by saliola

  • Description modified (diff)

Changed 5 years ago by saliola

comment:19 Changed 5 years ago by saliola

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

comment:20 Changed 5 years ago by saliola

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 5 years ago by saliola

  • Description modified (diff)

Changed 5 years ago by zabrocki

minor doc fixes and a quasi-symmetric function tutorial

comment:22 Changed 5 years ago by zabrocki

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

Changed 5 years ago by saliola

rebased to 5.3.beta2

Changed 5 years ago by saliola

extra doctests for coproduct and counit

comment:23 Changed 5 years ago by saliola

  • Description modified (diff)

comment:24 Changed 5 years ago by saliola

For the patchbot

Apply: trac_11929_8899-ncsf-qsym-folded-fs.patch, trac_11929_8899-additional_documentation-fs.patch

comment:25 Changed 5 years ago by saliola

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 5 years ago by saliola

Changed 5 years ago by saliola

Changed 5 years ago by saliola

comment:26 Changed 5 years ago by saliola

  • 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 5 years ago by saliola

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 5 years ago by mhansen

  • 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

Last edited 5 years ago by mhansen (previous) (diff)

comment:29 Changed 5 years ago by zabrocki

  • 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: Changed 5 years ago by mhansen

My guess is #9107 (and related #11791).

comment:31 in reply to: ↑ 30 ; follow-up: Changed 5 years ago by zabrocki

Replying to mhansen:

My guess is #9107 (and related #11791).

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 5 years ago by zabrocki

comment:32 Changed 5 years ago by zabrocki

  • Description modified (diff)
  • Status changed from needs_work to positive_review

added a patch which inserts two colons in ncsf.py to clean up the documentation of two methods. I've tested these patches after #9107 is applied and all tests pass! (I was slightly worried that some tests were not being executed because #9107 was not applied)

comment:33 in reply to: ↑ 31 ; follow-up: Changed 5 years ago by SimonKing

Replying to zabrocki:

Replying to mhansen:

My guess is #9107 (and related #11791).

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.

Does that mean #9107 should be a dependency?

comment:34 in reply to: ↑ 33 ; follow-up: Changed 5 years ago by 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.

Cheers,

Nicolas

Changed 5 years ago by saliola

APPLY ONLY THIS PATCH!

comment:35 Changed 5 years ago by saliola

  • Description modified (diff)

I folded these three patches together and cleaned up the commit message (so that that patchbot doesn't complain):

Apply: trac_11929_8899-ncsf-qsym-final.patch

comment:36 in reply to: ↑ 34 Changed 5 years ago by saliola

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 5 years ago by saliola

  • 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 jdemeyer

  • Milestone changed from sage-5.3 to sage-5.4

Changed 5 years ago by saliola

comment:39 Changed 5 years ago by saliola

  • 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 saliola

  • Status changed from needs_info to needs_review

comment:41 Changed 5 years ago by saliola

  • Status changed from needs_review to needs_work

comment:42 Changed 5 years ago by saliola

  • Status changed from needs_work to needs_review

comment:43 Changed 5 years ago by nthiery

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 zabrocki

  • Status changed from needs_review to positive_review

All tests pass on sage-5.3.rc0 so I will give it a positive review. Since #5457 got de-merged from 5.3 and so you might need the patch coproduct_with_realizations-fs.patch if they are applied in the wrong order. Should there be a dependency on #5457?

comment:45 Changed 5 years ago by aschilling

  • Dependencies changed from #12953, #12956, #12959, #13238, #13243 to #12953, #12956, #12959, #13238, #13243, #5457

comment:46 Changed 5 years ago by jdemeyer

  • 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 jdemeyer

  • 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: Changed 5 years ago by 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_.

comment:49 in reply to: ↑ 48 Changed 5 years ago by aschilling

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 jdemeyer

  • 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: Changed 5 years ago by jdemeyer

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 nthiery

Replying to jdemeyer:

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.

I guess that's ok after all. See the same comment on #5457.

comment:53 Changed 5 years ago by jdemeyer

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 nthiery

  • Keywords days38 added
Note: See TracTickets for help on using tickets.