Bijection between Rigged Configurations and Crystal Paths

[tscrim]

Implementation of rigged configurations and Kirillov-Reshetikhin tableaux and the bijection between the two. Also increases speed of Cartan matrix by saving the result.

CC: @sagetrac-sage-combinat @anneschilling

Component: combinatorics

Keywords: Crystals, days30, days38

Author: Travis Scrimshaw

Reviewer: Anne Schilling

Merged: sage-5.4.beta0

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

[saliola]

Changed keywords from Crystals, Days 30 to Crystals, days30

[anneschilling]

comment:3

Hi Travis,

The patch looks close to ready. However, there are still a couple of things that need to be fixed:

• I get doctest failures

    sage -t  "devel/sage-combinat/sage/combinat/rigged_configurations/kleber_tree.py"
**********************************************************************
File "/Applications/sage-5.0/devel/sage-combinat/sage/combinat/rigged_configurations/kleber_tree.py", line 41:
    sage: for x in KT: x
Expected:
    Kleber tree node with weight [2, 1, 2] and upwards edge root [0, 0, 0]
    Kleber tree node with weight [3, 0, 1] and upwards edge root [0, 1, 1]
    Kleber tree node with weight [1, 1, 1] and upwards edge root [1, 1, 1]
    Kleber tree node with weight [0, 0, 2] and upwards edge root [2, 2, 1]
    Kleber tree node with weight [0, 2, 2] and upwards edge root [1, 0, 0]
    Kleber tree node with weight [1, 0, 3] and upwards edge root [1, 1, 0]
    Kleber tree node with weight [2, 0, 0] and upwards edge root [0, 1, 1]
    Kleber tree node with weight [0, 0, 2] and upwards edge root [1, 1, 0]
    Kleber tree node with weight [0, 1, 0] and upwards edge root [1, 1, 1]
    Kleber tree node with weight [0, 1, 0] and upwards edge root [0, 0, 1]
Got:
    Kleber tree node with weight [2, 1, 2] and upwards edge root [0, 0, 0]
    Kleber tree node with weight [0, 2, 2] and upwards edge root [1, 0, 0]
    Kleber tree node with weight [1, 0, 3] and upwards edge root [1, 1, 0]
    Kleber tree node with weight [1, 1, 1] and upwards edge root [1, 1, 1]
    Kleber tree node with weight [0, 0, 2] and upwards edge root [2, 2, 1]
    Kleber tree node with weight [3, 0, 1] and upwards edge root [0, 1, 1]
    Kleber tree node with weight [2, 0, 0] and upwards edge root [0, 1, 1]
    Kleber tree node with weight [0, 0, 2] and upwards edge root [1, 1, 0]
    Kleber tree node with weight [0, 1, 0] and upwards edge root [1, 1, 1]
    Kleber tree node with weight [0, 1, 0] and upwards edge root [0, 0, 1]
**********************************************************************
File "/Applications/sage-5.0/devel/sage-combinat/sage/combinat/rigged_configurations/kleber_tree.py", line 57:
    sage: for x in KT: x
Expected:
    Kleber tree node with weight [1, 1, 2, 0, 0, 0, 0] and upwards edge root [0, 0, 0, 0, 0, 0, 0]
    Kleber tree node with weight [0, 0, 3, 0, 0, 0, 0] and upwards edge root [1, 1, 0, 0, 0, 0, 0]
    Kleber tree node with weight [0, 1, 1, 1, 0, 0, 0] and upwards edge root [1, 1, 1, 0, 0, 0, 0]
    Kleber tree node with weight [1, 0, 1, 0, 1, 0, 0] and upwards edge root [1, 2, 2, 1, 0, 0, 0]
    Kleber tree node with weight [0, 0, 1, 0, 0, 1, 0] and upwards edge root [2, 3, 3, 2, 1, 0, 0]
    Kleber tree node with weight [2, 0, 1, 1, 0, 0, 0] and upwards edge root [0, 1, 1, 0, 0, 0, 0]
    Kleber tree node with weight [1, 0, 0, 2, 0, 0, 0] and upwards edge root [0, 1, 1, 0, 0, 0, 0]
    Kleber tree node with weight [0, 0, 0, 1, 1, 0, 0] and upwards edge root [1, 1, 1, 0, 0, 0, 0]
