Implement quasi-symmetric functions

[BruceWestbury]

This feature is being implemented as part of #8899. There is a patch up on that ticket ready for review right now.

Implement quasisymmetric functions as a graded Hopf algebra with basis. The preferred basis is the basis of fundamental quasisymmetric functions. This should also implement the inclusion of the Hopf algebra of symmetric functions (as a homomorphism) and the principle
specialisation (as a homomorphism).

Depends on #8899

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

Component: combinatorics

Keywords: Hopf algebras, sd40

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

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

[jbandlow]

Attachment: trac_11929_quasisymmetric_functions-jb.patch.gz

[jbandlow]

comment:1

I've attached the patch that I've been using from the sage-combinat queue, modified to apply cleanly to sage-4.7.1. There are obviously documentation issues, which I will begin working on. Comments welcome!

[jbandlow]

comment:2

Recording todo's for myself here:

1. Doc and tests throughout
2. The partial morphism from qsym --> sym is implemented with .to_symmetric_function(). The reverse morphism should be implemented in SF.
3. Look at how principle specializations are implemented in SF, and be implement here in a consistent way.
4. Homomorphisms to/from polynomial rings should also be implemented.
5. The combinatorial rule for multiplying fundamentals is not implemented, and should be.

[jbandlow]

comment:3

Replying to @jbandlow:
6. Learn how to use WikiFormatting for lists...

[BruceWestbury]

comment:4

Replying to @jbandlow:

I've attached the patch that I've been using from the sage-combinat queue, modified to apply cleanly to sage-4.7.1. There are obviously documentation issues, which I will begin working on. Comments welcome!

That looks great! I have read the code but not tried to run it. I will need to see if I can follow the instructions in the on-line documentation. I have some comments:

• You have declared quasisymmetric functions as Hopf algebra but I can only see algebra operations. (This is sufficient for my purposes.)
• You have implemented the inclusion of symmetric functions by writing the monomial functions in terms of the monomial functions. It is also straightforward to implement this by writing the elementary and homogeneous functions in terms of the fundamental functions. I don't know what, if anything, is gained by implementing this.
• Do you mean to allow the base ring to be a non-commutative ring?

I asked for the principal specialisation but did not give the whole story. Let f be of degree r and ps(f) the principle specialisation. Then what I am actually interested in is (1-q)...(1-q^r)ps(f) which is a polynomial in q. This is straightforward to implement using the major_index method of Composition. I have got in the habit of calling this the fake degree polynomial.

Mathematically, this is a graded algebra homomorphism to the quantum divided power algebra. This is a graded Z[q]-algebra. As a graded Z[q]-module it is Z[q,x] where x has degree one. The multiplication is x^r.x^s = [r+s,r]_q x^r+s (where [r+s,r]_q is the quantum binomial coefficient).

I can't see a coproduct on the quantum divided power algebra which makes it a bialgebra.

I have not been able to find divided power algebras (quantum or otherwise) in sage.
Did I miss something? and, if not, should these be implemented?

[jbandlow]

comment:5

Replying to @BruceWestbury:

That looks great! I have read the code but not tried to run it. I will need to see if I can follow the instructions in the on-line documentation. I have some comments:

It turns out you won't be able to run it, as it depends on some category code which is also only available on the combinat queue for the time being. I'll check with Nicolas about how to proceed on this.

• You have declared quasisymmetric functions as Hopf algebra but I can only see algebra operations. (This is sufficient for my purposes.)

Good catch! It might not be a bad idea for me to implement the basic Hopf operations here as well; it shouldn't be too difficult, I think.

• You have implemented the inclusion of symmetric functions by writing the monomial functions in terms of the monomial functions. It is also straightforward to implement this by writing the elementary and homogeneous functions in terms of the fundamental functions. I don't know what, if anything, is gained by implementing this.

Implementing the various homomorphisms could definitely improve performance in some cases, but I'm less inclined to go down that road at the moment.

• Do you mean to allow the base ring to be a non-commutative ring?

Another good catch. I definitely haven't thought through the issues of that. Perhaps I should restrict to commutative rings.

I asked for the principal specialisation but did not give the whole story. Let f be of degree r and ps(f) the principle specialisation. Then what I am actually interested in is (1-q)...(1-q^r)ps(f) which is a polynomial in q. This is straightforward to implement using the major_index method of Composition. I have got in the habit of calling this the fake degree polynomial.

Mathematically, this is a graded algebra homomorphism to the quantum divided power algebra. This is a graded Z[q]-algebra. As a graded Z[q]-module it is Z[q,x] where x has degree one. The multiplication is x^r.x^s = [r+s,r]_q x^r+s (where [r+s,r]_q is the quantum binomial coefficient).

I can't see a coproduct on the quantum divided power algebra which makes it a bialgebra.

I have not been able to find divided power algebras (quantum or otherwise) in sage.
Did I miss something? and, if not, should these be implemented?

I'm not aware of the divided power algebras in sage. You may be able to get information or ideas on implementation from the sage-algebra list. From this description, it doesn't look like a quick and limited implementation would be so hard. (Also, did you mean to have an x somewhere in your definition of the homomorphism Qsym-->QuantumDividedPowerAlgebra ? If not, I'm confused as to how the homomorphism is graded.)

[BruceWestbury]

comment:6

Replying to @jbandlow:

I'm not aware of the divided power algebras in sage. You may be able to get information or ideas on implementation from the sage-algebra list. From this description, it doesn't look like a quick and limited implementation would be so hard. (Also, did you mean to have an x somewhere in your definition of the homomorphism Qsym-->QuantumDividedPowerAlgebra ? If not, I'm confused as to how the homomorphism is graded.)

I have put a brief description of the QuantumDividedPowerAlgebra on the Wiki page. I have also made an attempt at implementing DividedPowerAlgebra. This did not succeed. I have added this as an attachment to the wiki page. I am sure this is not correct protocol but I did not have any better ideas.

[jdemeyer]

Milestone sage-4.7.3 deleted

[sagetrac-vferay]

comment:8

Hi Jason,

it seems that you have not been working recently on this patch. I will add a few feature (antipode, coproduct) in a separate patch.

Valentin

[saliola]

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

[saliola]

Dependencies: #8899

[saliola]

Changed keywords from Hopf algebras to Hopf algebras, sd40

[saliola]

comment:11

(for the patchbot)

Apply:

[sagetrac-chrisjamesberg]

comment:12

We would like to close this ticket. It has already been implemented in #8899.

[jdemeyer]

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

[jdemeyer]

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