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: sage-6.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 aschilling)

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 zabrocki

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

New commits:

8d76e45initial fix by adding extra condition to check
a48b105cleaned up the conditions being checked, added test for error

comment:2 Changed 4 years ago by zabrocki

  • Status changed from new to needs_review

comment:3 Changed 4 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 4 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 4 years ago by git

  • Commit changed from a48b105bfb91aaeacac7cd6606b57aa585f3bc23 to 6b696d93d08d273a0414586a2993bfffd909aa83

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

6b696d9made the function recursive and this seems to solve the problem : TODO remove #print statements

comment:6 Changed 4 years ago by git

  • Commit changed from 6b696d93d08d273a0414586a2993bfffd909aa83 to 6b738d2d2abfded2ae67258008d29c6499fa54a2

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

6b738d2added the problem tests, deleted the #print statements, fixed a problem by returning None

comment:7 Changed 4 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 4 years ago by git

  • Commit changed from 6b738d2d2abfded2ae67258008d29c6499fa54a2 to 3ee5f3639269ac461dc29f2d300d8a40a2ad48af

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

3ee5f36change to .to_transposition_sequence() so that the standard marked tableau is used

comment:9 Changed 4 years ago by tscrim

  • Cc tscrim added

comment:10 follow-up: Changed 4 years ago by git

  • Commit changed from 3ee5f3639269ac461dc29f2d300d8a40a2ad48af to 381acd835802d712e3a4a7ba547c7aeb2393b94a

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

529a544Merge branch 'develop' into public/combinat/zabrocki/fixstrongtableaux/17252
381acd8fixed typos

comment:11 in reply to: ↑ 10 Changed 4 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 4 years ago by aschilling

  • Keywords tableaux added
  • Priority changed from minor to major
  • Reviewers set to Anne Schilling

comment:13 Changed 4 years ago by aschilling

  • Description modified (diff)

Looks good now!

Anne

comment:14 Changed 4 years ago by aschilling

  • Status changed from needs_review to positive_review

comment:15 Changed 4 years ago by zabrocki

Thanks for reviewing and finding the bug. -Mike

comment:16 Changed 4 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.