Got:
    Kleber tree node with weight [1, 1, 2, 0, 0, 0, 0] and upwards edge root [0, 0, 0, 0, 0, 0, 0]
    Kleber tree node with weight [2, 0, 1, 1, 0, 0, 0] and upwards edge root [0, 1, 1, 0, 0, 0, 0]
    Kleber tree node with weight [0, 1, 1, 1, 0, 0, 0] and upwards edge root [1, 1, 1, 0, 0, 0, 0]
    Kleber tree node with weight [1, 0, 1, 0, 1, 0, 0] and upwards edge root [1, 2, 2, 1, 0, 0, 0]
    Kleber tree node with weight [0, 0, 1, 0, 0, 1, 0] and upwards edge root [2, 3, 3, 2, 1, 0, 0]
    Kleber tree node with weight [0, 0, 3, 0, 0, 0, 0] and upwards edge root [1, 1, 0, 0, 0, 0, 0]
    Kleber tree node with weight [1, 0, 0, 2, 0, 0, 0] and upwards edge root [0, 1, 1, 0, 0, 0, 0]
    Kleber tree node with weight [0, 0, 0, 1, 1, 0, 0] and upwards edge root [1, 1, 1, 0, 0, 0, 0]
**********************************************************************
1 items had failures:
   2 of  10 in __main__.example_0
***Test Failed*** 2 failures.
For whitespace errors, see the file /Users/anne/.sage//tmp/kleber_tree_51023.py
	 [9.1 s]

• If you type sage -coverage filename for all the files you added/changed, it says that there are still quite a few methods without doctests. Please bring this up to 100% coverage!

• The file sage/combinat/rigged_configurations/crystal_path_element.py has a comment

    TODO:: Make this equal the number of rigged configurations via iteration. 
 	   A proper is_highest_weight() function without needing to change the index set

Would this be easy to fix? If so, please include it in the patch.

• Why do you return "None" in sage/combinat/rigged_configurations/crystal_path_element.py for the action of e and f if i=0? Perhaps you should have an assertion and return an error "Only classical crystal operators are implemented" or something like this.

• The description at the start of CrystalPaths needs to be changed

class CrystalPaths(AbstractCrystalPaths):
    r"""
    A crystal path is a tensor product of
    :class:`CrystalPathFactors<certain crystals>` which are a generalization
    of Kirillov Reshetikhin (KR) crystals of some affine Kac-Moody algebra.
    
    The reason they are not KR crystals is because the bijection from rigged
    configurations (RC) to crystal paths does not always generate a valid
    tableaux. In particular, for type `D_n^{(1)}` the highest weight RC's will
    correspond to Kashiwara-Nakashima crystals that are highest weight KR
    crystal `B^{r,s}` with some vertical dominos removed from the rectangle.
    The bijection constructs the full rectangle, but in general it is not
    semi-standard.
    
    For more information on KR crystals, see
    :mod:`sage.combinat.crystals.kirillov_reshetikin`.

What you call CrystalPaths is not a generalization of KR crystals, but rather a different model or representation for KR crystals. This representation at the end should be isomorphic to the model for KR crystals in terms of Kashiwara-Nakashima tableaux. Also your link `sage.combinat.crystals.kirillov_reshetikin' is broken since there is an h missing. I suggest to change this description to

class CrystalPaths(AbstractCrystalPaths):
    r"""
    A crystal path is a tensor product of :class:`CrystalPathFactors<certain crystals>`.

    CrystalPaths provide a different model for tensor products of Kirillov-Reshetikhin
    crystals to the model in terms of Kashiwara-Nakashima tableaux.
    Through the bijection with rigged configurations, the tableaux that are produced
    in the CrystalPaths model for type `D_n^{(1)}` are all of rectangular shapes
    and do not necessarily obey the usual strict increase in columns and weak increase
    in rows. The relation between the two tableaux models is given by a filling map.
    For more information see [OSS2011]_ .

    REFERENCES:

        .. [OSS2011] Masato Okado, Reiho Sakamoto, Anne Schilling
           *Affine crystal structure on rigged configurations of type `D_n^{(1)}`*
           J. Algebraic Combinatorics, to appear, doi:10.1007/s10801-012-0383-z (arXiv:1109.3523 [math.QA])
    
    For more information on KR crystals, see
    :mod:`sage.combinat.crystals.kirillov_reshetikhin`.

