Opened 5 years ago

Closed 4 years ago

#11929 closed enhancement (duplicate)

Implement quasi-symmetric functions

Reported by: bruce Owned by: bruce
Priority: minor Milestone: sage-duplicate/invalid/wontfix
Component: combinatorics Keywords: Hopf algebras, sd40
Cc: sage-combinat, chrisjamesberg, zabrocki Merged in:
Authors: Reviewers: Jason Bandlow, Chris Berg, Franco Saliola, Nicolas M. Thiéry
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #8899 Stopgaps:

Description (last modified by saliola)

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

Attachments (1)

trac_11929_quasisymmetric_functions-jb.patch (18.1 KB) - added by jbandlow 5 years ago.

Download all attachments as: .zip

Change History (15)

Changed 5 years ago by jbandlow

comment:1 follow-up: Changed 5 years ago by 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!

comment:2 follow-up: Changed 5 years ago by jbandlow

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.

comment:3 in reply to: ↑ 2 Changed 5 years ago by jbandlow

Replying to jbandlow:

  1. Learn how to use WikiFormatting for lists...

comment:4 in reply to: ↑ 1 ; follow-up: Changed 5 years ago by bruce

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-qr)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 xr.xs = [r+s,r]_q xr+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?

comment:5 in reply to: ↑ 4 ; follow-up: Changed 5 years ago by jbandlow

Replying to bruce:

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-qr)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 xr.xs = [r+s,r]_q xr+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.)

comment:6 in reply to: ↑ 5 Changed 5 years ago by bruce

  • Owner changed from jbandlow to bruce

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.

comment:7 Changed 5 years ago by jdemeyer

  • Milestone sage-4.7.3 deleted

Milestone sage-4.7.3 deleted

comment:8 Changed 5 years ago by vferay

  • Milestone set to sage-5.0

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

comment:9 Changed 5 years ago by nthiery

  • Description modified (diff)

comment:10 Changed 5 years ago by saliola

  • Authors changed from bruce to Jason Bandlow, Chris Berg, Franco Saliola, Nicolas M. Thiéry
  • Cc sage-combinat chrisjamesberg zabrocki added
  • Dependencies set to #8899
  • Description modified (diff)
  • Keywords sd40 added
  • Status changed from new to needs_review

comment:11 Changed 5 years ago by saliola

(for the patchbot)

Apply:

comment:12 Changed 4 years ago by chrisjamesberg

  • Status changed from needs_review to positive_review

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

comment:13 Changed 4 years ago by jdemeyer

  • Authors Jason Bandlow, Chris Berg, Franco Saliola, Nicolas M. Thiéry deleted
  • Milestone changed from sage-5.7 to sage-duplicate/invalid/wontfix
  • Reviewers changed from bruce to Jason Bandlow, Chris Berg, Franco Saliola, Nicolas M. Thiéry

comment:14 Changed 4 years ago by jdemeyer

  • Resolution set to duplicate
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.