QSym: internal coproduct, Frobenius, lambda-of-monomials, documentation fixes

[darijgr]

The patch does the following:

• Implement the internal coproduct on QSym, the ring of quasi-symmetric functions. (There is no reasonable internal product on QSym.)

• Implement the Frobenius=Adams endomorphisms on QSym. (There seems to be no Verschiebung.)

• Add a method that computes the lambda-ring operations at the monomial basis elements. This will be very useful later when we implement Hazewinkel's polynomial basis.

• Fix errors in the docstrings in sage/combinat/ncsf_qsym/qsym.py. The fundamental basis was defined incorrectly. The coproduct was claimed to be inherited from the polynomial ring (which was wrong). The finitely-many-variables case was moved from the beginning to the end of the introduction because it is not implemented in Sage. Shuffles were replaced by stuffles in the definition of the product on the monomial basis.

There are some obvious ways to go from here (corresponding changes on NSym, the Hazewinkel basis, possibly optimizing the dual immaculates etc.) but I am done for now.

The #14775 dependency is only because of a reference in the docstrings.

Apply:

• attachment: trac_15094-rebased-QSym-dg.patch​
• attachment: trac_15094-review-ts.patch
• attachment: trac_15094-last-changes-dg.patch

Depends on #14775
Depends on #13505

CC: @sagetrac-sage-combinat @zabrocki @saliola @sagetrac-chrisjamesberg @jbandlow

Component: combinatorics

Keywords: sage-combinat, qsym, quasi-symmetric functions

Author: Darij Grinberg

Reviewer: Mike Zabrocki, Travis Scrimshaw

Merged: sage-5.13.beta0

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

[darijgr]

Author: Darij Grinberg

[darijgr]

comment:1

Attachment: trac_15094-qsym_doc-dg.patch.gz

[darijgr]

Dependencies: #14775

[zabrocki]

comment:2

I have an initial review patch (not done yet) and without removing a few accented characters I was unable to compile the documentation. I cannot figure out why some of the doc strings do not appear in the documentation files (e.g. anything in Bases.ElementMethods). This problem seems to be a pre-existing condition, but I can't read the docstrings easily without fixing it.

I haven't played with the functionality, but just a comment about the math: If Adams / Frobenius is defined on QSym should Verschiebung be defined on NSym? Just a thought.

[darijgr]

comment:3

Thanks for looking into this! I copypasted the accents from the Windows host (no idea how to generate them in Ubuntu), so I'm not surprised they were causing issues; sorry for that. As for [Mal-These], I prefer long identifiers to avoid collision, but if [Mal] is unique (and stays so until the merge) that's fine with me.

Yes, there are Verschiebungen on NSym, to be implemented in a later patch.

[zabrocki]

comment:4

I don't think that identifiers need to be long to be unique. Maybe it is the hyphen, but the [Mal-These] was causing very awkward formatting in the documentation. Probably [MalThese] or [Mal93] are fine.

I will continue to look at the code. Please see if you can figure out why the documentation for ElementMethods including frobenius and internal_coproduct do not appear.

[darijgr]

comment:5

I've no idea; I'm not able to reasonably view the docs on my Ubuntu at all (neither html nor pdf which doesn't even compile) so I'm working more or less blindly as far as the markup goes.

[zabrocki]

comment:6

Hi Darij,
I've finished reviewing this patch. I have an additional handful of minor doc changes (which are harder to track down because they don't appear in the html file).

I added the dependency of #13505 because it modifies qsym.py and this patch will come after and so needs to be rebased. Can you fold the patches and rebase against it (and #14101)? I will upload a new version in a minute.

The reason why the documentation does not appear is that class QuasiSymmetricFunctions -> class Bases -> class ElementMethods is nested too far and there is a bug that prevents the documentation from being compiled. Nicolas and others are working on a patch in #9107 to make the documentation in nested classes appear.

The strangest thing I found in the documentation is that the word itself was replaced by itQuasiSymmetricFunctions. I cannot explain that.

[zabrocki]

Changed dependencies from #14775 to #14775, #13505

[darijgr]

comment:7

Attachment: trac_15094_review-mz.patch.gz

Thanks for the update. Commenting as I'm reading through it:

Sorry for the trac syntax in the docstrings; that was stupid of me.

I've changed

	                This example demonstrates the non-commutativity of the internal 
	                coproduct::

into

                This is confirmed by the following Sage computation (incidentally
                demonstrating the non-cocommutativity of the internal
                coproduct)::

In contexts like

Element methods of the ``Monomial`` basis of ``QuasiSymmetricFunctions.``

the period should be outside of the verbatim mode.

I added a link to Gessel's paper in the reference list.

Replaced "degree of the power series" by "total degree of the power series".

"the product by the realization within the polynomial ring" replaced by "the product on the realization within the ring of power series".

The next paragraph now reads

    There is a coproduct on `\mathrm{QSym}` as well, which in the Monomial 
    basis acts by cutting the composition into a left half and a right
    half. The coproduct is not co-commutative::

[darijgr]

Attachment: trac_15094-not_rebased.patch.gz

qfolded but not yet rebased. backup version in case mpatch fucks up

[darijgr]

comment:8

Rebased. Positive review then?

[darijgr]

comment:9

patchbot:

apply trac_15094-rebased-QSym-dg.patch​

[zabrocki]

comment:11

I am getting 9 doctests failing

Please check, but I think that you need to add the line

from sage.combinat.ncsf_qsym.combinatorics import compositions_order

[darijgr]

Attachment: trac_15094-rebased-QSym-dg.patch.gz

qfolded & rebased

[darijgr]

comment:12

Oops! Thanks for catching this creepy issue (I see where it came from; it shows rebasing is not as simple as merging diffs). The tests (well, those in the ncsf_qsym subfolder) pass now.

[zabrocki]

comment:13

I also checked and adding that line everything passes.

[darijgr]

comment:14

Thank you again!

[zabrocki]

Reviewer: Mike Zabrocki

[tscrim]

Changed reviewer from Mike Zabrocki to Mike Zabrocki, Travis Scrimshaw

[tscrim]

comment:16

Attachment: trac_15094-review-ts.patch.gz

I got some docbuilder warnings and there some doc formatting issues. Here's a review patch which fixes these as well as makes one notational change from \mathbf{k} to R since the former commonly denotes a field but we often consider (almost) arbitrary rings such as \ZZ.

[tscrim]

comment:17

For patchbot:

Apply: trac_15094-rebased-QSym-dg.patch​, trac_15094-review-ts.patch

[darijgr]

Attachment: trac_15094-last-changes-dg.patch.gz

[darijgr]

comment:18

Nice changes; here's just a couple of typos fixed. I'm setting it to positive review, OK?

For patchbot:

Apply: trac_15094-rebased-QSym-dg.patch​, trac_15094-review-ts.patch trac_15094-last-changes-dg.patch

[jdemeyer]

Merged: sage-5.13.beta0