Opened 7 years ago

Closed 7 years ago

#8810 closed enhancement (fixed)

Implementation of Stanley symmetric functions

Reported by: aschilling Owned by: sage-combinat
Priority: major Milestone: sage-4.5.2
Component: combinatorics Keywords:
Cc: sage-combinat Merged in: sage-4.5.2.alpha0
Authors: Steve Pon, Anne Schilling, Nicolas M. Thiéry Reviewers: Nicolas M. Thiéry, Thomas Lam
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by stevenpon)

#8810: Implementation of Stanley symmetric functions for types A,B and A/B/C/D affine

Depends on #8811.

Based on the combinatorics of Pieri factors (sage/combinat/root_systems/pieri_factors.py)

Currently, there are two implementations of the maximal Pieri factors: a combinatorial implementation and a type-free implementation using translations in the affine Weyl group. Type D affine Stanley symmetric functions are still conjectural, but type D affine Pieri factors have been established rigorously.

Attachments (4)

trac_8810_stanley_symmetric_functions-sp-as.patch (58.1 KB) - added by stevenpon 7 years ago.
trac_8810_stanley_symmetric_functions-sp-as.2.patch (59.0 KB) - added by aschilling 7 years ago.
trac_8810_stanley_symmetric_functions-untabified.patch (59.2 KB) - added by davidloeffler 7 years ago.
Version without tabs - apply only this patch
trac_8810_stanley_symmetric_functions-docfix.patch (780 bytes) - added by mpatel 7 years ago.
Small doc fix. Apply on top of "untabified" patch.

Download all attachments as: .zip

Change History (26)

comment:1 Changed 7 years ago by stevenpon

  • Description modified (diff)
  • Status changed from new to needs_review

Depends on #8811, which needs review.

comment:2 Changed 7 years ago by jason

There's no patch up at #8811, though.

comment:3 Changed 7 years ago by jbandlow

  • Status changed from needs_review to needs_work

I'm just starting this review, and I will probably have more to say, but here some initial issues. In the file weyl_groups.py:

  • The methods exp_poly_to_sym, pieri_factors, and is_pieri_factor are missing doctests.
  • Do you think exp_poly_to_sym has general use? If so, it should probably be placed in the symmetric function code somewhere. If not, it should probably be made private (eg. _exp_poly_to_sym)
  • In exp_poly_to_sym, you should replace

