Opened 7 years ago

Closed 5 years ago

#15621 closed enhancement (fixed)

Implement regular partition tuples

Reported by: tscrim Owned by: sage-combinat
Priority: major Milestone: sage-7.3
Component: combinatorics Keywords: regular partition tuples
Cc: sage-combinat, andrew.mathas Merged in:
Authors: Travis Scrimshaw Reviewers: Darij Grinberg
Report Upstream: N/A Work issues:
Branch: 6ac8979 (Commits) Commit: 6ac89794e490e0632816701bd736babfb3045d12
Dependencies: Stopgaps:

Description

As the title states and needed for #15508.

Change History (23)

comment:1 Changed 7 years ago by tscrim

  • Status changed from new to needs_review

comment:2 Changed 7 years ago by tscrim

There is a notable change to the behavior of PartitionTuples, in that it now always returns elements of itself (previously it returned partitions if the element was of level 1).

comment:3 follow-up: Changed 7 years ago by andrew.mathas

Hi Travis,

First, I'd like to say that I am very much against the advertised change that PartitionTuples now always returns a element of this class in level 1 as I think that this is mathematically incorrect (...and it will mean that I have to change some of my own code:). On the other hand, if this is necessary for #15508 or #15525 then one way to preserve mathematical correctness might be to use coercions/conversions in level 1? Also, if one does this then in partition_tuple.py shouldn't

sage: [5,1,1] in PartitionTuples() 
True

return False?

Secondly, I am not sure how useful the implemented class RegularPartitionTuples will be. In level 1 this class is useful because the regular partitions index the irreducible representations of the Hecke algebra of type A and (equivalently) a related crystal graph for the irreducible highest weight representation of the quantised affine special linear group. For higher levels I think that the corresponding sets of partition tuples are more complicated than the class you have implemented.

The documentation does not seem to say what an element of RegularPartitionTuples is but from the code it looks like these things are just tuples of regular partitions. These partition tuples do not index the crystal bases of the higher level Fock spaces so if this is what this patch implements then it is probably not what you want for #15508. Except in level 1, the only known descriptions of the partition tuples that arise in the Fock space combinatorics are recursive: more explicitly, these are the partition tuples for which you can construct a path in the crystal graph starting from the empty partition tuple.

I have an implementation of the class that is needed for the Fock spaces in u/andrew.mathas/combinat/tableaux_residues where they are called KleshchevPartitions in partition_tuple.py. If I haven't misread what your code does I would be happy to help in trying to merge these two branches -- I don't care what the class is called. My code first implements "good node sequences" for partition tuples. This is the combinatorial data that you need to describe the realisation of the crystal graph that corresponds to the Fock space. The iterator for KleshchevPartitions then, in effect, constructs the crystal graph.

I wasn't planning on putting this code into sage any time soon because I thought that no one was interested in it apart from me -- although it is already avalable on git. As a result I haven't properly tested my code, although it is documented and it probably works:) It is also worth mentioning that your Fock space code should give another way of constructing these partition (tuples) using the degrees of the higher level "LLT polynomials" that arise (so it shouldn't need this class). Finally, unfortunately, there are at least four different natural conventions for these objects, all of which are probably used by some one -- in level 1, there are two natural choices related by conjugation of partitions and in higher levels you can conjugate and reverse the order of the partitions in the tuple.

Andrew

Last edited 7 years ago by andrew.mathas (previous) (diff)

comment:4 in reply to: ↑ 3 ; follow-ups: Changed 7 years ago by tscrim

  • Status changed from needs_review to needs_work

Hey Andrew,

Replying to andrew.mathas:

First, I'd like to say that I am very much against the advertised change that PartitionTuples now always returns a element of this class in level 1 as I think that this is mathematically incorrect (...and it will mean that I have to change some of my own code:). On the other hand, if this is necessary for #15508 or #15525 then one way to preserve mathematical correctness might be to use coercions/conversions in level 1? Also, if one does this then in partition_tuple.py shouldn't

sage: [5,1,1] in PartitionTuples() 
True

return False?

I was thinking it was necessary for #15508, but then I realized I was directly using the parent class instead of just going through PartitionTuples. I'll change this back, and put some warnings about this. Although I think we should make sure we can convert from level 1 partition tuples to partitions if the user happens to accidentally have created one.

Secondly, I am not sure how useful the implemented class RegularPartitionTuples will be.

...

I wasn't planning on putting this code into sage any time soon because I thought that no one was interested in it apart from me -- although it is already avalable on git. As a result I haven't properly tested my code, although it is documented and it probably works:)

