Implementation of the Schuetzenberger involution, the Lusztig involution and the promotion operator

[sagetrac-ebeyerstedt]

This patch implements the Schuetzenberger involution on both words and tableaux. In addition it generalizes the promotion operator on tableaux to act not only on rectangular tableaux, but tableaux of any shape.

For crystals in the category ClassicalCrystals, the Lusztig involution is implemented and tested in type A to give the same result as the Schuetzenberger involution.

A section about the Lusztig involution is added to the thematic tutorial on crystals. A copy of the html documentation built using

sage -docbuild thematic_tutorials html

is available here:

http://www.math.ucdavis.edu/~anne/sage/lie/crystals.html

(which might not always be completely up to date).

Apply trac_10446_schuetzenberger_involution-as.patch

CC: @anneschilling @sagetrac-ilke @sagetrac-sage-combinat

Component: combinatorics

Keywords: schuetzenberger, words, crystals

Author: Erin Beyerstedt, Ilke Canakci, Anne Schilling

Reviewer: Jason Bandlow, Nicolas M. Thiéry

Merged: sage-4.7.1.alpha0

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

[anneschilling]

comment:2

This already looks very good!

One suggestion I have is to check whether there is an alphabet associated to a given word 'self'. In this case it would be better to use the maximum of the alphabet instead of the maximum of the appearing letters. For example, if you inputted

sage: w=Word([1,2,3],alphabet=[1,2,3,4,5])
sage: w.alphabet()
Ordered Alphabet [1, 2, 3, 4, 5]

then you would like the Schuetzenberger involution to return the word
345 instead of 123.

Anne

[sagetrac-ebeyerstedt]

Implementation of Schuetzenberger Involution on Words and Tableau

[sagetrac-ebeyerstedt]

comment:6

Attachment: trac_10446_schuetzenberger_involution.patch.gz

This patch now contains two functions, both of which define the schuetzenberger involution - one that works on the class of words and the other on tableau.

[anneschilling]

Reviewer: Anne Schilling

[anneschilling]

comment:8

Replying to @anneschilling:

This looks good and all tests pass! One suggestion I have is that it should be possible to pass the alphabet underlying a given tableau for the method schuetzenberger_involution for tableaux. Currently

sage: t = Tableau([[1,1,4],[2]])
sage: t.schuetzenberger_involution()
[[1, 3, 4], [4]]

but if the underlying alphabet is different, the answer would be different.
This would require to change the method to_word in tableau.py.

Also, for words it would be good to add a test that shows that one can have repeated letters:

sage: w = Word([2,1,1,4], alphabet=[1,2,3,4,5,6])
sage: w.schuetzenberger_involution()
word: 3665

Thanks so much for your work on this!

Anne

[anneschilling]

Changed author from Erin Beyerstedt, Ilke Canakci to Erin Beyerstedt, Ilke Canakci, Anne Schilling

[anneschilling]

Changed reviewer from Anne Schilling to none

[anneschilling]

comment:11

I just fixed the issues with the Schuetzenberger involution that were still bothering me and also added a new implementation of the promotion operator that can now act on tableaux of any shape.

Apply trac_10446_schuetzenberger_involution-as.patch

[jbandlow]

comment:12

Hi Anne,

Thanks for the patch! I am happy to review this. The biggest issue I have right now is the name of the function 'has_letter'. I think that a function with that name should just return True or False. I think what I would prefer is for the method 'cells' to include an optional parameter. So, something like the following behavior:

    sage: t = Tableau([[1,2],[2]])
    sage: t.cells()
    [(0, 0), (0, 1), (1, 0)]
    sage: t.cells(2)
    [(0, 1), (1, 0)]

What do you think?

[nthiery]

comment:13

Replying to @jbandlow:

Thanks for the patch! I am happy to review this. The biggest issue I have right now is the name of the function 'has_letter'. I think that a function with that name should just return True or False. I think what I would prefer is for the method 'cells' to include an optional parameter. So, something like the following behavior:

    sage: t = Tableau([[1,2],[2]])
    sage: t.cells()
    [(0, 0), (0, 1), (1, 0)]
    sage: t.cells(2)
    [(0, 1), (1, 0)]

What do you think?

What about:

    sage: t.cells_containing(2)
    [(0,1), (1,0)]

to not pollute cells with more logic?

[anneschilling]

Changed keywords from schuetzenberger, involution, words to schuetzenberger, words, crystals

[anneschilling]

comment:17

Just posted a new version of the patch including Dan's suggestion that the star map should be created as a dictionary when the crystal is created.

[anneschilling]

comment:18

A new version of the patch is attached, where I changed the map i->i^* to a cached method rather than an attribute of the crystal according to Nicolas' suggestion on the sage-combinat mailing list.

Cheers,

Anne

[anneschilling]

comment:20

Following Dan's suggestions, the Lustzig involution is now a method of ClassicalCrystals. It also works for finite-dimensional highest weight crystals of type E_6 for example. A section on the Lusztig involution is added to the thematic tutorial.

I hope this is now finally ready!

Anne

[anneschilling]

Changed reviewer from Jason Bandlow to Jason Bandlow, Nicolas Thiery

[anneschilling]

comment:22

Posted a slightly revised version incorporating Nicolas' review patch. Jason, could you give it a final review?

Anne

[jbandlow]

comment:23

Hi Anne,

The code looks good to me, but it fails to apply for me to a clean 4.6.2. Are there dependencies?

-Jason

[anneschilling]

comment:24

Hi Jason,

You need to apply this patch to the latest version sage-4.7.alpha4, not sage-4.6.2, since there were a couple of crystal patches merged into sage such as #10632 and #10485.

Cheers,

Anne

[jbandlow]

comment:25

Hi Anne,

I don't have the latest alpha, but I tested the patch on the sage-combinat queue, as well as looked carefully at the code, and it looks good to me.

Thanks!

[anneschilling]

comment:26

Apply trac_10446_schuetzenberger_involution-as.patch

[anneschilling]

comment:27

Hi Jeroen,

Would it be possible to get this patch into sage-4.7 for Sage Days 30?

Thank you,

Anne

[jdemeyer]

comment:29

Replying to @anneschilling:

Hi Jeroen,

Would it be possible to get this patch into sage-4.7 for Sage Days 30?

Well, I kind of made sage-4.7 "feature-complete" already, so I prefer not to do this. Normally, it should go into sage-4.7.1.alpha0 in time for Sage Days 30.

[jdemeyer]

comment:30

Could you remove the following part from the commit message, which doesn't really serve any purpose:

A section about the Lusztig involution is added to the thematic tutorial on crystals.
A copy of the html documentation built using

{{{
sage -docbuild thematic_tutorials html
}}}

is available here:

http://www.math.ucdavis.edu/~anne/sage/lie/crystals.html

(which might not always be completely up to date).

[anneschilling]

comment:31

Attachment: trac_10446_schuetzenberger_involution-as.patch.gz

Replying to @jdemeyer:

Could you remove the following part from the commit message, which doesn't really serve any purpose:

Done. I left the first sentence since it does serve a purpose.

[jdemeyer]

Merged: sage-4.7.1.alpha0

[jdemeyer]

Changed reviewer from Jason Bandlow, Nicolas Thiery to Jason Bandlow, Nicolas M. Thiéry