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: sage-8.3
Component: combinatorics Keywords: row standard tableaux
Cc: sage-combinat, 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:

Status badges

Description (last modified by andrew.mathas)

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 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:2 Changed 5 years ago by andrew.mathas

  • Cc sage-combinat added

comment:3 Changed 5 years ago by tscrim

  • Cc tscrim darij added
  • 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:

d41fc7dImplementing row standard tableaux of partition shape
eb8b0efImplementing row standard tableaux of partition tuple shape
d88af21Row 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: Changed 5 years ago by git

  • Commit changed from d88af218c5edf36d1437cf7015d747b91ae2f50a to 0beb23787ab087f47a2000af8c46a2cfd870d2ec

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

af5a2beRow standard tableau tuples with residue sequences
bf7646aMerge branch 'u/andrew.mathas/row_standard_tableaux' of git://trac.sagemath.org/sage into t/21162/row_standard_tableaux
0beb237Refactoring 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

Replying to git:

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

af5a2beRow standard tableau tuples with residue sequences
bf7646aMerge branch 'u/andrew.mathas/row_standard_tableaux' of git://trac.sagemath.org/sage into t/21162/row_standard_tableaux
0beb237Refactoring 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:

25e2ecbMerge branch 'develop' into t/21162/row_standard_tableaux
79778daMerging 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:

25e2ecbMerge branch 'develop' into t/21162/row_standard_tableaux
79778daMerging into develop and fixing errant doc-tests

New commits:

25e2ecbMerge branch 'develop' into t/21162/row_standard_tableaux
79778daMerging 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: 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

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 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:

e3e7c21Fixing 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:

76d3534More 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:

7d524cdMerge branch 'u/andrew.mathas/row_standard_tableaux' of git://trac.sagemath.org/sage into u/andrew.mathas/row_standard_tableaux
ef1c28dSome cleanup and improve Tableau(Tuple).

comment:23 follow-up: 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:

cd748a9Fixing 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:

f69cc9dLast 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:

d5a2e36Renaming RowStandardTableaux_residue* -> RowStandardTableauTuples_residue*

comment:29 in reply to: ↑ 23 Changed 4 years ago by andrew.mathas

Replying to gh-darijgr:

    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:

b50cc08Merge 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: 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:

ee43a4bDoc changes

comment:35 in reply to: ↑ 33 Changed 4 years ago by andrew.mathas

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 tscrim

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

LGTM. Darij?

comment:37 follow-up: 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

Replying to 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?)

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:

85d2e3eMore 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:

e908d59Adding q-analogs used in quantum groups.
f4bba3eMerge branch 'public/quantum_groups/q_numbers-25067' into public/modules/fock_space
b4f73faMinor tweaks to documentation
d139e28Merge branch 'public/modules/fock_space' of git://trac.sagemath.org/sage into public/combinat/kleshchev_partitoins-20564
e78de6cFixing duplicate references.
cadff7bAdding mathscinet links
88b72f1Merge branch '8.3.beta0 develop' into t/20564/public/combinat/kleshchev_partitoins-20564
f3fc941Making KleshchevPartitions a lazy import
8263e74A few other touchups.
4de8a8bMerge 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:

2bc9534Fixing 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:

4d19ecdFixing 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:

ba22b7fMerge branch 'develop' into t/20564/public/combinat/kleshchev_partitoins-20564
5e5719eMerge branch 'public/combinat/row_standard_tableaux-21162' of git://trac.sagemath.org/sage into public/combinat/row_standard_tableaux-21162
4aaa086Fixing 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.

comment:51 Changed 4 years ago by andrew.mathas

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.