If I understand Fayers correctly, the generalized LLT works for the full tensor product space and the RegularPartitionTuples should index that basis. I had put a TODO message in #15508 about wanting to use a smaller domain. I'm now thinking the best thing to do is just do that now and have both spaces available, but that's something specifically for #15508.

I have #15584 which constructs Kleshchev partitions (as well some other crystals, but I can separate out just the Kleshchev partitions if desired), but does so by using the signature rule. I just skimmed over your code, and I think it's different that how you're doing it, but I very easily could be wrong. Nevertheless, we can check them against each other, and if you want, get your code on Kleshchev partitions into Sage as well. I will then use either of them (whichever turns out to be faster/more useful/put into sage) to index the HW basis for #15508.

It is also worth mentioning that your Fock space code should give another way of constructing these partition (tuples) using the degrees of the higher level "LLT polynomials" that arise (so it shouldn't need this class).

It would be useful for the __getitem__ and _element_constructor_ of the HW repr, but I don't think it wouldn't be useful for creating the indexing set for the basis.

Finally, unfortunately, there are at least four different natural conventions for these objects, all of which are probably used by some one -- in level 1, there are two natural choices related by conjugation of partitions and in higher levels you can conjugate and reverse the order of the partitions in the tuple.

The last one is the oh-so-funTM Kashiwara vs. anti-Kashiwara for tensor products of crystals, but the conjugation should be easy enough to handle. In conclusion there's more to do for #15584, #15525, #15508, and here.

comment:5 in reply to: ↑ 4 ; follow-up: Changed 7 years ago by andrew.mathas

Replying to tscrim:

I was thinking it was necessary for #15508, but then I realized I was directly using the parent class instead of just going through PartitionTuples. I'll change this back, and put some warnings about this. Although I think we should make sure we can convert from level 1 partition tuples to partitions if the user happens to accidentally have created one.

Perhaps I am being too precious here:) In a discussion on sage-combinat Simon King was certainly very much against the current behaviour...and changing this is certainly not so drastic for my code. The main difference/annoyance is that with this change the level 1 partition tuples would be missing many of the methods of their honest partition counter-parts. Another way out would be to force partition tuples to have level at least 2.

If I understand Fayers correctly, the generalized LLT works for the full tensor product space and the RegularPartitionTuples should index that basis. I had put a TODO message in #15508 about wanting to use a smaller domain. I'm now thinking the best thing to do is just do that now and have both spaces available, but that's something specifically for #15508.

OK, I need to look at Fayers properly to see what he does. I've been meaning to do this anyway because my promised comments on #15508 require this.

I have #15584 which constructs Kleshchev partitions (as well some other crystals, but I can separate out just the Kleshchev partitions if desired), but does so by using the signature rule. I just skimmed over your code, and I think it's different that how you're doing it, but I very easily could be wrong. Nevertheless, we can check them against each other, and if you want, get your code on Kleshchev partitions into Sage as well. I will then use either of them (whichever turns out to be faster/more useful/put into sage) to index the HW basis for #15508.

I suspect that it comes down to the same thing: I am guessing that you are using Kashiwarra's theorem for the tensor product of crystal graphs, in which case our methods should be equivalent.

