Implementation of shifted tableaux

[anneschilling]

This ticket implements a new class for shifted primed tableaux, and an A-type crystal for those objects.

CC: @tscrim @sagetrac-kbparamonov @sagetrac-hawkes @anneschilling @mantepse @AndrewAtLarge

Component: combinatorics

Keywords: shifted primed tableaux, crystals

Author: Kirill Paramonov

Branch/Commit: bf7e707

Reviewer: Anne Schilling, Travis Scrimshaw, Martin Rubey

Issue created by migration from https://trac.sagemath.org/ticket/22921

[tscrim]

comment:1

See #20041.

[anneschilling]

Description changed:

--- 
+++ 
@@ -1 +1,3 @@
-This ticket implements a new class for shifted tableaux and algorithm related to these.
+This ticket implements a new class for unimodal tableaux, signed primed tableaux, and related insertion algorithms such as Kraskiewicz insertion and mixed Haiman insertion.
+
+This ticket is related to, but different from #20041 and will build on top of it.

[fca50f62-7f78-4828-ba06-52f19fb43d4e]

Branch: public/combinat/primed_tableaux_22921

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

3043717

File shifted_tableaux.py added in combinat.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Commit: 3043717

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 3043717 to f6aa0ef

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

f6aa0ef

New functions and comments

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from f6aa0ef to d00e09b

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

d00e09b

Added proper links

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from d00e09b to 13b6c8a

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

13b6c8a

added crystal structure

[anneschilling]

comment:11

Looking at the code, I do not think it is necessary to implement a new class for StrictPartitions. You can access those using the already existing Partitions code:

sage: Partitions(7, max_slope=-1).list()
[[7], [6, 1], [5, 2], [4, 3], [4, 2, 1]]

Please also make sure that you stick to the Sage coding conventions described here ​http://doc.sagemath.org/html/en/developer/coding_basics.html

[anneschilling]

comment:12

I still get many doctest failures (here are two, but there are many more):

sage -t tableau_shifted_primed.py
**********************************************************************
File "tableau_shifted_primed.py", line 43, in sage.combinat.tableau_shifted_primed.ShiftedPrimedTableau
Failed example:
    T([[1,"2'","3'",3],[2,"3'"]])[1]
Exception raised:
    Traceback (most recent call last):
      File "/Applications/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 509, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Applications/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 872, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.combinat.tableau_shifted_primed.ShiftedPrimedTableau[1]>", line 1, in <module>
        T([[Integer(1),"2'","3'",Integer(3)],[Integer(2),"3'"]])[Integer(1)]
      File "sage/structure/parent.pyx", line 941, in sage.structure.parent.Parent.__call__ (/Applications/sage/src/build/cythonized/sage/structure/parent.c:9839)
        return mor._call_(x)
      File "sage/structure/coerce_maps.pyx", line 110, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (/Applications/sage/src/build/cythonized/sage/structure/coerce_maps.c:4895)
        raise
      File "sage/structure/coerce_maps.pyx", line 105, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (/Applications/sage/src/build/cythonized/sage/structure/coerce_maps.c:4762)
        return C._element_constructor(x)
      File "/Applications/sage/local/lib/python2.7/site-packages/sage/combinat/tableau_shifted_primed.py", line 904, in _element_constructor_
        raise ValueError("{} is not an element of {}".format(t, self))
    ValueError: [[1, "2'", "3'", 3], [2, "3'"]] is not an element of Shifted Primed tableaux of shape [4, 2]
**********************************************************************
File "tableau_shifted_primed.py", line 45, in sage.combinat.tableau_shifted_primed.ShiftedPrimedTableau
Failed example:
    t = ShiftedPrimedTableau([[1,"2p",2.5,3],[0,2,2.5]])
