#17252: bug fix in StrongTableaux.marked_CST_to_transposition_sequence
-------------------------------------+-------------------------------------
Reporter: zabrocki | Owner:
Type: defect | Status: needs_review
Priority: major | Milestone: sage-6.4
Component: combinatorics | Resolution:
Keywords: tableaux | Merged in:
Authors: Mike Zabrocki | Reviewers: Anne Schilling
Report Upstream: N/A | Work issues:
Branch: | Commit:
public/combinat/zabrocki/fixstrongtableaux/17252|
381acd835802d712e3a4a7ba547c7aeb2393b94a
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Old description:
> Anne Schilling pointed out the following error in the algorithm to
> convert a strong marked column strict tableau to a sequence of
> transpositions:
> {{{
> 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]]
> }}}
> however the answer should be `[[4,5],[3,4],[2,3],[1,2],[-1,0],[0,1]]` 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.
>
> 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.
>
> It looks like there are a couple of ways of catching this condition. It
> might be sufficient to check that applying the transposition t_{2,4} is
> not valid (because it really should be applying t_{-2,0} instead). That
> fix might or might not be sufficient (and a counterexample will be
> difficult to identify). To be more thorough, I will verify that if
> t_{ij} decreases the length of the core by 1, then the labels of the
> cells in range(i,j) that are removed include exactly one negative label.
New description:
Anne Schilling pointed out the following error in the algorithm to convert
a strong marked column strict tableau to a sequence of transpositions:
{{{
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]]
}}}
however the answer should be `[[4,5],[3,4],[2,3],[1,2],[-1,0],[0,1]]` 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.
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.
The fix was to implement the method `to_transposition_sequence`
recursively by checking that the result of applying `t_{i,j}` can reduced
to the empty core.
--
Comment (by aschilling):
Looks good now!
Anne
--
Ticket URL: <http://trac.sagemath.org/ticket/17252#comment:13>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
