NSym (NCSF): Verschiebung, doc improvements, meet and join of compositions

[darijgr]

This patch does the following:

• Implement the Verschiebung map on NSym (the map adjoint to the Frobenius on QSym implemented in QSym: internal coproduct, Frobenius, lambda-of-monomials, documentation fixes #15094). The current implementation handles all bases by coercion to the homogeneous one. I planned to implement the Psi, Phi, R and L bases separately, but I am unable to (see below).

• Add a to_descent_algebra map to the newly implemented (Descent algebra #14981) descent algebra. The difference between the signature of my map, to_descent_algebra(self, n), and that of the old map to the symmetric group algebra, to_symmetric_group_algebra(self), is intentional: My map takes a noncommutative symmetric function self and an integer n and projects the n-th homogeneous component of self on the n-th descent algebra; the map to_symmetric_group_algebra takes just a noncommutative symmetric function self and projects it on the deg(self)-th symmetric group algebra if self is homogeneous, otherwise throws an exception. If self is 0, then it outputs the int 0 (because 0 doesn't have a degree). In my opinion, my signature is the better one, not least because it handles 0 correctly.

• Clean up some of the doc and add definitions for the most important bases. The inaptly named "MultiplicativeBasesOnGroupLikeElements" class now has a more explanatory docstring. The incorrect claim about m_to_s_stat always outputting an integer has been removed. Dependency on the base ring being a QQ-algebra has been made clearer.

• The meet and the join of two compositions wrt the refinement order have been implemented.

Here are things I wanted to change/add but got too confused:

• I don't understand why the internal product is implemented in generic_basis_code.py rather than ncsf.py. Isn't generic_basis_code.py for methods shared between QSym and NSym? There is no internal product on QSym.

• This here is a doctest which has been around before me:

                sage: N = NonCommutativeSymmetricFunctions(QQ)
                sage: S = N.complete()
                sage: S.internal_product
                Generic endomorphism of Non-Commutative Symmetric Functions over the Rational Field in the Complete basis

The output makes no sense: The internal product is not an endomorphism of anything.

• I am trying to overshadow the verschiebung function I implemented on a generic NSym basis by a specific implementation on the ribbon basis. So I've added it under class ElementMethods: in the class Ribbon. But it doesn't get precedence over the generic implementation at runtime! What am I doing wrong?

• [Fixed by Travis, Implement to_symmetric_group_algebra for all bases of DescentAlgebra #15170.] This is probably for Travis: is it intentional that the to_symmetric_group_algebra method in descent_algebra.py is defined only on the D-basis, rather than on every basis or globally on the whole descent algebra?

Apply:

• attachment: trac_15164-NSym-verschiebung-dg.patch​
• attachment: trac_15164-review-ts.patch​

Depends on #14775
Depends on #14981
Depends on #15094
Depends on #15122

CC: @tscrim @sagetrac-sage-combinat @zabrocki @nthiery

Component: combinatorics

Keywords: sage-combinat, NSym, NCSF, symmetric functions

Author: Darij Grinberg

Reviewer: Travis Scrimshaw

Merged: sage-5.13.beta1

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

[darijgr]

Attachment: trac_15164-NSym-verschiebung-dg.patch.gz

[darijgr]

Description changed:

--- 
+++ 
@@ -6,7 +6,7 @@
 
 * Clean up some of the doc and add definitions for the most important bases. The inaptly named "MultiplicativeBasesOnGroupLikeElements" class now has a more explanatory docstring. The incorrect claim about m_to_s_stat always outputting an integer has been removed. Dependency on the base ring being a QQ-algebra has been made clearer.
 
-* The meet and the join of two compositions wrt the refinement order have been implemented (as a sort of continuation of #15122, which is a dependency).
+* The meet and the join of two compositions wrt the refinement order have been implemented.
 
 Here are things I wanted to change/add but got too confused:
 

[darijgr]

Description changed:

--- 
+++ 
@@ -20,7 +20,7 @@
                 sage: S.internal_product
                 Generic endomorphism of Non-Commutative Symmetric Functions over the Rational Field in the Complete basis
 ```
-The output makes no sense: The internal product is not an endomorphism of everything.
+The output makes no sense: The internal product is not an endomorphism of anything.
 
 * I am trying to overshadow the `verschiebung` function I implemented on a generic NSym basis by a specific implementation on the ribbon basis. So I've added it under `class ElementMethods:` in the `class Ribbon`. But it doesn't get precedence over the generic implementation at runtime! What am I doing wrong?
 

[tscrim]

comment:4

Hey Darij,

I only defined to_symmetric_group_algebra() on the D basis since that is where the natural coercion occurred. It looks like I forgot to implement a method to extend it to the other bases via coercion.

[darijgr]

comment:5

Hi Travis,

OK. Who of us should fix it? And in this ticket or in a new one?

[tscrim]

comment:6

I'll take care of it in #15170.

[darijgr]

Description changed:

--- 
+++ 
@@ -24,4 +24,4 @@
 
 * I am trying to overshadow the `verschiebung` function I implemented on a generic NSym basis by a specific implementation on the ribbon basis. So I've added it under `class ElementMethods:` in the `class Ribbon`. But it doesn't get precedence over the generic implementation at runtime! What am I doing wrong?
 
-* This is probably for Travis: is it intentional that the `to_symmetric_group_algebra` method in `descent_algebra.py` is defined only on the D-basis, rather than on every basis or globally on the whole descent algebra?
+* [Fixed by Travis, #15170.] This is probably for Travis: is it intentional that the `to_symmetric_group_algebra` method in `descent_algebra.py` is defined only on the D-basis, rather than on every basis or globally on the whole descent algebra?

[tscrim]

comment:8

I will review this in the next few days. Promise.

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:9

Hey Darij,

Here's my review patch which adds sup() / inf() aliases for join() / meet() (resp.), moves the description block for internal_product, and makes some minor docstring tweaks elsewhere. If you're happy with my changes, go ahead and set this to positive review.

Best,

Travis