Opened 5 years ago

Closed 5 years ago

# bug fix in StrongTableaux.marked_CST_to_transposition_sequence

Reported by: Owned by: zabrocki major sage-6.4 combinatorics tableaux aschilling, tscrim Mike Zabrocki Anne Schilling N/A 381acd8 (Commits) 381acd835802d712e3a4a7ba547c7aeb2393b94a

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:1 Changed 5 years ago by zabrocki

• Branch set to public/combinat/zabrocki/fixstrongtableaux/17252
• Commit set to a48b105bfb91aaeacac7cd6606b57aa585f3bc23

New commits:

 ​8d76e45 initial fix by adding extra condition to check ​a48b105 cleaned up the conditions being checked, added test for error

### comment:2 Changed 5 years ago by zabrocki

• Status changed from new to needs_review

### comment:3 Changed 5 years ago by zabrocki

• 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 5 years ago by zabrocki

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 5 years ago by git

• 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 5 years ago by git

• 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 5 years ago by zabrocki

• 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 5 years ago by git

• 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:10 follow-up: ↓ 11 Changed 5 years ago by git

• Commit changed from 3ee5f3639269ac461dc29f2d300d8a40a2ad48af to 381acd835802d712e3a4a7ba547c7aeb2393b94a

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

 ​529a544 Merge branch 'develop' into public/combinat/zabrocki/fixstrongtableaux/17252 ​381acd8 fixed typos

### comment:11 in reply to: ↑ 10 Changed 5 years ago by aschilling

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 5 years ago by aschilling

• Priority changed from minor to major
• Reviewers set to Anne Schilling

### comment:13 Changed 5 years ago by aschilling

• Description modified (diff)

Looks good now!

Anne

### comment:14 Changed 5 years ago by aschilling

• Status changed from needs_review to positive_review

### comment:15 Changed 5 years ago by zabrocki

Thanks for reviewing and finding the bug. -Mike

### comment:16 Changed 5 years ago by vbraun

• Branch changed from public/combinat/zabrocki/fixstrongtableaux/17252 to 381acd835802d712e3a4a7ba547c7aeb2393b94a
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.