It is also worth mentioning that your Fock space code should give another way of constructing these partition (tuples) using the degrees of the higher level "LLT polynomials" that arise (so it shouldn't need this class).

It would be useful for the __getitem__ and _element_constructor_ of the HW repr, but I don't think it wouldn't be useful for creating the indexing set for the basis.

I agree it is not useful for constructing the indexing set but I think that it does speed up the calculation of e basis for the highest weight module, primarily because the canonical bases elements which appear in L(\Lambda) are identified by their maximal degree term so you don't ever need to compute the set of Kleshchev multipartitions.

Andrew

Last edited 7 years ago by andrew.mathas (previous) (diff)

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

Replying to andrew.mathas:

Perhaps I am being too precious here:) In a discussion on sage-combinat Simon King was certainly very much against the current behaviour...and changing this is certainly not so drastic for my code. The main difference/annoyance is that with this change the level 1 partition tuples would be missing many of the methods of their honest partition counter-parts. Another way out would be to force partition tuples to have level at least 2.

Just to be clear, I'm not changing the output of things like PartitionTuples(level=1), this will still return Partitions, but instead the __iter__() over elements of PartitionTuples() and the corresponding _element_constructor_(), which where not returning elements of the corresponding parent object. So we get things like

sage: P = PartitionTuples()
sage: pt = P([[3,1,1]]); pt
([3, 1, 1])
sage: pt.parent() is P
True

