Opened 5 years ago

Closed 4 years ago

# Row standard tableaux

Reported by: Owned by: andrew.mathas andrew.mathas major sage-8.3 combinatorics row standard tableaux sage-combinat, tscrim, darij Andrew Mathas Travis Scrimshaw N/A 4aaa086 4aaa0861ededc8d0b10b48f6375cc4d382138758 #20564

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


### comment:1 Changed 5 years ago by andrew.mathas

• Authors set to Andrew Mathas
• 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:3 Changed 5 years ago by tscrim

• Milestone changed from sage-7.3 to sage-7.4

### comment:4 Changed 5 years ago by andrew.mathas

• Branch set to u/andrew.mathas/row_standard_tableaux

### comment:5 Changed 5 years ago by andrew.mathas

• Commit set to d88af218c5edf36d1437cf7015d747b91ae2f50a
• Description modified (diff)

New commits:

 ​d41fc7d Implementing row standard tableaux of partition shape ​eb8b0ef Implementing row standard tableaux of partition tuple shape ​d88af21 Row standard tableau tuples with residue sequences

### comment:6 Changed 5 years ago by andrew.mathas

• Description modified (diff)

### comment:7 Changed 5 years ago by andrew.mathas

• Description modified (diff)

### comment:8 follow-up: ↓ 9 Changed 5 years ago by git

• 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 andrew.mathas

• Status changed from new to needs_review

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 slow-down. 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 cheuberg

• Status changed from needs_review to needs_work

branch does not merge.

### comment:11 Changed 4 years ago by git

• Commit changed from 0beb23787ab087f47a2000af8c46a2cfd870d2ec to 79778daf6df73d312f6c17d612e2bf692cedf723

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

 ​25e2ecb Merge branch 'develop' into t/21162/row_standard_tableaux ​79778da Merging into develop and fixing errant doc-tests

### comment:12 Changed 4 years ago by andrew.mathas

• 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 doc-tests

New commits:

 ​25e2ecb Merge branch 'develop' into t/21162/row_standard_tableaux ​79778da Merging into develop and fixing errant doc-tests

### comment:13 Changed 4 years ago by chapoton

patchbot is not happy at all, see the failing plugins

### comment:14 follow-up: ↓ 15 Changed 4 years ago by darij

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 row-standard) 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:Robinson-Schensted-Knuth_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?

Last edited 4 years ago by darij (previous) (diff)

### comment:15 in reply to: ↑ 14 Changed 4 years ago by andrew.mathas

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 row-standard) tableau classes, like this:

Thanks Darij! Sorry! I completely agree. I think that all of these are fixed in my soon-to-be-uploaded 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 class StandardTableaux_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.

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

### comment:16 Changed 4 years ago by andrew.mathas

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 git

• 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 chapoton

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

Last edited 4 years ago by chapoton (previous) (diff)

### comment:19 Changed 4 years ago by andrew.mathas

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!

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

### comment:20 Changed 4 years ago by git

• Commit changed from e3e7c216d5a01701a55d0f18da8a3ee984371dd1 to 76d35345c48a3dbf68a7e1c1d194564c540677cf

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

 ​76d3534 More doc-tests + patchbot happiness

### comment:21 Changed 4 years ago by andrew.mathas

• Description modified (diff)

### comment:22 Changed 4 years ago by tscrim

• Branch changed from u/andrew.mathas/row_standard_tableaux to public/combinat/row_standard_tableaux-21162
• Commit changed from 76d35345c48a3dbf68a7e1c1d194564c540677cf to ef1c28d58afde27faa8aea936a6d15d28c1ac05b
• Milestone changed from sage-7.4 to sage-8.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 follow-up: ↓ 29 Changed 4 years ago by gh-darijgr

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?

Last edited 4 years ago by gh-darijgr (previous) (diff)

### comment:24 Changed 4 years ago by git

• 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 tscrim

I fixed a few things but not all.

### comment:26 Changed 4 years ago by git

• 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 tscrim

Okay, this takes care of the rest of comment:23.

### comment:28 Changed 4 years ago by git

• 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 andrew.mathas

    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 gh-darijgr

Yeah, good point Andrew (and thanks Travis for fixing the comments).

### comment:31 Changed 4 years ago by git

• 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_tableaux-21162

### comment:32 Changed 4 years ago by andrew.mathas

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/sage-devel/20382%7Csort:date/sage-devel/BUKf_lI1fJw/gqHCRlpmCAAJ

### comment:33 follow-up: ↓ 35 Changed 4 years ago by tscrim

Andrew, it looks like the changes you mentioned have not been merged in.

### comment:34 Changed 4 years ago by git

• 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 andrew.mathas

Andrew, it looks like the changes you mentioned have not been merged in.

Thanks. Done now.

### comment:36 Changed 4 years ago by tscrim

• Reviewers changed from Travis Scrimshaw to Travis Scrimshaw, Darij Grinberg

LGTM. Darij?

### comment:37 follow-up: ↓ 38 Changed 4 years ago by gh-darijgr

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 rep-theory 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 1-partition tuple?

### comment:38 in reply to: ↑ 37 Changed 4 years ago by andrew.mathas

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 rep-theory 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 1-partition 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.

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

### comment:39 Changed 4 years ago by git

• 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 tscrim

• 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 andrew.mathas

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 git

• 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 q-analogs used in quantum groups. ​f4bba3e Merge branch 'public/quantum_groups/q_numbers-25067' 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_partitoins-20564 ​e78de6c Fixing duplicate references. ​cadff7b Adding mathscinet links ​88b72f1 Merge branch '8.3.beta0 develop' into t/20564/public/combinat/kleshchev_partitoins-20564 ​f3fc941 Making KleshchevPartitions a lazy import ​8263e74 A few other touchups. ​4de8a8b Merge branch 'public/combinat/row_standard_tableaux-21162' of git://trac.sagemath.org/sage into public/combinat/row_standard_tableaux-21162

### comment:43 Changed 4 years ago by tscrim

• 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 darij

+.. [DJM1999] \R. Dipper, G. James and A. Mathas
+             *The cyclotomic q-Schur algebra*, Math. Z, **229** (1999), 385-416.
+             :mathscinet:MR1635149


Isn't it "Cyclotomic q-Schur algebras" or am I getting two papers confused?

### comment:45 Changed 4 years ago by git

• 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 git

• 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 andrew.mathas

• 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 fbissey

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 git

• 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_partitoins-20564 ​5e5719e Merge branch 'public/combinat/row_standard_tableaux-21162' of git://trac.sagemath.org/sage into public/combinat/row_standard_tableaux-21162 ​4aaa086 Fixing the docbuild.

### comment:50 Changed 4 years ago by tscrim

• Status changed from needs_review to positive_review

Fixed. Thank you for catching that.

Also rebased over the latest develop and #20564.

Thanks Travis!

### comment:52 Changed 4 years ago by vbraun

• Branch changed from public/combinat/row_standard_tableaux-21162 to 4aaa0861ededc8d0b10b48f6375cc4d382138758
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.