search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.43k stars 478 forks source link

Implement non commutative symmetric functions #8899

Closed nthiery closed 12 years ago

nthiery commented 14 years ago

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

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:

Dependencies:

Apply:

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 commented 12 years ago

Dependencies: #12953, #12956

nthiery commented 12 years ago

Description changed:

--- 
+++ 
@@ -1 +1,3 @@
-Patch under dev. on the sage-combinat patch server
+Patch under heavy dev. on the sage-combinat patch server.
+
+It will include quasi symmetric functions as well (see #11929)
saliola commented 12 years ago

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

saliola commented 12 years ago
comment:4

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

(for the patchbot)

saliola commented 12 years ago

Changed keywords from none to sd40

saliola commented 12 years ago

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

saliola commented 12 years ago

Description changed:

--- 
+++ 
@@ -1,3 +1,28 @@
-Patch under heavy dev. on the sage-combinat patch server.
+This patch includes quasi symmetric functions as well (see #11929).

-It will include 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:
+
+- #12959 : provides the machinery for converting to a_realization for default implementations
+- #13238 : integer matrices (required for the internal product in NCSF)
+- #13243 : new methods for compositions
+
saliola commented 12 years ago
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 commented 12 years ago
comment:7

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

saliola commented 12 years ago
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 commented 12 years ago
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:

i.e. a double dash after the variable to be explained?

Anne

saliola commented 12 years ago

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

saliola commented 12 years ago
comment:11

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

saliola commented 12 years ago

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

saliola commented 12 years ago
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 commented 12 years ago
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])
  1. 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 commented 12 years ago

Attachment: trac_11929_8899-add_degree_to_elementmethods-fs.patch.gz

saliola commented 12 years ago
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])
  1. 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:

saliola commented 12 years ago
comment:15

attachment: trac_11929_8899-include_doc_in_reference_manual-fs.patch deals with documentation:

saliola commented 12 years ago

Changed work issues from include new files in documentation ; clean up ReST markup to none

saliola commented 12 years ago

Attachment: trac_11929_8899-include_doc_in_reference_manual-fs.patch.gz

saliola commented 12 years ago
comment:17

Attachment: trac_11929_8899-modify_duality_method_names-fs.patch.gz

The patch [attachment: trac_11929_8899-modify_duality_method_names-fs.patch] modifies the duality method names to conform to #13372. Namely:

sage: N.dual()
Quasisymmetric functions over the Rational Field
sage: S.dual()
Quasisymmetric functions over the Rational Field on the Monomial basis
sage: R.dual()
Quasisymmetric functions over the Rational Field on the Fundamental basis
saliola commented 12 years ago

Description changed:

--- 
+++ 
@@ -26,3 +26,11 @@
 - #13238 : integer matrices (required for the internal product in NCSF)
 - #13243 : new methods for compositions

