Opened 13 years ago

Closed 8 years ago

## #8322 closed defect (invalid)

# on sage.combinat.tableau.insert_word() , parameter left= is broken (fix provided)

Reported by: | drini | Owned by: | somebody |
---|---|---|---|

Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |

Component: | combinatorics | Keywords: | |

Cc: | Merged in: | ||

Authors: | Pedro Sanchez | Reviewers: | Josh Swanson |

Report Upstream: | N/A | Work issues: | |

Branch: | Commit: | ||

Dependencies: | Stopgaps: |

### Description

on /usr/local/sage2/local/lib/python2.6/site-packages/sage/combinat/tableau.py

at the

def insert_word(): if left: w = [i for i in reversed(w)] res = self for i in w: res = res.schensted_insert(i,left=left) return res

the left= parameter on insert word has no effect as the following code shows:

T=Tableau([]) w = [2,1,1,3,2,4] print T.insert_word(w) T=Tableau([]) print T.insert_word(w,left=True) T=Tableau([]) print T.insert_word(w,left=False)

printing

[[1, 1, 2, 4], [2, 3]] [[1, 1, 2, 4], [2, 3]] [[1, 1, 2, 4], [2, 3]]

which is the correct result of right row-insertion for Schensted's algorithm but left-insertion is broken.

The problem lies on the left=left on the inner call, which should be

**res = res.schensted_insert(i,left=False) **

The background is this (ref: William, Fulton. Young Tableaux. Cambridge University Press)

A "left" insertion a -> b -> c (starting with c) is equivalent to right insertion a <- b <- c (starting with a)

therefore the lines

if left: w = [i for i in reversed(w)]

are **correctly transforming** the left insertion into a right one by reversing the insertion order .

However, left=left is an error, shoud be left=False since it's already converted into a right insertion, and so:

setting left=True will exchange the meanings of left-right insertions, since the reversal already turned the column-insertion into row-insertion (kind of like "negative-negative" cancelling) and the result is that calling left=False on insert_word will give the left result and left=True will give the right one!!

The correct code, therefore is

def insert_word(): if left: w = [i for i in reversed(w)] res = self for i in w: res = res.schensted_insert(i,left=False) return res

which would give the correct results:

w = [2,1,1,3,2,4] T=Tableau([]); print insertar(T, w) T=Tableau([]); print insertar(T, w,left=False) T=Tableau([]); print insertar(T, w,left=True)

(insertar is an alias I made for testing) and would then print:

[[1, 1, 2, 4], [2, 3]] [[1, 1, 2, 4], [2, 3]] [[1, 1, 2], [2, 3], [4]]

default call : CORRECT (right insertion)

explicit right insertion : CORRECT

explicit left insertion : CORRECT

whereas setting res = res.schensted_insert(i,left=True) would give

[[1, 1, 2], [2, 3], [4]] [[1, 1, 2], [2, 3], [4]] [[1, 1, 2, 4], [2, 3]]

default call : left-insertion WRONG!

explicit right insertion : WRONG! (it gave the left one)

explicit left insertion : WRONG! (it gave the right one)

Notice also that setting left=True affects the default case.

**Conclusion**

res = res.schensted_insert(i,left=left)

should be changed to

res = res.schensted_insert(i,left=False)

This is first bug I send, so I apologize if I don't fill correctly the values below

### Change History (9)

### comment:1 Changed 13 years ago by

Authors: | → Pedro Sanchez |
---|

### comment:2 Changed 12 years ago by

### comment:3 Changed 9 years ago by

Milestone: | sage-5.11 → sage-5.12 |
---|

### comment:4 Changed 9 years ago by

Milestone: | sage-6.1 → sage-6.2 |
---|

### comment:5 Changed 9 years ago by

Milestone: | sage-6.2 → sage-6.3 |
---|

### comment:6 Changed 8 years ago by

Milestone: | sage-6.3 → sage-6.4 |
---|

### comment:7 Changed 8 years ago by

Milestone: | sage-6.4 → sage-duplicate/invalid/wontfix |
---|---|

Status: | new → needs_review |

### comment:8 Changed 8 years ago by

Reviewers: | → Josh Swanson |
---|---|

Status: | needs_review → positive_review |

### comment:9 Changed 8 years ago by

Resolution: | → invalid |
---|---|

Status: | positive_review → closed |

**Note:**See TracTickets for help on using tickets.

The left=True parameter does have an effect. One can compare:

The latter is returning the result of Schensted inserting the concatenation of the words w and the reading word of t (in that order). This operation is used in the code for katabolism (and possibly elsewhere), and reflects multiplication in the plactic monoid.