A similar change should be made to

class CrystalPathFactors(CrystalOfWords):
    r"""
    This is a generalized Kirillov Reshetikhin crystal `B^{r,s}` since it is a
    tableaux with (exactly) `r` rows and `s` columns, but does not need to
    satisfy any row or column restrictions (such as being semi-standard).

    For more information, see :class:`CrystalPaths`.

• I think the names "CrystalPaths" and "CrystalPathFactors" are not optimal. Perhaps "KirillovReshetkhinTableaux" instead of "CrystalPathFactors" as in http://arxiv.org/abs/1109.3523 and "TensorProductsOfKirillovReshetkhinTableaux" or something like this.

• Something is not yet right with your code for CrystalPaths for type D. The number of classically highest weight elements in KR tensor products and CrystalPaths should be the same, but they are not. See also my comment above that the two are just different representations of the same crystal.

    sage: CP = CrystalPaths(['D', 4, 1], [[2,1],[2,1]]); CP
    Crystal paths of type ['D', 4, 1] and tableau shape(s) [[1, 1], [1, 1]]
    sage: len([b for b in CP if b.is_highest_weight()])
    7
    sage: KR = KirillovReshetikhinCrystal(['D',4,1],2,1)
    sage: T = TensorProductOfCrystals(KR,KR)
    sage: len([b for b in T if b.is_highest_weight(index_set=[1,2,3,4])])
    10

• Your description of Kleber trees

r""" 
 		Kleber trees 
 		 
 		This is a standard tree data structure implementation where the nodes 
 		store a weight and are connected to their children and their parent. 
 		However this is also an edge labeled tree and we store the end labels in 
 		the child nodes since this makes the manipulations of this Kleber's tree 
 		easier to implement. 
 		 
 		Note that iteration is done by breath-first since this is how the list is 
 		created. To do depth-first, call depth_first_iter(). 

is very implementation oriented. I think a brief mathematical summary would be appropriate. Say what Kleber trees are used for, how the nodes are labelled etc..

• Can you fix the method _latex_ in KleberTree line 343 and beyond?

• At the beginning of sage/combinat/rigged_configurations/rigged_configuration_element.py please give a brief description of what a rigged configuration element is (like a sequence of partitions together with labelings of the parts).

• Could you please comment on your changes to root_system/cartan_type.py and dynkin_diagram.py. Why are you making these changes?

• Last, but not least: you need to export your file so that it has the right header. The patch should also contain a summary of the changes at the top (before the code). You can achieve this by hg qrefresh -e and then writing the summary.

So much for now!

Anne

[anneschilling]

Reviewer: Anne Schilling

[anneschilling]

Changed keywords from Crystals, days30 to Crystals, days30, days38

[anneschilling]

comment:6

Attachment: trac_11305-rigged_configurations-ts.patch.gz

Travis incorporated all comments I made above and via e-mail. We tested his implementation of the bijection between rigged configurations and KR tableaux against a Mathematica program written by Reiho Sakamoto.

Once all tests pass, I will set a positive review!

Thanks, Travis, for your work on this!

Anne

[jdemeyer]

Merged: sage-5.4.beta0

[jdemeyer]

Additional patch

[jdemeyer]

comment:10

Attachment: 11305_long_time.patch.gz

My additional patch attachment: 11305_long_time.patch needs review (just mention the review in the comments, don't change the status).

[anneschilling]

comment:11

Replying to @jdemeyer:

My additional patch attachment: 11305_long_time.patch needs review (just mention the review in the comments, don't change the status).

Looks ok to me!

Anne