Opened 4 years ago
Closed 4 years ago
#17252 closed defect (fixed)
bug fix in StrongTableaux.marked_CST_to_transposition_sequence
Reported by:  zabrocki  Owned by:  

Priority:  major  Milestone:  sage6.4 
Component:  combinatorics  Keywords:  tableaux 
Cc:  aschilling, tscrim  Merged in:  
Authors:  Mike Zabrocki  Reviewers:  Anne Schilling 
Report Upstream:  N/A  Work issues:  
Branch:  381acd8 (Commits)  Commit:  381acd835802d712e3a4a7ba547c7aeb2393b94a 
Dependencies:  Stopgaps: 
Description (last modified by )
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.
Change History (16)
comment:1 Changed 4 years ago by
 Branch set to public/combinat/zabrocki/fixstrongtableaux/17252
 Commit set to a48b105bfb91aaeacac7cd6606b57aa585f3bc23
comment:2 Changed 4 years ago by
 Status changed from new to needs_review
comment:3 Changed 4 years ago by
 Status changed from needs_review to needs_work
More testing shows that checking the conditions in the ribbon is not sufficient.
Example:
Let
T = [[1, 2, 5, 5, 5, 5, 5], [3, 4, 5, 5], [5]]
if you apply the transposition t_{6,7} to T then the shape will be [6,3]
leaving
[[1, 2, 5, 5, 5, 5], [3, 4, 5]]
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 [5,2,1]
leaving
[[1, 2, 5, 5, 5], [3, 4], [5]]
The markings in both cases are correct, but the right transposition to apply is the t_{5,7}.
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.
comment:4 Changed 4 years ago by
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.
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.
comment:5 Changed 4 years ago by
 Commit changed from a48b105bfb91aaeacac7cd6606b57aa585f3bc23 to 6b696d93d08d273a0414586a2993bfffd909aa83
Branch pushed to git repo; I updated commit sha1. New commits:
6b696d9  made the function recursive and this seems to solve the problem : TODO remove #print statements

comment:6 Changed 4 years ago by
 Commit changed from 6b696d93d08d273a0414586a2993bfffd909aa83 to 6b738d2d2abfded2ae67258008d29c6499fa54a2
Branch pushed to git repo; I updated commit sha1. New commits:
6b738d2  added the problem tests, deleted the #print statements, fixed a problem by returning None

comment:7 Changed 4 years ago by
 Status changed from needs_work to needs_review
I've been testing these functions and don't see any obvious change in speed, and this does seem to completely fix the bug.
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).
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.
comment:8 Changed 4 years ago by
 Commit changed from 6b738d2d2abfded2ae67258008d29c6499fa54a2 to 3ee5f3639269ac461dc29f2d300d8a40a2ad48af
Branch pushed to git repo; I updated commit sha1. New commits:
3ee5f36  change to .to_transposition_sequence() so that the standard marked tableau is used

comment:9 Changed 4 years ago by
 Cc tscrim added
comment:10 followup: ↓ 11 Changed 4 years ago by
 Commit changed from 3ee5f3639269ac461dc29f2d300d8a40a2ad48af to 381acd835802d712e3a4a7ba547c7aeb2393b94a
comment:11 in reply to: ↑ 10 Changed 4 years ago by
Hi Mike,
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.
Best,
Anne
comment:12 Changed 4 years ago by
 Keywords tableaux added
 Priority changed from minor to major
 Reviewers set to Anne Schilling
comment:14 Changed 4 years ago by
 Status changed from needs_review to positive_review
comment:15 Changed 4 years ago by
Thanks for reviewing and finding the bug. Mike
comment:16 Changed 4 years ago by
 Branch changed from public/combinat/zabrocki/fixstrongtableaux/17252 to 381acd835802d712e3a4a7ba547c7aeb2393b94a
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
initial fix by adding extra condition to check
cleaned up the conditions being checked, added test for error