Implementation of Knutson-Tao puzzles

[aschilling]

This patch implements Knutson-Tao puzzles in various settings (Grassmannian, equivariant Grassmannian, K theoretic, Belkale-Kumar puzzles).

This code was written during Sage Days 45 at ICERM with Franco Saliola, Anne Schilling, and Avinash Dalal in discussions with Allen Knutson. The code was tested afterwards by Liz Beazley and Ed Richmond.

Apply:

• trac_14141-knutson_tao_puzzles-as.patch​

[aschilling]

Hi Franco,

The patch is basically ready to go now. Could you please look over my changes? Also, there is one method which is currently broken (namely _plot_color_edges), which would still be good to have around.

Thanks!

Anne

[aschilling]

Added documentation to rst file.

Anne

[saliola]

What version is this patch based on ? (It doesn't apply to sage-5.8.)

[aschilling]

Replying to saliola:

What version is this patch based on ? (It doesn't apply to sage-5.8.)

For me it applies to sage-5.9.beta2.

[chapoton]

some stupid suggestions:

• use .. TODO instead of just todo

• use the role :arxiv:`xxxx.xxxx` when citing a paper on arxiv

[aschilling]

Frédéric, thank you for the comments. They should be fixed now. Currently, a more serious issue is the following that Liz observed:

sage: Hps = PuzzleSolver("H")
sage: Hsolns = Hps('001001', '001010')
sage: Puzz = Hsolns[0]
sage: Puzz.LR_tab_from_puzzle()
---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-39-2284d874276b> in <module>()
----> 1 Puzz.LR_tab_from_puzzle()

/Applications/sage-5.9.beta2/local/lib/python2.7/site-packages/sage/combinat/knutson_tao_puzzles.pyc in LR_tab_from_puzzle(self)
   1629                 for j in range(0,lam[k-1]):
   1630                     LRrow.append(None)
-> 1631                 LRrow.extend(self.path_thru_puzzle(i+1))
   1632                 LRtableaux.append(LRrow)
   1633         return SkewTableau(LRtableaux)

/Applications/sage-5.9.beta2/local/lib/python2.7/site-packages/sage/combinat/knutson_tao_puzzles.pyc in path_thru_puzzle(self, coord)
   1565         """
   1566         i = coord
-> 1567         assert self._ne_labels[coord-1] == '1', "The coordinate needs to be a coordinate of a 1 on the north east boundary"
   1568         j = self._n
   1569         k = 0

AssertionError: The coordinate needs to be a coordinate of a 1 on the north east boundary

[chapoton]

By the way, it would be better to avoid the use of assert.

[nthiery]

Replying to chapoton:

By the way, it would be better to avoid the use of assert.

Well, it depends. If it's about checking the internal state of the program, asserts are *good*; we want more of them! If it's about checking the arguments provided directly by a user that's more arguable. See the discussion we had on sage-combinat-devel.

[saliola]

General comments on the patch:

• This patch has not been rebased: it fails to apply on 5.9.beta5 (and on 5.9.rc0 according to the patchbot).
• All tests pass on 5.9.beta5.
• some methods are missing INPUT blocks, some do not describe all the possible input arguments, some do not test all the possible input options

Comments on the interface:

• I don't think that PuzzlePiece, PuzzlePieces, PuzzleSolver should be imported into the global namespace. These names are too generic to apply to only KT puzzles.
• Is it expected that the average user will create new puzzle pieces? or is it that PuzzleSolver will be the most used command?
• I think it would be preferable to have one entry point to the module, from which users import what they need.
• And this entry point should have appropriate documentation describing all the features (kind of like the current documentation to the module, but with some enhancements).
• Perhaps KnutsonTaoPuzzleSolver?

Comments on documentation to the module (top of the file):

• If I do import knutson_tao_puzzles followed by knutson_tao_puzzles?, I see 1/0 0/1 as a puzzle piece. I don't know what this piece is. Is this a problem with the documentation rendering system?
• The string representations should be explained: most people won't know what 1/0 0\1 means.
• The TODO section describes a possible speed up. Isn't this what _fill_strip and _fill_puzzle_by_strips does?

Comments on PartialPuzzle:

• LR_tab_from_puzzle is not a good name. Perhaps just call it skew_lr_tableau.
• plot_thru_puzzle is not a good name. thru is not an English word.
• the error from comment 7 above should be included as a doctest.
• assert should be avoided.
• partition_from_string: I don't know what this method does. The documentation is not descriptive. What is the "string data" of a partition? If this is a standard partition constructor, then should it be in Partition instead?

Comments on PuzzleSolver:

• "Initialize the puzzle solver" is not a sufficient 1-line description since it doesn't mention the kind of puzzles dealt with.
• there is an option called 'maxLetter' in the INPUT section, but the init doesn't take maxLetter as an argument ... oh wait, it's in __classcall_private__. Why is __classcall_private__ needed here?
• there should be doctests that show how to use "maxLetter"
• The output is not a function (but instances of the class happen to be callable).
• several methods are missing the mandatory 1-line string documentation and instead just include examples / tests.

Comments on SchubertCalculusAlgebra:

• should this really be in this module? it seems to experimental (there is also some commented out code that shouldn't be included)
• it was implemented as a proof of concept and has no special features; perhaps it should be deleted and further developed in a separate patch?
• in the doctest for product_on_basis, the base ring of the algebra is QQ, but the coefficients belong to a different ring:

  sage: from sage.combinat.knutson_tao_puzzles import SchubertCalculusAlgebra
  sage: Sc = SchubertCalculusAlgebra(QQ, (3,3)).basis()
  sage: x = Sc[Word('001011')] * Sc[Word('010101')]
  sage: x.parent().base_ring()
  Rational Field
  sage: x.coefficients()[0].parent()
  Multivariate Polynomial Ring in y0, y1, y2, y3, y4, y5, y6 over Integer Ring
  

[saliola]

Oh, and I've attached a file that fixes plotting by colouring only the edges. Fold it if you like it.

[saliola]

I don't have the time to address my comments myself this week with a proper review patch, but I can at some point over the next week. There are a few things to decide beforehand, so we can at least discuss these here in the meantime.

[aschilling]

Replying to saliola:

Oh, and I've attached a file that fixes plotting by colouring only the edges. Fold it if you like it.

Thanks, Franco! Up to a little tweak, I folded the patch and uploaded the new version on trac!

Anne

[aschilling]

Replying to saliola:

General comments on the patch:

• This patch has not been rebased: it fails to apply on 5.9.beta5 (and on 5.9.rc0 according to the patchbot).

I think it depends trivially on #14299 which was merged in sage-5.10.beta0.

Comments on the interface:

• I don't think that PuzzlePiece, PuzzlePieces, PuzzleSolver should be imported into the global namespace. These names are too generic to apply to only KT puzzles.

How would the user then find information about puzzles? If we do not import anything in the namespace, then there is no entry point via tab completion.

• Is it expected that the average user will create new puzzle pieces? or is it that PuzzleSolver will be the most used command?

I think PuzzleSolver will be the most common command. And currently the user does not have to create his/her own puzzle pieces since PuzzleSolver("H") is an option. That's also why I think PuzzleSolver should be in the global namespace.

• I think it would be preferable to have one entry point to the module, from which users import what they need.
• And this entry point should have appropriate documentation describing all the features (kind of like the current documentation to the module, but with some enhancements).
• Perhaps KnutsonTaoPuzzleSolver?

Sure, we could rename it this way.

Comments on documentation to the module (top of the file):

• If I do import knutson_tao_puzzles followed by knutson_tao_puzzles?, I see 1/0 0/1 as a puzzle piece. I don't know what this piece is. Is this a problem with the documentation rendering system?

I do not seem to see this!?

• The string representations should be explained: most people won't know what 1/0 0\1 means.
• The TODO section describes a possible speed up. Isn't this what _fill_strip and _fill_puzzle_by_strips does?

Ok, then please remove this comment!

Comments on PartialPuzzle:

• LR_tab_from_puzzle is not a good name. Perhaps just call it skew_lr_tableau.
• plot_thru_puzzle is not a good name. thru is not an English word.

Ok, feel free to change the names.

• the error from comment 7 above should be included as a doctest.
• assert should be avoided.
• partition_from_string: I don't know what this method does. The documentation is not descriptive. What is the "string data" of a partition? If this is a standard partition constructor, then should it be in Partition instead?

Yes, in fact you can do

        sage: Partitions().from_zero_one([1, 1, 1, 1, 0, 1, 0])
        [5, 4]

But I think the only problem is that one needs the partition to be padded by 0s.

Comments on PuzzleSolver:

• "Initialize the puzzle solver" is not a sufficient 1-line description since it doesn't mention the kind of puzzles dealt with.
• there is an option called 'maxLetter' in the INPUT section, but the init doesn't take maxLetter as an argument ... oh wait, it's in __classcall_private__. Why is __classcall_private__ needed here?

To mend the input, so that UniqueRepresentation? works!

• there should be doctests that show how to use "maxLetter"
• The output is not a function (but instances of the class happen to be callable).
• several methods are missing the mandatory 1-line string documentation and instead just include examples / tests.

I think private methods are not required to have the one line description.

Comments on SchubertCalculusAlgebra:

• should this really be in this module? it seems to experimental (there is also some commented out code that shouldn't be included)

Ed and Liz really liked this feature, to be able to compute structure coefficients in an easy way.

• it was implemented as a proof of concept and has no special features; perhaps it should be deleted and further developed in a separate patch?
• in the doctest for product_on_basis, the base ring of the algebra is QQ, but the coefficients belong to a different ring:

  sage: from sage.combinat.knutson_tao_puzzles import SchubertCalculusAlgebra
  sage: Sc = SchubertCalculusAlgebra(QQ, (3,3)).basis()
  sage: x = Sc[Word('001011')] * Sc[Word('010101')]
  sage: x.parent().base_ring()
  Rational Field
  sage: x.coefficients()[0].parent()
  Multivariate Polynomial Ring in y0, y1, y2, y3, y4, y5, y6 over Integer Ring
  

That is indeed a problem!

I don't have the time to address my comments myself this week with a proper review patch, but I can at some point over the next week. There are a few things to decide beforehand, so we can at least discuss these here in the meantime.

I am looking forward to your review patch next week! I am moving back to Davis tomorrow, so won't have time either to work on this before your review patch.

[nthiery]

I just pushed a micro review patch on the queue that fixes a documentation building error (an itemize which was improperly layed out). Feel free to fold or whatever, I won't touch it further.

[aschilling]

Thanks, Nicolas! I folded the patch. Franco, could you post the review patch that you announced?

[saliola]

Here is a patch that addresses almost all of the issues I raised above. The big changes are as follows:

• renamed PuzzleSolver to KnutsonTaoPuzzleSolver
• improved documentation for KnutsonTaoPuzzleSolver
• renamed PartialPuzzle to PuzzleFilling
• moved cohomology_product to PuzzleSolver.structure_contstants (this way it is more readily available to the user)
• deleted LR_tab_from_puzzle (will be implemented in a future patch)
• deleted SchubertCalculusAlgebra (will be implemented in a future patch)

Apply: trac_14141-knutson_tao_puzzles-as.patch, trac_14141-review-fs.patch

[saliola]

I just found a doctest that passes, but should fail:

        sage: from sage.combinat.knutson_tao_puzzles import BK_pieces
        sage: BK_pieces(3)
        Nablas : [0\0/0, 1\1/1, 2\2/2, 3\3/3]
        Deltas : [0/0\0, 1/1\1, 2/2\2, 3/3\3]

Whoever added this code and doctest should explain what is going on.

And I included a doctest that fails: we need an example of a puzzle with BK pieces.

            sage: ps = KnutsonTaoPuzzleSolver("BK", 3)                                                                                                                                            
            sage: solns = ps('10212', '12012')
            sage: sorted(solns, key=str)

[aschilling]

Hi Franco!

Thanks for your work on this!

I currently get one doctest failure

sage -t knutson_tao_puzzles.py
**********************************************************************
File "knutson_tao_puzzles.py", line 1485, in sage.combinat.knutson_tao_puzzles.KnutsonTaoPuzzleSolver.__init__
Failed example:
    sorted(solns, key=str)
Expected nothing
Got:
    []
**********************************************************************
1 item had failures:
   1 of  40 in sage.combinat.knutson_tao_puzzles.KnutsonTaoPuzzleSolver.__init__
    [342 tests, 1 failure, 0.42 s]
----------------------------------------------------------------------
sage -t knutson_tao_puzzles.py  # 1 doctest failed
----------------------------------------------------------------------
Total time for all tests: 0.6 seconds
    cpu time: 0.3 seconds
    cumulative wall time: 0.4 seconds

I will have a closer look soon.

Best,

Anne

[saliola]

Attached a patch to fix the issues with the BK puzzle pieces. Essentially, a for loop was not indented properly, so puzzle some BK pieces were missing.

Apply: trac_14141-knutson_tao_puzzles-as.patch, trac_14141-review-fs.patch, trac_14141-BK-fix-fs.patch

[aschilling]

Hi Franco!

Thanks for the patches. I folded them and looked them over. One "major" change I made is to put the documentation that was in the init method of KnutsonTaoPuzzleSolver? in its header, so that it actually shows up in the documentation! Before it was invisible to the user from the documentation, but contained the explanation about the main use cases of the code. I also fixed some small issues with the referencing.

If you are happy with the changes, I am happy to set a positive review!

Anne

[aschilling]

Fixed some issues with the documentation. Franco, are we ready to go?

[saliola]

One more small patch that puts some examples of plotting in the documentation string for KnutsonTaoPuzzleSolver.

I'm happy with the patch otherwise. Anne, if you accept my changes, fold it and set this to positive review.

Apply: trac_14141-knutson_tao_puzzles-as.patch, trac_14141-documentation-for-plotting-fs.patch

[aschilling]

Great! I folded the patches and added one more item to the TODO list with a link to the (broken) implementation of the bijection from puzzles to tableaux on the misc server.

[jdemeyer]

! Emergency stop.
 ...                                              
                                                  
l.110743 .../2, 10\PYGZob{}/0, 10\PYGZcb{}(10)/2,}
                                                  
!  ==> Fatal error occurred, no output PDF file produced!
Transcript written on combinat.log.
]]

LaTeX Warning: Hyper reference `sage/modules/free_module_element:sage.modules.f
ree_module_element.FreeModuleElement.nintegrate' on page 72 undefined on input 
line 6250.

[72]make[1]: *** [combinat.pdf] Error 1

[nthiery]

Replying to jdemeyer:

LaTeX Warning: Hyper reference `sage/modules/free_module_element:sage.modules.f
ree_module_element.FreeModuleElement.nintegrate' on page 72 undefined on input 
line 6250.

[72]make[1]: *** [combinat.pdf] Error 1

Just in case this can help: I was struck by this two days ago elsewhere, and it was just because I had forgotten to put a r in front of a documentation string containing '\'.

[aschilling]

Just in case this can help: I was struck by this two days ago elsewhere, and it was just because I had forgotten to put a r in front of a documentation string containing '\'.

Ok, thanks! I added r""" in front of most documentation and removed a link to http which might have caused the problem.

Without more specific instructions on how to debug this, I am not sure what else to do.

Anne

[nthiery]

Replying to aschilling:

Just in case this can help: I was struck by this two days ago elsewhere, and it was just because I had forgotten to put a r in front of a documentation string containing '\'.

Ok, thanks! I added r""" in front of most documentation and removed a link to http which might have caused the problem.

Without more specific instructions on how to debug this, I am not sure what else to do.

    sage -docbuild all html
    sage -docbuild reference/combinat pdf

The first one resolves the various links. The second one should reproduce the error reported by Jeroen; or nothing if it has been fixed.

Cheers,

Nicolas

[aschilling]

My changes did not fix the problem. What is the usual way to debug this?

[saliola]

I added r""" to every documentation string and it worked for me. (Almost all of our documentation strings contain a \.)

Thanks for your help, Nicolas.

I've attached the patch. It's ready for review. Anne, can you test it? Apply the patch and then run the following commands:

sage -b
sage -docbuild all html
sage -docbuild reference/combinat pdf

[aschilling]

Thanks, Franco! I had to make one more change to make it all work!

Anne