Bender-Knuth involutions and standardization of semistandard Young tableaux

[darijgr]

I've implemented standardization and Bender-Knuth involutions on straight and skew semistandard tableaux. I've also fixed two typos in error strings and copied some methods for straight tableaux into the skew tableaux file (though I believe much more should be done in this direction).

EDIT: Finished, thanks to Travis.

Apply:

• attachment: trac_14574-folded.patch

CC: @tscrim

Component: combinatorics

Keywords: tableaux, partitions, combinat

Author: Darij Grinberg

Reviewer: Travis Scrimshaw

Merged: sage-5.10.beta5

Issue created by migration from https://trac.sagemath.org/ticket/14574

[darijgr]

Attachment: trac_14574_preliminary_version.patch.gz

not yet merge ready

[darijgr]

Attachment: trac_14574-bender_knuth_et_al-v1.patch.gz

[darijgr]

Attachment: trac_14574-bender_knuth_et_al-v1.2.patch.gz

Finished version -- please review

[darijgr]

comment:3

[trac_14574-bender_knuth_et_al-v1.2.patch] and [trac_14574-bender_knuth_et_al-v1.patch] are the same file; I derped again when uploading.

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:4

Hey Darij,

I've made some changes in my review patch to the implementations. In particular, here's a comparison of my implementation of the Bender-Knuth inversions. Here's mine:

sage: T = SemistandardTableaux(shape=[6,3,3,1], max_entry=5)
sage: T.cardinality()
4000
sage: %time L = [x.bender_knuth_involution(2) for x in T]
CPU times: user 4.49 s, sys: 0.21 s, total: 4.70 s
Wall time: 4.94 s

Yours:

sage: %time L = [x.bender_knuth_involution(2) for x in T]
CPU times: user 4.78 s, sys: 0.11 s, total: 4.88 s
Wall time: 5.16 s

So there's not much difference, but I'd guess mine could be shown (eventually) to be slightly faster on larger sets. Anyways, if you agree with my changes, you can set this to positive review.

Thanks,

Travis

PS - For future reference, you'll need your real name in the authors section.

[tscrim]

Changed author from darij to Darij Grinberg

[darijgr]

comment:6

Hi Travis! That was quick.

skew_tableau.py:

Oops, I have no idea how I managed to add a second to_row method instead of changing the old one; thanks for being more attentive than I was. But could you add these tests

            sage: SkewTableau([[None, None, None], [None]]).to_word_by_row()
            word: 
            sage: SkewTableau([]).to_word_by_row()
            word: 

into the to_word_by_row method? Thanks. (Maybe also into to_word_by_column?)

My reasoning behind the straight=False keyword is that when I call standardization on a standard tableau, I don't want the output to be checked for standardness twice (once for standardness as a skew standard tableau, and then again for standardness when transformed into a standard tableau). Is this a moot point? I am not sure if our classes actually do all that checking, but even if they don't I assume they eventually will.

Here's something I should have done myself: In the docstring of to_permutation, can you explain what "reading order" means? The notation is not as standard as people think it is; for instance, van Leeuwen's Littlewood-Richardson paper ( http://www-math.univ-poitiers.fr/~maavl/pdf/lrr.pdf ) defines "a reading order" rather than "the reading order". (And our reading order is neither Semitic nor Kanji; I don't think anyone ever wrote in that order...)

On line 504 in your revision, replace "self" by "T".

On the next line, "revsersed" should be "reversed".

On line 515, "True" should be backticked from both sides.

Line 576 in your revision: "Bender-Knuth involution" should be "k-th Bender-Knuth involution". Sorry, that one is my own oversight.

Line 587: "over all i" -> "over all i ranging over this iterable" (or however this is normally said).

Line 591 of revision: Again, "True" needs more backticks.

Line 659: Why do you import bisect_right when you don't use it?

Lines 663-694: Is the compiler smart enough that replacing all those calls of result_tab[i] by result_tab_i after first declaring result_tab_i to be result_tab[i] won't add any performance? If so, this could save me some work in the future.

Line 681: Add whitespaces to k+1 for consistency.

tableau.py:

On the docstrings, most of the above stuff applies again (sorry for duplication).

Line 885: Why the "skew"?

Line 892: why did you add "skew"?

Line 938: Could you pass the check variable as well? Or is this automatic?

Good point that the theorems belong into the Examples, not the Tests section. Good job on the docs as well.

[tscrim]

comment:7

This should take care of everything.

For the straight issue, I did not like this way of doing things. However there are other issues in the safety checks being made which I think should be on another ticket. I'm pretty sure some things are checked twice, and there should be a way which naturally converts from (semi)standard skew tableaux to (semi)standard tableaux without (semi)standardness (and tableaux) checks.

Anyways, if you'd want, you can pull out the involution part as a separate function which returns a list of lists. It's up to you if you're fine with my implementation or to change it.

Best,

Travis

[tscrim]

Attachment: trac_14574-bender_knuth-review-ts.patch.gz

[darijgr]

just for comparison

[darijgr]

comment:8

Attachment: for_comparison.patch.gz

Thanks for the speedy review. I've folded the review with my old file and thrown in a couple more corrections. I guess I'll open a separate ticket for unchecked generation of tableau objects; this makes more sense to solve on a global scale.

Here attachment: for_comparison.patch is just the result of folding, without my corrections.

[tscrim]

comment:9

Very minor nitpick, but could you make the commit message more about what the patch does? Once you've done that, you can set this to positive review. Thanks Darij.

[darijgr]

Attachment: trac_14574-folded.patch.txt

[darijgr]

folded version with a few more corrections

[darijgr]

comment:10

Attachment: trac_14574-folded.patch.gz

[vbraun]

comment:11

patchbot:

apply trac_14574-folded.patch

[jdemeyer]

Merged: sage-5.10.beta5