Exception raised:
    Traceback (most recent call last):
      File "/Applications/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 509, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Applications/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 872, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.combinat.tableau_shifted_primed.ShiftedPrimedTableau[2]>", line 1, in <module>
        t = ShiftedPrimedTableau([[Integer(1),"2p",RealNumber('2.5'),Integer(3)],[Integer(0),Integer(2),RealNumber('2.5')]])
      File "sage/misc/lazy_import.pyx", line 389, in sage.misc.lazy_import.LazyImport.__call__ (/Applications/sage/src/build/cythonized/sage/misc/lazy_import.c:4016)
        return self._get_object()(*args, **kwds)
      File "sage/misc/classcall_metaclass.pyx", line 330, in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (/Applications/sage/src/build/cythonized/sage/misc/classcall_metaclass.c:1415)
        return cls.classcall(cls, *args, **kwds)
      File "/Applications/sage/local/lib/python2.7/site-packages/sage/combinat/tableau_shifted_primed.py", line 86, in __classcall_private__
        return ShiftedPrimedTableaux(shape = shape, weight = weight)(T)
      File "sage/structure/parent.pyx", line 941, in sage.structure.parent.Parent.__call__ (/Applications/sage/src/build/cythonized/sage/structure/parent.c:9839)
        return mor._call_(x)
      File "sage/structure/coerce_maps.pyx", line 110, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (/Applications/sage/src/build/cythonized/sage/structure/coerce_maps.c:4895)
        raise
      File "sage/structure/coerce_maps.pyx", line 105, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (/Applications/sage/src/build/cythonized/sage/structure/coerce_maps.c:4762)
        return C._element_constructor(x)
      File "/Applications/sage/local/lib/python2.7/site-packages/sage/combinat/tableau_shifted_primed.py", line 1004, in _element_constructor_
        raise ValueError("{} is not an element of {}".format(t, self))
    ValueError: [[1, '2p', 2.50000000000000, 3], [0, 2, 2.50000000000000]] is not an element of Shifted Primed Tableaux of weight (1, 4, 1) and shape [4, 2]

[anneschilling]

comment:13

Here are some more trivial comments:

• you need a blank line before and after EXAMPLES::

• Returnes -> Return (several times)

• you need a blank line after the one-line description of a given method

• you need a 4-space indent of the code for each EXAMPLES:: This indent is sometimes missing.

• EXAMPE: -> EXAMPLES::

• There is still some documentation missing for some of the methods

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

5dee1d6

Fixed functions

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 13b6c8a to 5dee1d6

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 5dee1d6 to d582dcd

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

d582dcd

Added documentation, cleaned up the code

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

5bc82dc

Fixed doctests

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from d582dcd to 5bc82dc

[mantepse]

comment:17

In #23319 I have just implemented a growth diagram version of the insertion algorithm...

[fca50f62-7f78-4828-ba06-52f19fb43d4e]

Reviewer: aschilling, tscrim

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 5bc82dc to 84093c4

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

84093c4

fix minor formatting issues

[mantepse]

comment:20

It would be nice to get this in, so we can have the following from #23896

sage: G = GrowthDiagramShiftedShapes([5, 10, 8, 7, 4, 1, 2, 9, 3, 6])
sage: G.P_symbol().pp()
 1   2   3   6   9
     4   5   7
         8   10

sage: G.Q_symbol().pp()
1   2   4'  5'  6'
    3   7'  8
        9   10

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 84093c4 to 724d7b6

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

8853225	fix a bug and add more (failing) tests
995d6d6	fix final fehler, produce P_symbol as StrongTableau
1ddf882	add rank function
500e234	docfixes
7027638	doc fixes (in particular use the global reference file) and simplify defaults
a1db015	make r a class attribute and implement test for Domino as an example
1ca9e7a	Merge branch 'develop' into t/23319/growth_diagram_improvements
6b2a647	add documentation and doctests
5928543	Merge branch 'u/mantepse/growth_diagram_improvements' of git://trac.sagemath.org/sage into t/22921/public/combinat/primed_tableaux_22921
724d7b6	more trivial fixes

[mantepse]

comment:22

Oh dear, help needed. All the commits after

​84093c4 fix minor formatting issues

should go away!

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 724d7b6 to 84093c4

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

ff08b90

more trivial fixes

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 84093c4 to ff08b90

[mantepse]

comment:25

I just realised that we should have a skew version, too.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from ff08b90 to 3c84bbd

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

3c84bbd

New Sage version

[fca50f62-7f78-4828-ba06-52f19fb43d4e]

comment:27

Thanks for the minor fixes! Let me know if you have further feedback. I'd rather do a semistandard version of Haiman insertion here, after the base class is implemented.

Replying to @mantepse:

It would be nice to get this in, so we can have the following from #23896

sage: G = GrowthDiagramShiftedShapes([5, 10, 8, 7, 4, 1, 2, 9, 3, 6])
sage: G.P_symbol().pp()
 1   2   3   6   9
     4   5   7
         8   10

