Implement non commutative symmetric functions

[nthiery]

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:

• Improvements to Sets.WithRealizations #12959 : provides the machinery for converting to a_realization for default implementations
• add functionality for counting, generating, and manipulating non-negative integer matrices #13238 : integer matrices (required for the internal product in NCSF)
• new methods for compositions #13243 : new methods for compositions

Apply:

• attachment: trac_11929_8899-ncsf-qsym-final.patch
• attachment: trac_11929_8899-ncsf-qsym-repr-fix-fs.patch

Depends on #12953
Depends on #12956
Depends on #12959
Depends on #13238
Depends on #13243
Depends on #5457

CC: @sagetrac-sage-combinat @sagetrac-chrisjamesberg @zabrocki @anneschilling

Component: combinatorics

Keywords: sd40, days38

Author: Jason Bandlow, Chris Berg, Franco Saliola, Nicolas M. Thiéry

Reviewer: Mike Zabrocki, Franco Saliola, Mike Hansen

Merged: sage-5.4.beta1

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

[nthiery]

Dependencies: #12953, #12956

[saliola]

Changed author from Nicolas M. Thiéry, ... to Jason Bandlow, Chris Berg, Franco Saliola, Nicolas M. Thiéry

[saliola]

comment:4

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

(for the patchbot)

[saliola]

Changed keywords from none to sd40

[saliola]

Changed dependencies from #12953, #12956 to #12953, #12956, #12959, #13238, #13243

[saliola]

comment:6

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.

[saliola]

comment:7

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

[saliola]

comment:8

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

[anneschilling]

comment:10

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

[saliola]

Work Issues: include new files in documentation ; clean up ReST markup

[saliola]

comment:11

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

[saliola]

Attachment: trac_11929_8899-ncsf-qsym-fs.patch.gz

[saliola]

comment:12

I rebased attachment: 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]

[saliola]

comment:13

Attachment: trac_11929_8899-fix_skewby-fs.patch.gz

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:
a. raise an error if the element is not homogeneous; or
b. return the maximum of the degrees of the homogeneous summands?

[saliola]

Attachment: trac_11929_8899-add_degree_to_elementmethods-fs.patch.gz

[saliola]

comment:14

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:
a. raise an error if the element is not homogeneous; or
b. return the maximum of the degrees of the homogeneous summands?

Based on the discussion on sage-combinat-devel, I updated attachment: 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

[nthiery]

comment:43

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

[zabrocki]

comment:44

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?

[anneschilling]

Changed dependencies from #12953, #12956, #12959, #13238, #13243 to #12953, #12956, #12959, #13238, #13243, #5457

[jdemeyer]

Merged: sage-5.4.beta1

[jdemeyer]

comment:47

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

[jdemeyer]

Changed merged from sage-5.4.beta1 to none

[saliola]

comment:48

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

[anneschilling]

comment:49

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

[jdemeyer]

comment:50

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.

[jdemeyer]

Merged: sage-5.4.beta1

[jdemeyer]

comment:51

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.

[nthiery]

comment:52

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.

[jdemeyer]

comment:53

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

[nthiery]

Changed keywords from sd40 to sd40, days38