+**Apply**:
+* [attachment: trac_11929_8899-antipode_by_coercion_in_category-fs.patch](https://github.com/sagemath/sage-prod/files/10649041/trac_11929_8899-antipode_by_coercion_in_category-fs.patch.gz)
+* [attachment: coproduct_with_realizations-fs.patch](https://github.com/sagemath/sage-prod/files/10649042/coproduct_with_realizations-fs.patch.gz)
+* [attachment: trac_11929_8899-ncsf-qsym-fs.patch](https://github.com/sagemath/sage-prod/files/10649032/trac_11929_8899-ncsf-qsym-fs.patch.gz)
+* [attachment: trac_11929_8899-fix_skewby-fs.patch](https://github.com/sagemath/sage-prod/files/10649034/trac_11929_8899-fix_skewby-fs.patch.gz)
+* [attachment: trac_11929_8899-add_degree_to_elementmethods-fs.patch](https://github.com/sagemath/sage-prod/files/10649035/trac_11929_8899-add_degree_to_elementmethods-fs.patch.gz)
+* [attachment: trac_11929_8899-include_doc_in_reference_manual-fs.patch](https://github.com/sagemath/sage-prod/files/10649036/trac_11929_8899-include_doc_in_reference_manual-fs.patch.gz)
+* [attachment: trac_11929_8899-modify_duality_method_names-fs.patch](https://github.com/sagemath/sage-prod/files/10649037/trac_11929_8899-modify_duality_method_names-fs.patch.gz)
saliola commented 12 years ago

Attachment: trac_11929_8899-is_symmetric-fs.patch.gz

saliola commented 12 years ago
comment:19

[attachment: trac_11929_8899-is_symmetric-fs.patch] : fixes a bug Mike found in is_symmetric and renames to_sym to to_symmetric_function.

saliola commented 12 years ago

Description changed:

--- 
+++ 
@@ -34,3 +34,4 @@
 * [attachment: trac_11929_8899-add_degree_to_elementmethods-fs.patch](https://github.com/sagemath/sage-prod/files/10649035/trac_11929_8899-add_degree_to_elementmethods-fs.patch.gz)
 * [attachment: trac_11929_8899-include_doc_in_reference_manual-fs.patch](https://github.com/sagemath/sage-prod/files/10649036/trac_11929_8899-include_doc_in_reference_manual-fs.patch.gz)
 * [attachment: trac_11929_8899-modify_duality_method_names-fs.patch](https://github.com/sagemath/sage-prod/files/10649037/trac_11929_8899-modify_duality_method_names-fs.patch.gz)
+* [attachment: trac_11929_8899-is_symmetric-fs.patch](https://github.com/sagemath/sage-prod/files/10649038/trac_11929_8899-is_symmetric-fs.patch.gz)
saliola commented 12 years ago

Attachment: trac_11929_8899-internal_product_fix-fs.patch.gz

saliola commented 12 years ago
comment:20

attachment: trac_11929_8899-internal_product_fix-fs.patch fixes an issue with categories since we haven't defined an internal product for QSym.

saliola commented 12 years ago

Description changed:

--- 
+++ 
@@ -35,3 +35,4 @@
 * [attachment: trac_11929_8899-include_doc_in_reference_manual-fs.patch](https://github.com/sagemath/sage-prod/files/10649036/trac_11929_8899-include_doc_in_reference_manual-fs.patch.gz)
 * [attachment: trac_11929_8899-modify_duality_method_names-fs.patch](https://github.com/sagemath/sage-prod/files/10649037/trac_11929_8899-modify_duality_method_names-fs.patch.gz)
 * [attachment: trac_11929_8899-is_symmetric-fs.patch](https://github.com/sagemath/sage-prod/files/10649038/trac_11929_8899-is_symmetric-fs.patch.gz)
+* [attachment: trac_11929_8899-internal_product_fix-fs.patch](https://github.com/sagemath/sage-prod/files/10649039/trac_11929_8899-internal_product_fix-fs.patch.gz)
d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db commented 12 years ago

minor doc fixes and a quasi-symmetric function tutorial

d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db commented 12 years ago

Description changed:

--- 
+++ 
@@ -36,3 +36,4 @@
 * [attachment: trac_11929_8899-modify_duality_method_names-fs.patch](https://github.com/sagemath/sage-prod/files/10649037/trac_11929_8899-modify_duality_method_names-fs.patch.gz)
 * [attachment: trac_11929_8899-is_symmetric-fs.patch](https://github.com/sagemath/sage-prod/files/10649038/trac_11929_8899-is_symmetric-fs.patch.gz)
 * [attachment: trac_11929_8899-internal_product_fix-fs.patch](https://github.com/sagemath/sage-prod/files/10649039/trac_11929_8899-internal_product_fix-fs.patch.gz)
+* [attachment: trac_11929_8899-additional_documentation-mz.patch](https://github.com/sagemath/sage-prod/files/10649040/trac_11929_8899-additional_documentation-mz.patch.gz)
d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db commented 12 years ago
comment:22

Attachment: trac_11929_8899-additional_documentation-mz.patch.gz

Minor changes to documentation plus the addition of a tutorial for quasi-symmetric function and additional doc tests and examples. The doc tests added use functionality that is in sage-5.3.beta2.

saliola commented 12 years ago

Attachment: trac_11929_8899-antipode_by_coercion_in_category-fs.patch.gz

rebased to 5.3.beta2

saliola commented 12 years ago

Attachment: coproduct_with_realizations-fs.patch.gz

extra doctests for coproduct and counit

saliola commented 12 years ago

Description changed:

--- 
+++ 
@@ -27,13 +27,5 @@
 - #13243 : new methods for compositions

 **Apply**:
-* [attachment: trac_11929_8899-antipode_by_coercion_in_category-fs.patch](https://github.com/sagemath/sage-prod/files/10649041/trac_11929_8899-antipode_by_coercion_in_category-fs.patch.gz)
-* [attachment: coproduct_with_realizations-fs.patch](https://github.com/sagemath/sage-prod/files/10649042/coproduct_with_realizations-fs.patch.gz)
-* [attachment: trac_11929_8899-ncsf-qsym-fs.patch](https://github.com/sagemath/sage-prod/files/10649032/trac_11929_8899-ncsf-qsym-fs.patch.gz)
-* [attachment: trac_11929_8899-fix_skewby-fs.patch](https://github.com/sagemath/sage-prod/files/10649034/trac_11929_8899-fix_skewby-fs.patch.gz)
-* [attachment: trac_11929_8899-add_degree_to_elementmethods-fs.patch](https://github.com/sagemath/sage-prod/files/10649035/trac_11929_8899-add_degree_to_elementmethods-fs.patch.gz)
-* [attachment: trac_11929_8899-include_doc_in_reference_manual-fs.patch](https://github.com/sagemath/sage-prod/files/10649036/trac_11929_8899-include_doc_in_reference_manual-fs.patch.gz)
-* [attachment: trac_11929_8899-modify_duality_method_names-fs.patch](https://github.com/sagemath/sage-prod/files/10649037/trac_11929_8899-modify_duality_method_names-fs.patch.gz)
-* [attachment: trac_11929_8899-is_symmetric-fs.patch](https://github.com/sagemath/sage-prod/files/10649038/trac_11929_8899-is_symmetric-fs.patch.gz)
-* [attachment: trac_11929_8899-internal_product_fix-fs.patch](https://github.com/sagemath/sage-prod/files/10649039/trac_11929_8899-internal_product_fix-fs.patch.gz)
-* [attachment: trac_11929_8899-additional_documentation-mz.patch](https://github.com/sagemath/sage-prod/files/10649040/trac_11929_8899-additional_documentation-mz.patch.gz)
+* [attachment: trac_11929_8899-ncsf-qsym-folded-fs.patch](https://github.com/sagemath/sage-prod/files/10649045/trac_11929_8899-ncsf-qsym-folded-fs.patch.gz)
+* [attachment: trac_11929_8899-additional_documentation-fs.patch](https://github.com/sagemath/sage-prod/files/10649043/trac_11929_8899-additional_documentation-fs.patch.gz)
saliola commented 12 years ago
comment:24

For the patchbot

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

saliola commented 12 years ago

Attachment: trac_11929_8899-additional_documentation-fs.patch.gz

saliola commented 12 years ago
comment:25

Hello Mike,

Thank you very much for your review, and your improvements to the documentation!

I folded all the patches that you've seen, including your patch. And I created one more that makes changes to the documentation, adds some doctests, etc.

So please review this last patch: attachment: trac_11929_8899-additional_documentation-fs.patch.

Here is a summary of the changes:

saliola commented 12 years ago

Attachment: additional-addional-documentation-mz.patch.gz

saliola commented 12 years ago

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

Attachment: trac_11929_8899-from_polynomial-fs.patch.gz

saliola commented 12 years ago

Description changed:

--- 
+++ 
@@ -28,4 +28,4 @@

 **Apply**:
 * [attachment: trac_11929_8899-ncsf-qsym-folded-fs.patch](https://github.com/sagemath/sage-prod/files/10649045/trac_11929_8899-ncsf-qsym-folded-fs.patch.gz)
-* [attachment: trac_11929_8899-additional_documentation-fs.patch](https://github.com/sagemath/sage-prod/files/10649043/trac_11929_8899-additional_documentation-fs.patch.gz)
+* [attachment: trac_11929_8899-from_polynomial-fs.patch](https://github.com/sagemath/sage-prod/files/10649046/trac_11929_8899-from_polynomial-fs.patch.gz)
saliola commented 12 years ago
comment:26

I folded the additional documentation patches (mine and Mike's) into the main patch since Mike gave mine a positive review and I positively reviewed Mike's changes.

And I posted one more patch that adds a new method from_polynomial to QSym.

Only the patch attachment: trac_11929_8899-from_polynomial-fs.patch needs review.

saliola commented 12 years ago
comment:27

Patchbot, please apply the following patches and tell me all tests pass!

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

mwhansen commented 12 years ago

Reviewer: Mike Zabrocki, Franco Saliola, Mike Hansen

mwhansen commented 12 years ago
comment:28

trac_11929_8899-from_polynomial-fs.patch looks good to me

d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db commented 12 years ago
comment:29

I have an issue with missing documentation. For example, the method is_symmetric is not appearing in the documentation for qsym.py. Can someone explain why?

mwhansen commented 12 years ago
comment:30

My guess is #9107 (and related #11791).

d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db commented 12 years ago
comment:31

Replying to @mwhansen:

My guess is #9107 (and related #11791).

Thanks Mike! I just tested and confirm that when I apply the patch that is attached to #9107 and then recompile, the missing documentation for methods appears. I will post a few more corrections to the documentation shortly (e.g. coproduct_on_generators() in ncsf.py is weird and that probably was one of the missing methods before).

d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db commented 12 years ago

Attachment: trac_11929_8899_minor_docfix-mz.patch.gz

d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db commented 12 years ago

Description changed:

--- 
+++ 
@@ -29,3 +29,4 @@
 **Apply**:
 * [attachment: trac_11929_8899-ncsf-qsym-folded-fs.patch](https://github.com/sagemath/sage-prod/files/10649045/trac_11929_8899-ncsf-qsym-folded-fs.patch.gz)
 * [attachment: trac_11929_8899-from_polynomial-fs.patch](https://github.com/sagemath/sage-prod/files/10649046/trac_11929_8899-from_polynomial-fs.patch.gz)
+* [attachment: trac_11929_8899_minor_docfix-mz.patch](https://github.com/sagemath/sage-prod/files/10649047/trac_11929_8899_minor_docfix-mz.patch.gz)