sage: G.Q_symbol().pp()
1   2   4'  5'  6'
    3   7'  8
        9   10

[mantepse]

comment:29

Replying to @sagetrac-kbparamonov:

Thanks for the minor fixes! Let me know if you have further feedback.

Well, the most important thing for me would be support for the skew version, and support for _ascii_art_. (In principle I think that there should be generic support for all sorts of fillings of shapes, but that's certainly not in the scope of this ticket.)

Important question: why do you use ClonableArray instead of ClonableList, as Tableau does?

I'd rather do a semistandard version of Haiman insertion here, after the base class is implemented.

As you like - maybe you could also do the skew version? You can use the growth diagram version for cross-checking the standard case - the ticket is already closed, so it will be in 8.1.beta7. The syntax has changed slightly, it is now

GrowthDiagram.rules.ShiftedShapes()([5,10,8,7,4,1,2,9,3,6])

I am too lazy to implement the semistandard version of the local rules, and I think they should be done generically anyway, via standardization and destandardization of the growth diagram.

[fca50f62-7f78-4828-ba06-52f19fb43d4e]

comment:30

Replying to @mantepse:

Well, the most important thing for me would be support for the skew version, and support for _ascii_art_. (In principle I think that there should be generic support for all sorts of fillings of shapes, but that's certainly not in the scope of this ticket.)

Got it

Important question: why do you use ClonableArray instead of ClonableList, as Tableau does?

Good point, ClonableList is more consistent.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

ef251e1

improved style and doctests

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 3c84bbd to ef251e1

[tscrim]

comment:32

Tableau probably should be using ClonableArray instead of ClonableList because it (should have) a fixed size. From the doc of structure/list_clone.pyx:

- :class:`ClonableArray` for arrays (lists of fixed length) of objects;
- :class:`ClonableList` for (resizable) lists of objects;

[mantepse]

comment:33

Replying to @tscrim:

Tableau probably should be using ClonableArray instead of ClonableList because it (should have) a fixed size.

OK, I misunderstood: apparently, size is the number of rows. So, a tableau really should be a ClonableArray of lists, right? Or should it be a ClonableArray of ClonableArrays?

[tscrim]

comment:34

ClonableArray of tuples is best so the rows cannot be modified via T[0] (a la #15862).

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from ef251e1 to 20aefa8

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

20aefa8

Added Ascii and unicode

[mantepse]

comment:36

Great! One further comment (apart from the skew thing): it might be nice to have, similar to what's provided by SkewTableau, an argument chain that takes a sequence of shapes and creates a shifted (skew) tableau. This is already implemented in #23896 (methods P_symbol and Q_symbol) for the standard case, but should be straightforward also for the (skew) semistandard case. You can simply take the code from there, I would then replace those with a call to ShiftedPrimedTableau(chain=Q_chain).

I admit that I'm not completely sure about how to do it right: in the shifted case, a chain is a sequence of strict partitions, alternating with a colour:

• colour 1 (black) - add a box on the diagonal
• colour 2 (blue) - add an ordinary box
• colour 3 (red) - add a primed box

Of course, black is redundant, so maybe you just want to have two colours...

[anneschilling]

comment:37

Hi Kirill,

Not all methods seems to have documentation, see

sage -coverage tableau_shifted_primed.py 
------------------------------------------------------------------------
SCORE tableau_shifted_primed.py: 86.8% (46 of 53)

Missing documentation:
     * line 1630: def __classcall_private__(cls, *args, **kwargs)
     * line 1660: def __init__(self, shape=[4, 2], n=2)
     * line 1669: def _repr_(self)
     * line 1678: def add_strip(sub_tab, full_tab, length)
     * line 1736: def preprocessing(T)

Missing doctests:
     * line 1243: def __init__(self, shape, max_elt)
     * line 1510: def __init__(self, weight, shape)
------------------------------------------------------------------------

[anneschilling]

comment:38

How do you actually make the crystal of shifted primed tableaux? There is no documentation given for this. Also, you want to include the crystal in the catalogue of crystals, so that it will be accessible as crystals.shifted_primed_tableaux(shape). Currently, this does not seem to be implemented.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

bf9567d

Added crystal documentation, put in the crystal catalog

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 20aefa8 to bf9567d