Opened 13 years ago

Closed 10 years ago

Last modified 10 years ago

#8899 closed enhancement (fixed)

Implement non commutative symmetric functions

Reported by: Nicolas M. Thiéry Owned by: Sage Combinat CC user
Priority: major Milestone: sage-5.4
Component: combinatorics Keywords: sd40, days38
Cc: Sage Combinat CC user, Chris Berg, Mike Zabrocki, Anne Schilling 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:

Status badges

Description (last modified by Franco 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 Franco Saliola 10 years ago.
trac_11929_8899-fix_skewby-fs.patch (2.1 KB) - added by Franco Saliola 10 years ago.
trac_11929_8899-add_degree_to_elementmethods-fs.patch (7.1 KB) - added by Franco Saliola 10 years ago.
trac_11929_8899-include_doc_in_reference_manual-fs.patch (47.4 KB) - added by Franco Saliola 10 years ago.
trac_11929_8899-modify_duality_method_names-fs.patch (15.4 KB) - added by Franco Saliola 10 years ago.
trac_11929_8899-is_symmetric-fs.patch (4.8 KB) - added by Franco Saliola 10 years ago.
trac_11929_8899-internal_product_fix-fs.patch (2.6 KB) - added by Franco Saliola 10 years ago.
trac_11929_8899-additional_documentation-mz.patch (23.7 KB) - added by Mike Zabrocki 10 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 Franco Saliola 10 years ago.
rebased to 5.3.beta2
coproduct_with_realizations-fs.patch (2.7 KB) - added by Franco Saliola 10 years ago.
extra doctests for coproduct and counit
trac_11929_8899-additional_documentation-fs.patch (32.0 KB) - added by Franco Saliola 10 years ago.
additional-addional-documentation-mz.patch (5.4 KB) - added by Franco Saliola 10 years ago.
trac_11929_8899-ncsf-qsym-folded-fs.patch (156.3 KB) - added by Franco Saliola 10 years ago.
trac_11929_8899-from_polynomial-fs.patch (6.2 KB) - added by Franco Saliola 10 years ago.
trac_11929_8899_minor_docfix-mz.patch (1.0 KB) - added by Mike Zabrocki 10 years ago.
trac_11929_8899-ncsf-qsym-final.patch (161.3 KB) - added by Franco Saliola 10 years ago.
APPLY ONLY THIS PATCH!
trac_11929_8899-ncsf-qsym-repr-fix-fs.patch (27.0 KB) - added by Franco Saliola 10 years ago.

Download all attachments as: .zip

Change History (71)

comment:1 Changed 13 years ago by Nicolas M. Thiéry

Status: newneeds_work

comment:2 Changed 13 years ago by Nicolas M. Thiéry

Type: defectenhancement

comment:3 Changed 11 years ago by Nicolas M. Thiéry

Dependencies: #12953, #12956
Description: modified (diff)

comment:4 Changed 10 years ago by Franco Saliola

Authors: Nicolas M. Thiéry, ...Jason Bandlow, Chris Berg, Franco Saliola, Nicolas M. Thiéry
Cc: Chris Berg added
Keywords: sd40 added
Status: needs_workneeds_review

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

(for the patchbot)

Last edited 10 years ago by Franco Saliola (previous) (diff)

comment:5 Changed 10 years ago by Franco Saliola

Dependencies: #12953, #12956#12953, #12956, #12959, #13238, #13243
Description: modified (diff)

comment:6 Changed 10 years ago by Franco 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 10 years ago by Franco Saliola

Cc: Mike 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 10 years ago by Franco 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 Changed 10 years ago by Anne Schilling

Cc: Anne Schilling added

comment:10 in reply to:  9 ; Changed 10 years ago by Anne Schilling

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 10 years ago by Franco Saliola

Status: needs_reviewneeds_work
Work issues: include new files in documentation ; clean up ReST markup

Thanks for catching these, Anne. We'll have to correct them.

Changed 10 years ago by Franco Saliola

comment:12 in reply to:  10 Changed 10 years ago by Franco 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 10 years ago by Franco Saliola

comment:13 Changed 10 years ago by Franco 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?

Changed 10 years ago by Franco Saliola

comment:14 in reply to:  13 Changed 10 years ago by Franco 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 10 years ago by Franco 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 10 years ago by Franco Saliola

Status: needs_workneeds_review
Work issues: include new files in documentation ; clean up ReST markup

Changed 10 years ago by Franco Saliola

comment:17 Changed 10 years ago by Franco 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 10 years ago by Franco Saliola

Description: modified (diff)

Changed 10 years ago by Franco Saliola

comment:19 Changed 10 years ago by Franco 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.

Changed 10 years ago by Franco Saliola

comment:20 Changed 10 years ago by Franco 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 10 years ago by Franco Saliola

Description: modified (diff)

Changed 10 years ago by Mike Zabrocki

minor doc fixes and a quasi-symmetric function tutorial

comment:22 Changed 10 years ago by Mike 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 10 years ago by Franco Saliola

rebased to 5.3.beta2

Changed 10 years ago by Franco Saliola

extra doctests for coproduct and counit

comment:23 Changed 10 years ago by Franco Saliola

Description: modified (diff)

comment:24 Changed 10 years ago by Franco Saliola

For the patchbot

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

Changed 10 years ago by Franco Saliola

comment:25 Changed 10 years ago by Franco 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 10 years ago by Franco Saliola

Changed 10 years ago by Franco Saliola

Changed 10 years ago by Franco Saliola

comment:26 Changed 10 years ago by Franco 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 10 years ago by Franco 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 10 years ago by Mike Hansen

Reviewers: Mike Zabrocki, Franco Saliola, Mike Hansen
Status: needs_reviewpositive_review

trac_11929_8899-from_polynomial-fs.patch looks good to me

Last edited 10 years ago by Mike Hansen (previous) (diff)

comment:29 Changed 10 years ago by Mike Zabrocki

Status: positive_reviewneeds_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 Changed 10 years ago by Mike Hansen

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

comment:31 in reply to:  30 ; Changed 10 years ago by Mike 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 10 years ago by Mike Zabrocki

comment:32 Changed 10 years ago by Mike Zabrocki

Description: modified (diff)
Status: needs_workpositive_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 ; Changed 10 years ago by Simon King

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 ; Changed 10 years ago by Nicolas M. Thiéry

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 10 years ago by Franco Saliola

APPLY ONLY THIS PATCH!

comment:35 Changed 10 years ago by Franco 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 10 years ago by Franco 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 10 years ago by Franco Saliola

Milestone: sage-wishlistsage-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 10 years ago by Jeroen Demeyer

Milestone: sage-5.3sage-5.4

Changed 10 years ago by Franco Saliola

comment:39 Changed 10 years ago by Franco Saliola

Description: modified (diff)
Status: positive_reviewneeds_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 10 years ago by Franco Saliola

Status: needs_infoneeds_review

comment:41 Changed 10 years ago by Franco Saliola

Status: needs_reviewneeds_work

comment:42 Changed 10 years ago by Franco Saliola

Status: needs_workneeds_review

comment:43 Changed 10 years ago by Nicolas M. Thiéry

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 10 years ago by Mike Zabrocki

Status: needs_reviewpositive_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 10 years ago by Anne Schilling

Dependencies: #12953, #12956, #12959, #13238, #13243#12953, #12956, #12959, #13238, #13243, #5457

comment:46 Changed 10 years ago by Jeroen Demeyer

Merged in: sage-5.4.beta1
Resolution: fixed
Status: positive_reviewclosed

comment:47 Changed 10 years ago by Jeroen Demeyer

Merged in: sage-5.4.beta1
Resolution: fixed
Status: closednew

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 Changed 10 years ago by Franco 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 10 years ago by Anne Schilling

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 10 years ago by Jeroen Demeyer

Merged in: sage-5.4.beta1
Resolution: fixed
Status: newclosed

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 Changed 10 years ago by Jeroen Demeyer

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 10 years ago by Nicolas M. Thiéry

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 10 years ago by Jeroen Demeyer

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 10 years ago by Nicolas M. Thiéry

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