R._from_dict(dict( ... ) with R.sum_of_terms( ... )

  • In the doc for pieri_factors: "Those are used.." should be "These are used..", "For any types" should be "For any type"
  • In each of the methods pieri_factors, is_pieri_factor, and left_pieri_factorizations a reference in the doc to the 'pieri_factors.py` file (where pieri factors are described in more detail) would be nice.
  • Some reference to a definition of a Stanley symmetric function should be given in the doc to the stanley_symmetric_.. methods.
  • The latex in the doc for left_pieri_factoriztions is not properly marked up.
  • In the doc for stanley_symmetric_function_as_polynomial, I don't understand the phrase "The results is given in the ring of symmetric functions in the elementary basis, each factorization having weight prod_i x_i". Can you explain this more fully?

There is a lot of really cool new functionality here. I'm looking forward to it getting in to sage. I'll try to finish this review soon.

comment:4 Changed 7 years ago by nthiery

  • Authors changed from Steve Pon, Nicolas Thiery, Anne Schilling to Steve Pon, Anne Schilling, Nicolas M. Thiéry

comment:5 Changed 7 years ago by jbandlow

Another point--I'm concerned about the following doctest in stanley_symmetric_function_as_polynomial:

    sage: W = WeylGroup(['B',3,1]) 
    sage: W.from_reduced_word([3,2,1]).stanley_symmetric_function_as_polynomial() 
    2.0*x1^3 + x1*x2 + 0.5*x3

The coefficients should be in QQ, I think. Probably you can replace return sum(...) with return R(sum( ... )) .

comment:6 Changed 7 years ago by stevenpon

  • Status changed from needs_work to needs_review

I updated the docs and addressed your concerns about exp_poly_to_sym (it's now included with symmetric functions), as well as putting coefficients in QQ. The patch is also in the combinat queue but currently disabled until Nicolas takes a quick look at my work. It should be back soon, though.

comment:7 follow-up: Changed 7 years ago by nthiery

Hi!

I am currently going through the patch, and will post shortly a reviewer's patch.

comment:8 in reply to: ↑ 7 Changed 7 years ago by nthiery

  • Status changed from needs_review to needs_work

Hi Steve!

I pushed a reviewers patch on the Sage-Combinat server. It fixes a bug or two, improves doctests, removes some unneeded imports, and removes some unneeded code. By the way, I have rebased the Grothendieck patch.

There are still quite a few missing doctests:

> sage -coverage combinat/root_system/pieri_factors.py                          
----------------------------------------------------------------------
combinat/root_system/pieri_factors.py
SCORE combinat/root_system/pieri_factors.py: 77% (28 of 36)
Missing documentation:
	 * elements(self):
	 * __classcall__(cls, W, min_length = 0, max_length = infinity, min_support = frozenset([]), max_support = None):
	 * maximal_elements_combinatorial(self):
Missing doctests:
	 * __iter__(self):
	 * __iter__(self):
	 * stanley_symm_poly_weight(self,w):
	 * maximal_elements_combinatorial(self):
	 * stanley_symm_poly_weight(self, w):

Please fix them, and look for TODO's in the file!

comment:9 follow-up: Changed 7 years ago by stevenpon

  • Status changed from needs_work to needs_review

Thanks Nicolas!

I was not sure how one usually goes about incorporating modifications from a reviewer's patch, so I hope what I did was alright. I incorporated your changes into my patch, added documentation and fixed the TODO's, and then disabled your reviewer patch in the combinat queue. The latest patch is now in the combinat queue and on the trac server.

comment:10 in reply to: ↑ 9 ; follow-up: Changed 7 years ago by nthiery

Replying to stevenpon:

Thanks Nicolas!

I was not sure how one usually goes about incorporating modifications from a reviewer's patch, so I hope what I did was alright. I incorporated your changes into my patch, added documentation and fixed the TODO's, and then disabled your reviewer patch in the combinat queue. The latest patch is now in the combinat queue and on the trac server.

See hg qfold, in the patch server documentation.

I have just added a new reviewer's patch, fixing the lack of tests for __classcall__, and a couple other small issues. Please review, fold, and reupload here. With that, this patch is good to go from a technical view point. I am now running all tests.

Anne: do you think we need further review from the mathematical view point? If yes, do you have suggestions for a reviewer?

comment:11 Changed 7 years ago by nthiery

For the record, all test pass on 4.4.3 on ubuntu linux with the following patches applied:

trac_8704-integer_range_print-fh.patch
trac_9104_freemod_name-fix-nt.patch
trac_8881-functorial_constructions-nt.patch
trac_8742-lazy_format-fh.patch
trac_8742-lazy_format-review-nt.patch
trac_8930-enumerated_set_deprecate-fh.patch
8691_permutation_plainchange_tjb.patch
trac_8926_family_repr-fh.patch
trac_8902-subsets_call_fix-fh.patch
trac_8910-combinatorial_class_parent-fh.patch
trac_8910-subsets_an_element-fh.patch
trac_8888_partition_rim-fh.patch
trac_8888_reviewer_jb.patch
trac_8811_reduced_word_of_translations-nt.patch
trac_8500_transitive_groups-final.patch
trac_8549_cycle_enumerator-nb.patch
trac_8490_square_free-vd.patch
trac_8490_review-sl.patch
trac_9096_disj_union_sphinx_fix-fh.patch
trac_8890-free_module-cleanup-nt.patch
trac_8954-nilTemperley-as.patch
trac_8913-cayley_graph_twosided_labels-nt.patch
trac_8887-typo_monoid_prod-fh.patch
trac_9106-UniqueRep_sphinx_fix-fh.patch
trac_8876-triangular_morphisms_improve-fh.patch
trac_8876-reviewer_patch-jb.patch
trac_9178-attrcall_hash_fix-nt.patch
trac_8911_categorification_crystals-as.patch
trac_8380_gap3_interface.patch
trac_9056_semirings_category-nb.patch
trac_9056_semirings_category-review-nt.patch
trac_8747-testsuite-speedup-fh.patch
trac_9105-categories-primer-improvements-nt.patch
trac_9213-doc_poset_elements-sl.patch
trac_9214-doc_lyndon_word-sl.patch
trac_8984_crystals_alcove_path_model_bj.patch
trac_9215_doc_animate-sl.patch
trac_9216_doc_group_pyx-sl.patch
trac_8562-rebased.patch
trac_9259-combinatorialclass_doc_fix-fh.patch
trac_8810_stanley_symmetric_functions-sp-as.patch
trac_8810_stanley_symmetric_functions-review-nt.patch

comment:12 in reply to: ↑ 10 ; follow-up: Changed 7 years ago by aschilling

Anne: do you think we need further review from the mathematical view point? If yes, do you have suggestions for a reviewer?

If a mathematical review is needed, then Mark Shimozono or Jason Bandlow might be good candidates.

comment:13 in reply to: ↑ 12 Changed 7 years ago by nthiery

Replying to aschilling:

Anne: do you think we need further review from the mathematical view point? If yes, do you have suggestions for a reviewer?

If a mathematical review is needed, then Mark Shimozono or Jason Bandlow might be good candidates.

Good idea. Let's try to save Jason some time for other reviews. Can you please send a quick e-mail to Mark?

comment:14 Changed 7 years ago by aschilling

  • Reviewers set to Nicolas M. Thiéry, Thomas Lam
  • Status changed from needs_review to positive_review

Nicolas Thiery did the technical review of this patch. Thomas Lam did the mathematical review of this patch. His comments are:

Anne,

I dont really know with the code, but I looked at some of the examples and I could not find any problem.

Thomas

Hence I am setting a positive review on this patch.

Release manager, please merge only:

trac_8810_stanley_symmetric_functions-sp-as.2.patch

Changed 7 years ago by davidloeffler

Version without tabs - apply only this patch

comment:15 Changed 7 years ago by davidloeffler

The patch trac_8810_stanley_symmetric_functions-sp-as.2.patch uses tabs for indentation, which is against sage library coding conventions. I have uploaded a version using spaces instead of tabs.

comment:16 Changed 7 years ago by nthiery

Thanks for spotting this!

Steve: please update the patch on the queue!

comment:17 follow-up: Changed 7 years ago by davidloeffler

  • Milestone set to sage-4.5

You might want to go through your combinat queue and check that none of the other patches introduce tabs, because rlm is going to merge #8680 in the next alpha, after which the doctest script will reject any source file that contains a tab character.

comment:18 in reply to: ↑ 17 Changed 7 years ago by nthiery

Replying to davidloeffler:

You might want to go through your combinat queue and check that none of the other patches introduce tabs, because rlm is going to merge #8680 in the next alpha, after which the doctest script will reject any source file that contains a tab character.

Great, I can't wait until #8680 is merged and our devs get early notices about tabs!

comment:19 Changed 7 years ago by mpatel

  • Status changed from positive_review to needs_work

With trac_8810_stanley_symmetric_functions-untabified.patch, I get one docbuild warning:

/mnt/usb1/scratch/mpatel/tmp/sage-4.5.1-rm/local/lib/python2.6/site-packages/sage/combinat/sf/monomial.py:docstring of sage.combinat.sf.monomial.SymmetricFunctionAlgebra_monomial.from_polynomial_exp:36: (ERROR/3) Unknown interpreted text role "function".

I'm about to attach a small patch that should fix this.

Changed 7 years ago by mpatel

Small doc fix. Apply on top of "untabified" patch.

comment:20 Changed 7 years ago by mpatel

  • Status changed from needs_work to needs_review

comment:21 Changed 7 years ago by nthiery

  • Status changed from needs_review to positive_review

Thanks for the fix! I did not rerun the test, but I don't see how the changes could break them either. Positive review!

comment:22 Changed 7 years ago by mpatel

  • Merged in set to sage-4.5.2.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.