Opened 5 years ago
Closed 4 years ago
#21162 closed enhancement (fixed)
Row standard tableaux
Reported by:  andrew.mathas  Owned by:  andrew.mathas 

Priority:  major  Milestone:  sage8.3 
Component:  combinatorics  Keywords:  row standard tableaux 
Cc:  sagecombinat, tscrim, darij  Merged in:  
Authors:  Andrew Mathas  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  4aaa086 (Commits, GitHub, GitLab)  Commit:  4aaa0861ededc8d0b10b48f6375cc4d382138758 
Dependencies:  #20564  Stopgaps: 
Description (last modified by )
Implement row standard tableau in sage, of both partition and partition tuple shape. A row standard tableau is a tableau in which the numbers 1,2,...,n
appear in increasing order, from left to right, in each row. These tableau are naturally in bijection with the cosets of the corresponding Young subgroup (or standard parabolic) in the full symmetric group and hence they index bases for various permutation modules, which is why it will be useful to have them.
The shape of a row standard tableau should really be a composition, rather than a partition, but implementing tableau of composition shape would take significantly more effort. For the corresponding modules, up to isomorphism, it is enough to consider row standard tableaux of partition shape so this ticket only considers row standard tableau of partition (tuple) shape. It also defines residue sequences for such tableaux, which are needed in the KLR setting.
The new classes implemented are:
RowStandardTableaux RowStandardTableaux_all RowStandardTableaux_size RowStandardTableaux_shape RowStandardTableauTuples RowStandardTableauTuples_all RowStandardTableauTuples_level RowStandardTableauTuples_size RowStandardTableauTuples_level_size RowStandardTableauTuples_shape RowStandardTableaux_residue RowStandardTableaux_residue_shape
Change History (52)
comment:1 Changed 5 years ago by
 Component changed from PLEASE CHANGE to combinatorics
 Description modified (diff)
 Keywords row standard tableaux added
 Owner changed from (none) to andrew.mathas
 Type changed from PLEASE CHANGE to enhancement
comment:2 Changed 5 years ago by
 Cc sagecombinat added
comment:3 Changed 5 years ago by
 Cc tscrim darij added
 Milestone changed from sage7.3 to sage7.4
comment:4 Changed 5 years ago by
 Branch set to u/andrew.mathas/row_standard_tableaux
comment:5 Changed 5 years ago by
 Commit set to d88af218c5edf36d1437cf7015d747b91ae2f50a
 Description modified (diff)
comment:6 Changed 5 years ago by
 Description modified (diff)
comment:7 Changed 5 years ago by
 Description modified (diff)
comment:8 followup: ↓ 9 Changed 5 years ago by
 Commit changed from d88af218c5edf36d1437cf7015d747b91ae2f50a to 0beb23787ab087f47a2000af8c46a2cfd870d2ec
Branch pushed to git repo; I updated commit sha1. New commits:
af5a2be  Row standard tableau tuples with residue sequences

bf7646a  Merge branch 'u/andrew.mathas/row_standard_tableaux' of git://trac.sagemath.org/sage into t/21162/row_standard_tableaux

0beb237  Refactoring StandardTableaux as a derived class of RowStandardTableaux

comment:9 in reply to: ↑ 8 Changed 5 years ago by
 Status changed from new to needs_review
Replying to git:
Branch pushed to git repo; I updated commit sha1. New commits:
af5a2be Row standard tableau tuples with residue sequences
bf7646a Merge branch 'u/andrew.mathas/row_standard_tableaux' of git://trac.sagemath.org/sage into t/21162/row_standard_tableaux
0beb237 Refactoring StandardTableaux as a derived class of RowStandardTableaux
The last commit message is misleading: this commit makes StandardTableauTuples
inherit from RowStandardTableauTuples
but I ended up leaving StandardTableaux
inheriting from SemiStandardTableaux
, and not making it inherit from RowStandardTableaux
as well, because having it inherit from both wouldn't gain anything and would probably result in a fractional slowdown. The problem is that StandardTableaux
now has two natural parents and there is no reason to prefer one over the other so I let the code history in sage decide. Currently this doesn't affect anything because, for example,
sage: [[1,2,3],[4,5]] in RowStandardTableaux() True sage: [[1,2,3],[4,5]] in RowStandardTableaux(5) True sage: StandardTableau([[1,2,3],[4,5]]) in RowStandardTableaux(5) True
works as one would expect.
comment:10 Changed 5 years ago by
 Status changed from needs_review to needs_work
