Opened 13 years ago

Closed 8 years ago

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

Reported by: Owned by: drini somebody major sage-duplicate/invalid/wontfix combinatorics Pedro Sanchez Josh Swanson N/A

### 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

### comment:1 Changed 13 years ago by drini

Authors: → Pedro Sanchez

### comment:2 Changed 12 years ago by jbandlow

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

```    sage: t = Tableau([[2, 3], [3]])
sage: w = [1, 1, 3, 3]
sage: t.insert_word(w)
[[1, 1, 3, 3], [2, 3], [3]]
sage: t.insert_word(w, left=True)
[[1, 1, 2, 3, 3, 3], [3]]
```

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.

### comment:3 Changed 9 years ago by jdemeyer

Milestone: sage-5.11 → sage-5.12

### comment:4 Changed 9 years ago by vbraun_spam

Milestone: sage-6.1 → sage-6.2

### comment:5 Changed 9 years ago by vbraun_spam

Milestone: sage-6.2 → sage-6.3

### comment:6 Changed 8 years ago by vbraun_spam

Milestone: sage-6.3 → sage-6.4

### comment:7 Changed 8 years ago by jpswanson

Milestone: sage-6.4 → sage-duplicate/invalid/wontfix new → needs_review

### comment:8 Changed 8 years ago by jpswanson

Reviewers: → Josh Swanson needs_review → positive_review

### comment:9 Changed 8 years ago by vbraun

Resolution: → invalid positive_review → closed
Note: See TracTickets for help on using tickets.