Opened 9 years ago
Closed 6 years ago
#15621 closed enhancement (fixed)
Implement regular partition tuples
Reported by:  Travis Scrimshaw  Owned by:  Sage Combinat CC user 

Priority:  major  Milestone:  sage7.3 
Component:  combinatorics  Keywords:  regular partition tuples 
Cc:  Sage Combinat CC user, Andrew Mathas  Merged in:  
Authors:  Travis Scrimshaw  Reviewers:  Darij Grinberg 
Report Upstream:  N/A  Work issues:  
Branch:  6ac8979 (Commits, GitHub, GitLab)  Commit:  6ac89794e490e0632816701bd736babfb3045d12 
Dependencies:  Stopgaps: 
Description
As the title states and needed for #15508.
Change History (23)
comment:1 Changed 9 years ago by
Status:  new → needs_review 

comment:2 Changed 9 years ago by
comment:3 followup: 4 Changed 9 years ago by
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. 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
comment:4 followups: 5 12 Changed 9 years ago by
Status:  needs_review → 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 inpartition_tuple.py
shouldn'tsage: [5,1,1] in PartitionTuples() Truereturn
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 ohsofun^{TM} Kashiwara vs. antiKashiwara 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 followup: 6 Changed 9 years ago by
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 sagecombinat 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 counterparts. 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
comment:6 Changed 9 years ago by
Replying to andrew.mathas:
Perhaps I am being too precious here:) In a discussion on sagecombinat 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 counterparts. 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 9 years ago by
Milestone:  sage6.1 → sage6.2 

comment:8 Changed 8 years ago by
Milestone:  sage6.2 → sage6.3 

comment:9 Changed 8 years ago by
Milestone:  sage6.3 → sage6.4 

comment:10 Changed 7 years ago by
Commit:  12f1d6b082f64d8d3ed56d8b04877e99aa634baa → 2ec0a28aa828a2496171fff48989a7d229a7f787 

Branch pushed to git repo; I updated commit sha1. New commits:
2ec0a28  Merge branch 'public/combinat/regular_partition_tuples' of git://trac.sagemath.org/sage into public/combinat/regular_partition_tuples

comment:11 Changed 7 years ago by
Commit:  2ec0a28aa828a2496171fff48989a7d229a7f787 → c6a4f44b22b1c8a90215da7bb9f7f29302bde49a 

comment:12 followup: 16 Changed 7 years ago by
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 inpartition_tuple.py
shouldn'tsage: [5,1,1] in PartitionTuples() Truereturn
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 7 years ago by
Milestone:  sage6.4 → sage6.10 

Status:  needs_work → needs_info 
comment:14 Changed 7 years ago by
Commit:  c6a4f44b22b1c8a90215da7bb9f7f29302bde49a → 340df1bea4879a7e695d2133edb94993ffa2137a 

Branch pushed to git repo; I updated commit sha1. New commits:
340df1b  Adding another doctest for containment.

comment:15 Changed 7 years ago by
Commit:  340df1bea4879a7e695d2133edb94993ffa2137a → 809cc130b52b00c21f14e57ff2b8296f60dafaed 

Branch pushed to git repo; I updated commit sha1. New commits:
809cc13  Fixing input of TableauxTuple to handle level 1 partition tuple input.

comment:16 followup: 17 Changed 7 years ago by
I noticed an inconsistency with this. In particular, we currently have:
sage: la = Partition([3,3,1]) sage: PT = PartitionTuples() sage: la in PTSo either we should have my change where the quoted example should be
True
, or we change it so that the example I gave returnsFalse
. 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 Changed 7 years ago by
Status:  needs_info → 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 PTSo either we should have my change where the quoted example should be
True
, or we change it so that the example I gave returnsFalse
. 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 FalseI 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 7 years ago by
Commit:  809cc130b52b00c21f14e57ff2b8296f60dafaed → f113a0fa7344c1f1c86d74c216c132c75c46e7a1 

Branch pushed to git repo; I updated commit sha1. New commits:
f113a0f  Some attempts at cleaning up the containment checks and converion from tuples.

comment:19 Changed 7 years ago by
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 6 years ago by
Commit:  f113a0fa7344c1f1c86d74c216c132c75c46e7a1 → 6ac89794e490e0632816701bd736babfb3045d12 

comment:21 Changed 6 years ago by
The code LGTM. Another issue that caught my mind in the process, but isn't exactly related, is #20584.
comment:22 Changed 6 years ago by
Dependencies:  #15525 

Milestone:  sage6.10 → sage7.3 
Reviewers:  → Darij Grinberg 
Status:  needs_review → positive_review 
comment:23 Changed 6 years ago by
Branch:  public/combinat/regular_partition_tuples → 6ac89794e490e0632816701bd736babfb3045d12 

Resolution:  → fixed 
Status:  positive_review → closed 
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).