branch does not merge.
comment:11 Changed 4 years ago by
 Commit changed from 0beb23787ab087f47a2000af8c46a2cfd870d2ec to 79778daf6df73d312f6c17d612e2bf692cedf723
comment:12 Changed 4 years ago by
 Description modified (diff)
 Status changed from needs_work to needs_review
I have merged in to 8.2.rc4. All doc tests pass
New commits:
25e2ecb  Merge branch 'develop' into t/21162/row_standard_tableaux

79778da  Merging into develop and fixing errant doctests

New commits:
25e2ecb  Merge branch 'develop' into t/21162/row_standard_tableaux

79778da  Merging into develop and fixing errant doctests

comment:13 Changed 4 years ago by
patchbot is not happy at all, see the failing plugins
comment:14 followup: ↓ 15 Changed 4 years ago by
The patchbot is hard to please lately. But I am not happy either; a lot of the doc still is copypasted from standard (rather than rowstandard) tableau classes, like this:
+ def cardinality(self): + r""" + Return the number of all standard tableaux of size ``n``. + + The number of standard tableaux of size `n` is equal to the + number of involutions in the symmetric group `S_n`. + This is a consequence of the symmetry of the RSK + correspondence, that if `\sigma \mapsto (P, Q)`, then + `\sigma^{1} \mapsto (Q, P)`. For more information, see + :wikipedia:`RobinsonSchenstedKnuth_correspondence#Symmetry`. +
I'm also wondering why e.g. the __iter__
method on class StandardTableaux_size
has been deleted, and why there are so many seemingly unrelated changes to other classes. Did a merge go wrong?
comment:15 in reply to: ↑ 14 Changed 4 years ago by
Replying to darij:
The patchbot is hard to please lately.
The patchbot errors seem to all be documentation and this builds fine for me. Am missing something?
But I am not happy either; a lot of the doc still is copypasted from standard (rather than rowstandard) tableau classes, like this:
Thanks Darij! Sorry! I completely agree. I think that all of these are fixed in my soontobeuploaded commit. At the same time, I have put in slightly better tests in the sense that the row standard tests now typically use tableaux that are row standard but not standard whereas previously they were often standard tableaux (which are of course also row standard, but that's not the point).
I'm also wondering why e.g. the
__iter__
method on classStandardTableaux_size
has been deleted,
This ticket refactors the standard tableaux classes through the row standard classes. As part of this refactoring StandardTableaux_size
is now a derived class of DisjointUnionEnumeratedSets
so the iterator comes for free.
and why there are so many seemingly unrelated changes to other classes.
As far as I can see there is only one not directly related change and this is adding block
methods to Partition
and PartitionTuple
. In fact, these are related because these classes implement the combinatorial machinery needed to index bases for the standard modules of the KLR algebras of type A
and the block
methods determine when these modules belong to the same block. Apart from this, this ticket only implements row standard tableau of partition and partition tuple shape together with residue sequences for these tableaux. The residue sequences are of course crucial in the KLR setting. The residue sequence classes are not described in the ticket description but they do appear in the list of new classes at the bottom. I can add a description if you'd like.
comment:16 Changed 4 years ago by
OK, I think that I understood what the patchbot was complaining about and I have fixed those too...well, except possibly for the issues with blocks
comment:17 Changed 4 years ago by
 Commit changed from 79778daf6df73d312f6c17d612e2bf692cedf723 to e3e7c216d5a01701a55d0f18da8a3ee984371dd1
Branch pushed to git repo; I updated commit sha1. New commits:
e3e7c21  Fixing doc tests and (some/all?) patchbot issues

comment:18 Changed 4 years ago by
EXAMPLE:: should be EXAMPLES::
and to silent the other plugin, you could just remove the comments
# pretty print
that the patchbot is not smart enough to ignore
comment:19 Changed 4 years ago by
Thanks Frédéric! I think that the patchbot should be happy now.
Btw, it's been a while since I submitted a patch through trac and I'm very impressed with the functionality in the patchbot now. It's really helpful!
comment:20 Changed 4 years ago by
 Commit changed from e3e7c216d5a01701a55d0f18da8a3ee984371dd1 to 76d35345c48a3dbf68a7e1c1d194564c540677cf
Branch pushed to git repo; I updated commit sha1. New commits:
76d3534  More doctests + patchbot happiness

comment:21 Changed 4 years ago by
 Description modified (diff)
comment:22 Changed 4 years ago by
 Branch changed from u/andrew.mathas/row_standard_tableaux to public/combinat/row_standard_tableaux21162
 Commit changed from 76d35345c48a3dbf68a7e1c1d194564c540677cf to ef1c28d58afde27faa8aea936a6d15d28c1ac05b
 Milestone changed from sage7.4 to sage8.3
 Reviewers set to Travis Scrimshaw
Now I got a little carried away with doing cleanup for Tableau(Tuple)
, but some of it was necessary for compatibility with the changes I wanted to do here. In particular, these resulted in a 3x speedup for iteration of the tableau tuples with a fix residue sequence. I also got some other iterator speed improvements, and now the code is using more standard idioms and/or less duplicate checking. There is likely more refactoring to be done, but this overall improves the situation IMO.
TL;DR If my changes are good, then positive review.
New commits:
7d524cd  Merge branch 'u/andrew.mathas/row_standard_tableaux' of git://trac.sagemath.org/sage into u/andrew.mathas/row_standard_tableaux

ef1c28d  Some cleanup and improve Tableau(Tuple).

comment:23 followup: ↓ 29 Changed 4 years ago by
Doc of class RowStandardTableaux? still speaks of standard tableaux. Also this is wrong:
+ elif n in SkewPartitions(): + from sage.combinat.skew_tableau import StandardSkewTableaux + return StandardSkewTableaux(n)
I see the word "semirow" used several times in the doc of tableau tuple classes, but never defined.
A class for row standard tableau of shape a partition tuple. This is a tuple of row standard tableau with entries `1, 2, \ldots, n`, where `n` is the size of the underlying partition tuple, such that the entries increase along rows in each component of the tuple.
This isn't very clear. You want to say:
A class for row standard tableau tuples of shape a partition tuple. A row standard tableau tuple of shape `(\lambda_1, \lambda_2, \ldots, \lambda_k)` is a tuple `(T_1, T_2, \ldots, T_k)`, where each `T_i` is a tableau of shape `\lambda_i` whose entries increase along rows, and with the following property: If we set `n = \lambda_1 + \lambda_2 + \cdots + \lambda_k`, then each of the numbers `1, 2, \ldots, n` appears in exactly one of the `T_i`, and appears exactly once in this `T_i`.
In the tableau_tuple.py
file, shouldn't Class RowStandardTableaux_residue
be renamed Class RowStandardTableauTuples_residue
?
comment:24 Changed 4 years ago by
 Commit changed from ef1c28d58afde27faa8aea936a6d15d28c1ac05b to cd748a9e7546d846380e4a4859ae49e7d62e38ab
Branch pushed to git repo; I updated commit sha1. New commits:
cd748a9  Fixing the doc.

comment:25 Changed 4 years ago by
I fixed a few things but not all.
comment:26 Changed 4 years ago by
 Commit changed from cd748a9e7546d846380e4a4859ae49e7d62e38ab to f69cc9d9b82a3114ce564e8be88f86be541d5795
Branch pushed to git repo; I updated commit sha1. New commits:
f69cc9d  Last little bit.

comment:27 Changed 4 years ago by
Okay, this takes care of the rest of comment:23.
comment:28 Changed 4 years ago by
 Commit changed from f69cc9d9b82a3114ce564e8be88f86be541d5795 to d5a2e365077e7b4d2b1ea740262cbec8df1a0a27
Branch pushed to git repo; I updated commit sha1. New commits:
d5a2e36  Renaming RowStandardTableaux_residue* > RowStandardTableauTuples_residue*

comment:29 in reply to: ↑ 23 Changed 4 years ago by
Replying to ghdarijgr:
A class for row standard tableau of shape a partition tuple. This is a tuple of row standard tableau with entries `1, 2, \ldots, n`, where `n` is the size of the underlying partition tuple, such that the entries increase along rows in each component of the tuple.This isn't very clear. You want to say:
A class for row standard tableau tuples of shape a partition tuple. A row standard tableau tuple of shape `(\lambda_1, \lambda_2, \ldots, \lambda_k)` is a tuple `(T_1, T_2, \ldots, T_k)`, where each `T_i` is a tableau of shape `\lambda_i` whose entries increase along rows, and with the following property: If we set `n = \lambda_1 + \lambda_2 + \cdots + \lambda_k`, then each of the numbers `1, 2, \ldots, n` appears in exactly one of the `T_i`, and appears exactly once in this `T_i`. }}
I have rewritten this as:
A row standard tableau tuple of size `n` is an ordered tuple of row standard tableaux (see :class:`RowStandardTableau`), with entries `1, 2, \ldots, n` such that, in each component, the entries are in increasing order along each row. If the tableau in component `k` has shape `\lambda^{(k)}` then `\lambda=(\lambda^{(1)},\ldots,\lambda^{(l)}` is a :class:`PartitionTuple`.
Using lambda_k
to refer the the components of the partition is likely to confuse because \lambda_k
is commonly used for a part of a partition. Having explicit references to the row
standard and partition tuple classes should remove any ambiguity.
comment:30 Changed 4 years ago by
Yeah, good point Andrew (and thanks Travis for fixing the comments).
comment:31 Changed 4 years ago by
 Commit changed from d5a2e365077e7b4d2b1ea740262cbec8df1a0a27 to b50cc08fae3ccba0302c8f52cbcba7e123f154c4
Branch pushed to git repo; I updated commit sha1. New commits:
b50cc08  Merge 8.3.beta0/develop into t/21162/public/combinat/row_standard_tableaux21162

comment:32 Changed 4 years ago by
Travis and Darij thanks for your work on this  especially the speed ups. I just pushed the change to the docs mentioned in comment #29. I also killed off the last semirow
 all of which were typos, so thanks for spotting them  and merged into 8.3.beta0.
The patchbot errors were confusing me but I now realise that they are related to https://groups.google.com/forum/#!searchin/sagedevel/20382%7Csort:date/sagedevel/BUKf_lI1fJw/gqHCRlpmCAAJ
comment:33 followup: ↓ 35 Changed 4 years ago by
Andrew, it looks like the changes you mentioned have not been merged in.
comment:34 Changed 4 years ago by
 Commit changed from b50cc08fae3ccba0302c8f52cbcba7e123f154c4 to ee43a4b215fff0aa736b5c17e1caee6cc566bf66
Branch pushed to git repo; I updated commit sha1. New commits:
ee43a4b  Doc changes

comment:35 in reply to: ↑ 33 Changed 4 years ago by
Replying to tscrim:
Andrew, it looks like the changes you mentioned have not been merged in.
Thanks. Done now.
comment:36 Changed 4 years ago by
 Reviewers changed from Travis Scrimshaw to Travis Scrimshaw, Darij Grinberg
LGTM. Darij?
comment:37 followup: ↓ 38 Changed 4 years ago by
Don't put my name in the reviewers list. I had perhaps 10 mins of eyes on the branch, and I don't know the whole reptheory stuff it's for, so all I could do is look for obvious bugs in the doc.
I don't see any more now, little as it means. But if I were you, I'd put a definition of "quantum characteristic" and "block" into the block
method on partition.py. (Blocks of what group? In what characteristic? Or totally unrelated?) Also maybe not talk about "partition tuple self
" in there, since I assume it's a 1partition tuple?
comment:38 in reply to: ↑ 37 Changed 4 years ago by
Replying to ghdarijgr:
Don't put my name in the reviewers list. I had perhaps 10 mins of eyes on the branch, and I don't know the whole reptheory stuff it's for, so all I could do is look for obvious bugs in the doc.
I don't see any more now, little as it means. But if I were you, I'd put a definition of "quantum characteristic" and "block" into the
block
method on partition.py. (Blocks of what group? In what characteristic? Or totally unrelated?)
I have rewritten the documentation for the block method. In particular, previously it said towards the end that this method is for blocks of the cyclotomic Hecke algebras of type A and it now says this at the top and with a little more detail. I have replaced quantum characteristic
with :meth:quantum_characteristic
I also fixed up the referencing relating to this ticket  there are still a few other embedded references in these files rather than in index.rst
...
Also maybe not talk about "partition tuple
self
" in there, since I assume it's a 1partition tuple?
Ah, I see that I was updating code for the block method of a residue sequence. I have now also revised the documentation for the block
methods of partitions and partition tuples.
comment:39 Changed 4 years ago by
 Commit changed from ee43a4b215fff0aa736b5c17e1caee6cc566bf66 to 85d2e3e6d0a064e113054ce8f6823173e61a1a63
Branch pushed to git repo; I updated commit sha1. New commits:
85d2e3e  More documentation tweaks

comment:40 Changed 4 years ago by
 Reviewers changed from Travis Scrimshaw, Darij Grinberg to Travis Scrimshaw
 Status changed from needs_review to positive_review
Since Darij does not want to be considered as a reviewer, I've removed his name (I disagree, but as he wishes).
The current state of affairs LGTM. We can make more improvements, e.g., bringing things to the master reference file, on later tickets.
comment:41 Changed 4 years ago by
Thanks very much Travis  and, unofficially, Darij!
There will be merge conflicts when the Kleshchev partition ticket, which will should go in first, but I will fix those when they come.
comment:42 Changed 4 years ago by
 Commit changed from 85d2e3e6d0a064e113054ce8f6823173e61a1a63 to 4de8a8b5bcfdea3cf12b85c30de0c07e9d0a4937
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. Last 10 new commits:
e908d59  Adding qanalogs used in quantum groups.

f4bba3e  Merge branch 'public/quantum_groups/q_numbers25067' into public/modules/fock_space

b4f73fa  Minor tweaks to documentation

d139e28  Merge branch 'public/modules/fock_space' of git://trac.sagemath.org/sage into public/combinat/kleshchev_partitoins20564

e78de6c  Fixing duplicate references.

cadff7b  Adding mathscinet links

88b72f1  Merge branch '8.3.beta0 develop' into t/20564/public/combinat/kleshchev_partitoins20564

f3fc941  Making KleshchevPartitions a lazy import

8263e74  A few other touchups.

4de8a8b  Merge branch 'public/combinat/row_standard_tableaux21162' of git://trac.sagemath.org/sage into public/combinat/row_standard_tableaux21162

comment:43 Changed 4 years ago by
 Dependencies set to #20564
 Status changed from needs_review to positive_review
I just decided to beat it to the punch so both tickets could be merged in the same beta. Trivial rebase.
comment:44 Changed 4 years ago by
+.. [DJM1999] \R. Dipper, G. James and A. Mathas + *The cyclotomic qSchur algebra*, Math. Z, **229** (1999), 385416. + :mathscinet:`MR1635149`
Isn't it "Cyclotomic qSchur algebras" or am I getting two papers confused?
comment:45 Changed 4 years ago by
 Commit changed from 4de8a8b5bcfdea3cf12b85c30de0c07e9d0a4937 to 2bc9534c6ce5937181efe36afbf3e92d2d3df0ca
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
2bc9534  Fixing DJM reference

comment:46 Changed 4 years ago by
 Commit changed from 2bc9534c6ce5937181efe36afbf3e92d2d3df0ca to 4d19ecd7069917b53b8ce797f97f3dfbc17cbaf4
Branch pushed to git repo; I updated commit sha1. New commits:
4d19ecd  Fixing mathscinet reference

comment:47 Changed 4 years ago by
 Status changed from needs_review to positive_review
That's embarrassing! I had the title wrong. The year wrong *and* the mathscinet reference wrong:(
comment:48 Changed 4 years ago by
Documentation fails to build
.. [BKW2011]_ \J. Brundan, A. Kleshchev, and W. Wang,
shouldn't have _
like other entries.
comment:49 Changed 4 years ago by
 Commit changed from 4d19ecd7069917b53b8ce797f97f3dfbc17cbaf4 to 4aaa0861ededc8d0b10b48f6375cc4d382138758
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
ba22b7f  Merge branch 'develop' into t/20564/public/combinat/kleshchev_partitoins20564

5e5719e  Merge branch 'public/combinat/row_standard_tableaux21162' of git://trac.sagemath.org/sage into public/combinat/row_standard_tableaux21162

4aaa086  Fixing the docbuild.

comment:50 Changed 4 years ago by
 Status changed from needs_review to positive_review
Fixed. Thank you for catching that.
Also rebased over the latest develop and #20564.
comment:51 Changed 4 years ago by
Thanks Travis!
comment:52 Changed 4 years ago by
 Branch changed from public/combinat/row_standard_tableaux21162 to 4aaa0861ededc8d0b10b48f6375cc4d382138758
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
Implementing row standard tableaux of partition shape
Implementing row standard tableaux of partition tuple shape
Row standard tableau tuples with residue sequences