where previously the element constructed was a Partition object whose parent was Partitions(). As I recall, Simon was against the parent object returned what not a subclass of PartitionTuple (but I'm okay with it). I'd be surprised if you were using something specific to Partition when iterating or constructing elements from a parent over varying levels (at least without a check on the level).

comment:7 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:8 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:9 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:10 Changed 5 years ago by git

  • Commit changed from 12f1d6b082f64d8d3ed56d8b04877e99aa634baa to 2ec0a28aa828a2496171fff48989a7d229a7f787

Branch pushed to git repo; I updated commit sha1. New commits:

2ec0a28Merge branch 'public/combinat/regular_partition_tuples' of git://trac.sagemath.org/sage into public/combinat/regular_partition_tuples

comment:11 Changed 5 years ago by git

  • Commit changed from 2ec0a28aa828a2496171fff48989a7d229a7f787 to c6a4f44b22b1c8a90215da7bb9f7f29302bde49a

Branch pushed to git repo; I updated commit sha1. New commits:

2fda619Merge branch 'public/combinat/regular_partition_tuples' of trac.sagemath.org:sage into public/combinat/regular_partition_tuples
c6a4f44Some fixes and tweaks from rebasing.

comment:12 in reply to: ↑ 4 ; follow-up: Changed 5 years ago by tscrim

Hey Andrew,

Replying to tscrim:

Replying to andrew.mathas:

First, I'd like to say that I am very much against the advertised change that PartitionTuples now always returns a element of this class in level 1 as I think that this is mathematically incorrect (...and it will mean that I have to change some of my own code:). On the other hand, if this is necessary for #15508 or #15525 then one way to preserve mathematical correctness might be to use coercions/conversions in level 1? Also, if one does this then in partition_tuple.py shouldn't

sage: [5,1,1] in PartitionTuples() 
True

return False?

I was thinking it was necessary for #15508, but then I realized I was directly using the parent class instead of just going through PartitionTuples. I'll change this back, and put some warnings about this. Although I think we should make sure we can convert from level 1 partition tuples to partitions if the user happens to accidentally have created one.

I noticed an inconsistency with this. In particular, we currently have:-

sage: la = Partition([3,3,1])
sage: PT = PartitionTuples()
sage: la in PT

So either we should have my change where the quoted example should be True, or we change it so that the example I gave returns False. Which would you prefer?

comment:13 Changed 5 years ago by tscrim

  • Milestone changed from sage-6.4 to sage-6.10
  • Status changed from needs_work to needs_info

comment:14 Changed 5 years ago by git

  • Commit changed from c6a4f44b22b1c8a90215da7bb9f7f29302bde49a to 340df1bea4879a7e695d2133edb94993ffa2137a

Branch pushed to git repo; I updated commit sha1. New commits:

340df1bAdding another doctest for containment.

comment:15 Changed 5 years ago by git

  • Commit changed from 340df1bea4879a7e695d2133edb94993ffa2137a to 809cc130b52b00c21f14e57ff2b8296f60dafaed

Branch pushed to git repo; I updated commit sha1. New commits:

809cc13Fixing input of TableauxTuple to handle level 1 partition tuple input.

comment:16 in reply to: ↑ 12 ; follow-up: Changed 5 years ago by andrew.mathas

I noticed an inconsistency with this. In particular, we currently have:-

sage: la = Partition([3,3,1])
sage: PT = PartitionTuples()
sage: la in PT

So either we should have my change where the quoted example should be True, or we change it so that the example I gave returns False. Which would you prefer?

Yes, this is certainly a bug. I would prefer the following:

sage: Partition([3,3,1]) in PartitionTuples()
True
sage: [3,3,1] in PartitionTuples()
True   # ** currently returns False

I am not sure if this is compatible with what you are proposing.

Andrew

comment:17 in reply to: ↑ 16 Changed 5 years ago by tscrim

  • Status changed from needs_info to needs_review

Replying to andrew.mathas:

I noticed an inconsistency with this. In particular, we currently have:-

sage: la = Partition([3,3,1])
sage: PT = PartitionTuples()
sage: la in PT

So either we should have my change where the quoted example should be True, or we change it so that the example I gave returns False. Which would you prefer?

Yes, this is certainly a bug. I would prefer the following:

sage: Partition([3,3,1]) in PartitionTuples()
True
sage: [3,3,1] in PartitionTuples()
True   # ** currently returns False

I am not sure if this is compatible with what you are proposing.

Yes it is as __contains__ does not have to mean the checked object is an honest element of the parent. However it's just the output when passed through PartitionTuples() will be a tuple of size 1:

sage: PT = PartitionTuples()
sage: [3,3,1] in PT
True
sage: PT([3,3,1])
([3, 3, 1])

I was worried about which way you wanted given your statement on comment:3.

However I will add a conversion from level 1 partition tuples to the corresponding set of partitions.

comment:18 Changed 5 years ago by git

  • Commit changed from 809cc130b52b00c21f14e57ff2b8296f60dafaed to f113a0fa7344c1f1c86d74c216c132c75c46e7a1

Branch pushed to git repo; I updated commit sha1. New commits:

f113a0fSome attempts at cleaning up the containment checks and converion from tuples.

comment:19 Changed 5 years ago by tscrim

I also noticed some places where containment checking led to errors being raised and took care of where I saw those on the last commit.

I also elected to not have a level 1 partition tuple register as being contained in Partitions as getting equivalent forms of partition tuples, such as [[4,3,3,1]] and ([4,3,3,1]) (as a tuple/list of a list) seems fraught with issues and lots of checks that would likely cause slowdowns in the containment checks. If you are checking for containment, you probably are going to convert afterwards, so I would actually say the more pythonic way is to try the conversion and then handle the raised error if it cannot be done.

Perhaps more succinctly, I don't think there is necessarily a perfect solution with the current implementation, but this is the best for our current applications.

comment:20 Changed 5 years ago by git

  • Commit changed from f113a0fa7344c1f1c86d74c216c132c75c46e7a1 to 6ac89794e490e0632816701bd736babfb3045d12

Branch pushed to git repo; I updated commit sha1. New commits:

d4e57baMerge branch 'public/combinat/regular_partition_tuples' of git://trac.sagemath.org/sage into partup
637aee7technical improvements to partition.py (j/w/w Travis)
6ac8979various

comment:21 Changed 5 years ago by darij

The code LGTM. Another issue that caught my mind in the process, but isn't exactly related, is #20584.

comment:22 Changed 5 years ago by darij

  • Dependencies #15525 deleted
  • Milestone changed from sage-6.10 to sage-7.3
  • Reviewers set to Darij Grinberg
  • Status changed from needs_review to positive_review

comment:23 Changed 5 years ago by vbraun

  • Branch changed from public/combinat/regular_partition_tuples to 6ac89794e490e0632816701bd736babfb3045d12
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.