Opened 7 years ago

Closed 5 years ago

Last modified 5 years ago

#11305 closed enhancement (fixed)

Bijection between Rigged Configurations and Crystal Paths

Reported by: tscrim Owned by: sage-combinat
Priority: major Milestone: sage-5.4
Component: combinatorics Keywords: Crystals, days30, days38
Cc: sage-combinat, aschilling Merged in: sage-5.4.beta0
Authors: Travis Scrimshaw Reviewers: Anne Schilling
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by aschilling)

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

Attachments (2)

trac_11305-rigged_configurations-ts.patch (184.9 KB) - added by tscrim 5 years ago.
11305_long_time.patch (2.4 KB) - added by jdemeyer 5 years ago.
Additional patch

Download all attachments as: .zip

Change History (13)

comment:1 Changed 7 years ago by saliola

  • Keywords days30 added; Days 30 removed

comment:2 Changed 6 years ago by tscrim

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

comment:3 Changed 6 years ago by aschilling

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`.
  • 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

comment:4 Changed 6 years ago by aschilling

  • Keywords days38 added
  • Reviewers set to Anne Schilling
  • Status changed from needs_review to needs_work

comment:5 follow-up: Changed 5 years ago by tscrim

  • Status changed from needs_work to needs_review

Changed 5 years ago by tscrim

comment:6 in reply to: ↑ 5 Changed 5 years ago by aschilling

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

comment:7 Changed 5 years ago by aschilling

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

comment:8 Changed 5 years ago by jdemeyer

  • Milestone changed from sage-5.3 to sage-5.4

comment:9 Changed 5 years ago by jdemeyer

  • Merged in set to sage-5.4.beta0
  • Resolution set to fixed
  • Status changed from positive_review to closed

Changed 5 years ago by jdemeyer

Additional patch

comment:10 follow-up: Changed 5 years ago by jdemeyer

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

comment:11 in reply to: ↑ 10 Changed 5 years ago by aschilling

Replying to jdemeyer:

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

Looks ok to me!

Anne

Note: See TracTickets for help on using tickets.