Implement non commutative symmetric functions

[Nicolas M. Thiéry]

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:

• trac_11929_8899-ncsf-qsym-final.patch​
• trac_11929_8899-ncsf-qsym-repr-fix-fs.patch​

[Franco Saliola]

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

(for the patchbot)

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

[Franco Saliola]

I put the author names in alphabetical order. I don't know the policy on this. I hope this is okay.

[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.)

[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

[Franco Saliola]

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

[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!

2. Also, I spotted an OUTPUT without the : behind it.

3. 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]

[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])
   

2. 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?

[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])
   

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

[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

[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

[Franco Saliola]

trac_11929_8899-is_symmetric-fs.patch​ : fixes a bug Mike found in is_symmetric and renames to_sym to to_symmetric_function.

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

[Mike Zabrocki]

minor doc fixes and a quasi-symmetric function tutorial

[Mike Zabrocki]

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.

[Franco Saliola]

rebased to 5.3.beta2

[Franco Saliola]

extra doctests for coproduct and counit

[Franco Saliola]

For the patchbot

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

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

[Franco Saliola]

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.

[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

[Mike Hansen]

trac_11929_8899-from_polynomial-fs.patch looks good to me

[Mike Zabrocki]

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?

[Mike Hansen]

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

[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).

[Mike Zabrocki]

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)

[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?

[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

[Franco Saliola]

APPLY ONLY THIS PATCH!

[Franco Saliola]

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

• trac_11929_8899-ncsf-qsym-folded-fs.patch​
• trac_11929_8899-from_polynomial-fs.patch​
• trac_11929_8899_minor_docfix-mz.patch​

Apply: trac_11929_8899-ncsf-qsym-final.patch​

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

[Franco Saliola]

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?

[Franco Saliola]

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

[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

[Mike Zabrocki]

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?

[Jeroen Demeyer]

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
**********************************************************************

[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_.

[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

[Jeroen Demeyer]

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.

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

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

[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(...)