Sage: Ticket #17252: bug fix in StrongTableaux.marked_CST_to_transposition_sequence
https://trac.sagemath.org/ticket/17252
<p>
Anne Schilling pointed out the following error in the algorithm to convert a strong marked column strict tableau to a sequence of transpositions:
</p>
<pre class="wiki">sage: StrongTableaux.marked_CST_to_transposition_sequence([[-1,-2,-2,-2,-2],[-2,2],[2]],3)
[[4, 5], [3, 4], [2, 4], [2, 3], [1, 2], [0, 1]]
</pre><p>
however the answer should be <code>[[4,5],[3,4],[2,3],[1,2],[-1,0],[0,1]]</code> and the problem arises because it was never clear in the algorithm for converting a marked column strict tableau into a sequence of transpositions what conditions I need to check to make sure I was applying a valid transposition. In fact, there was a comment in the code that indicated my worry that one might be able to apply two transpositions and reduce the length by 1.
</p>
<p>
This is exactly what happens in this case because if you apply the sequence of transpositions t_{2,4} on t_{3,4} t_{4,5} T then in fact t_{2,4} does reduce the length of shape of the tableau by 1, but there are no cells of content 2 and 3 in the tableau t_{3,4} t_{4,5} T.
</p>
<p>
The fix was to implement the method <code>to_transposition_sequence</code> recursively by checking that the result of applying <code>t_{i,j}</code> can reduced to the empty core.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/17252
Trac 1.1.6zabrockiWed, 29 Oct 2014 14:58:48 GMTcommit, branch set
https://trac.sagemath.org/ticket/17252#comment:1
https://trac.sagemath.org/ticket/17252#comment:1
<ul>
<li><strong>commit</strong>
set to <em>a48b105bfb91aaeacac7cd6606b57aa585f3bc23</em>
</li>
<li><strong>branch</strong>
set to <em>public/combinat/zabrocki/fixstrongtableaux/17252</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=8d76e45605f28d90c2406173de95e8f5b1838ee9"><span class="icon"></span>8d76e45</a></td><td><code>initial fix by adding extra condition to check</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=a48b105bfb91aaeacac7cd6606b57aa585f3bc23"><span class="icon"></span>a48b105</a></td><td><code>cleaned up the conditions being checked, added test for error</code>
</td></tr></table>
TicketzabrockiWed, 29 Oct 2014 15:03:24 GMTstatus changed
https://trac.sagemath.org/ticket/17252#comment:2
https://trac.sagemath.org/ticket/17252#comment:2
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TicketzabrockiWed, 29 Oct 2014 16:06:39 GMTstatus changed
https://trac.sagemath.org/ticket/17252#comment:3
https://trac.sagemath.org/ticket/17252#comment:3
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
More testing shows that checking the conditions in the ribbon is not sufficient.
</p>
<p>
Example:
Let
<code>T = [[-1, -2, -5, 5, -5, 5, -5], [-3, -4, 5, 5], [5]]</code>
if you apply the transposition t_{6,7} to T then the shape will be <code>[6,3]</code> leaving
<code>[[-1, -2, -5, 5, -5, 5], [-3, -4, 5]]</code>
and the marking is in cell (0,6) as hoped
if you apply the transposition t_{5,7} to T then the shape will be<code> [5,2,1]</code> leaving
<code>[[-1, -2, -5, 5, -5], [-3, -4], [5]]</code>
</p>
<p>
The markings in both cases are correct, but the right transposition to apply is the t_{5,7}.
</p>
<p>
The only way reason why you don't want to apply the t_{6,7} is just because no corner cell of t_{6,7} T has a marking. But I can only hope that checking this catches all cases.
</p>
TicketzabrockiWed, 29 Oct 2014 17:04:38 GMT
https://trac.sagemath.org/ticket/17252#comment:4
https://trac.sagemath.org/ticket/17252#comment:4
<p>
Testing if one of the corner cells has a mark is not sufficient because it could be that the next ribbon to remove is of shape (1,1) and the marked cell will not be on a corner.
</p>
<p>
I am coming to the conclusion that the test will need to be recursive. That is, the transposition sequence begins in t_{ij} if t_{ij} is a removable ribbon and if t_{ij} T has a transposition sequence which reduces it to empty.
</p>
TicketgitWed, 29 Oct 2014 19:48:20 GMTcommit changed
https://trac.sagemath.org/ticket/17252#comment:5
https://trac.sagemath.org/ticket/17252#comment:5
<ul>
<li><strong>commit</strong>
changed from <em>a48b105bfb91aaeacac7cd6606b57aa585f3bc23</em> to <em>6b696d93d08d273a0414586a2993bfffd909aa83</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=6b696d93d08d273a0414586a2993bfffd909aa83"><span class="icon"></span>6b696d9</a></td><td><code>made the function recursive and this seems to solve the problem : TODO remove #print statements</code>
</td></tr></table>
TicketgitWed, 29 Oct 2014 20:29:11 GMTcommit changed
https://trac.sagemath.org/ticket/17252#comment:6
https://trac.sagemath.org/ticket/17252#comment:6
<ul>
<li><strong>commit</strong>
changed from <em>6b696d93d08d273a0414586a2993bfffd909aa83</em> to <em>6b738d2d2abfded2ae67258008d29c6499fa54a2</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=6b738d2d2abfded2ae67258008d29c6499fa54a2"><span class="icon"></span>6b738d2</a></td><td><code>added the problem tests, deleted the #print statements, fixed a problem by returning None</code>
</td></tr></table>
TicketzabrockiWed, 29 Oct 2014 21:04:02 GMTstatus changed
https://trac.sagemath.org/ticket/17252#comment:7
https://trac.sagemath.org/ticket/17252#comment:7
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
I've been testing these functions and don't see any obvious change in speed, and this does seem to completely fix the bug.
</p>
<p>
The solution that I have posted is to make the function which converts a column strict marked tableau into a sequence of transpositions recursive. The solution is to say that the transposition sequence which reduces a tableau T of shape \gamma to empty begins with t_{ij} if the cells of content j is negative -v and the other labels of are v (and this is what was being done before) and t_{ij} T can be reduced to an empty tableau (and this part is new).
</p>
<p>
I had to add this second condition because it seems that we can't decide if applying t_{ij} to a column strict marked tableau yields a valid column strict marked tableau just by looking it in any obvious way. Examples need to be pretty large before this bug was triggered.
</p>
TicketgitWed, 29 Oct 2014 21:44:24 GMTcommit changed
https://trac.sagemath.org/ticket/17252#comment:8
https://trac.sagemath.org/ticket/17252#comment:8
<ul>
<li><strong>commit</strong>
changed from <em>6b738d2d2abfded2ae67258008d29c6499fa54a2</em> to <em>3ee5f3639269ac461dc29f2d300d8a40a2ad48af</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=3ee5f3639269ac461dc29f2d300d8a40a2ad48af"><span class="icon"></span>3ee5f36</a></td><td><code>change to .to_transposition_sequence() so that the standard marked tableau is used</code>
</td></tr></table>
TickettscrimWed, 29 Oct 2014 22:55:21 GMTcc changed
https://trac.sagemath.org/ticket/17252#comment:9
https://trac.sagemath.org/ticket/17252#comment:9
<ul>
<li><strong>cc</strong>
<em>tscrim</em> added
</li>
</ul>
TicketgitThu, 30 Oct 2014 05:17:02 GMTcommit changed
https://trac.sagemath.org/ticket/17252#comment:10
https://trac.sagemath.org/ticket/17252#comment:10
<ul>
<li><strong>commit</strong>
changed from <em>3ee5f3639269ac461dc29f2d300d8a40a2ad48af</em> to <em>381acd835802d712e3a4a7ba547c7aeb2393b94a</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=529a544f50423d30f381153b13c5bd0b0f30471b"><span class="icon"></span>529a544</a></td><td><code>Merge branch 'develop' into public/combinat/zabrocki/fixstrongtableaux/17252</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=381acd835802d712e3a4a7ba547c7aeb2393b94a"><span class="icon"></span>381acd8</a></td><td><code>fixed typos</code>
</td></tr></table>
TicketaschillingThu, 30 Oct 2014 05:21:39 GMT
https://trac.sagemath.org/ticket/17252#comment:11
https://trac.sagemath.org/ticket/17252#comment:11
<p>
Hi Mike,
</p>
<p>
Thanks for the quick fix of this issue! I rebased the branch on top of the latest development version of Sage and will run some more tests.
</p>
<p>
Best,
</p>
<p>
Anne
</p>
TicketaschillingThu, 30 Oct 2014 05:22:08 GMTpriority changed; keywords, reviewer set
https://trac.sagemath.org/ticket/17252#comment:12
https://trac.sagemath.org/ticket/17252#comment:12
<ul>
<li><strong>keywords</strong>
<em>tableaux</em> added
</li>
<li><strong>reviewer</strong>
set to <em>Anne Schilling</em>
</li>
<li><strong>priority</strong>
changed from <em>minor</em> to <em>major</em>
</li>
</ul>
TicketaschillingThu, 30 Oct 2014 06:09:50 GMTdescription changed
https://trac.sagemath.org/ticket/17252#comment:13
https://trac.sagemath.org/ticket/17252#comment:13
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/17252?action=diff&version=13">diff</a>)
</li>
</ul>
<p>
Looks good now!
</p>
<p>
Anne
</p>
TicketaschillingThu, 30 Oct 2014 06:10:01 GMTstatus changed
https://trac.sagemath.org/ticket/17252#comment:14
https://trac.sagemath.org/ticket/17252#comment:14
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
TicketzabrockiThu, 30 Oct 2014 13:21:05 GMT
https://trac.sagemath.org/ticket/17252#comment:15
https://trac.sagemath.org/ticket/17252#comment:15
<p>
Thanks for reviewing and finding the bug.
-Mike
</p>
TicketvbraunThu, 30 Oct 2014 22:28:38 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/17252#comment:16
https://trac.sagemath.org/ticket/17252#comment:16
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>public/combinat/zabrocki/fixstrongtableaux/17252</em> to <em>381acd835802d712e3a4a7ba547c7aeb2393b94a</em>
</li>
</ul>
Ticket