Fomin's growth diagrams and Schensted-like algorithms

[mantepse]

Depends on #21609

CC: @sagetrac-sage-combinat @darijgr @tscrim @kevindilks @sagetrac-etzanaki @VivianePons

Component: combinatorics

Keywords: days82

Author: Martin Rubey

Branch: 0b566fa

Reviewer: Frédéric Chapoton, Travis Scrimshaw

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

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

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

5099858

make the patchbot happy and indeed I discovered a bug in the _backward_rule of Burge

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

Changed commit from c0ffb06 to 5099858

[mantepse]

comment:36

Questions for the reviewer...

Background:

The main object underlying the algorithm is the "dual graded graph", that is, a pair of graded digraphs on the same set of vertices, with the same rank function, satisfying some relations (mainly: DU = UD + rI, where U means "up" in one graph and D is down in the other graph).

However, the code is intended mostly for experimenting with growth diagrams. In particular, it should be as easy as possible to define new rules. Thus it is important that nothing is enforced, unless needed. For example, it is perfectly OK to define only _forward_rule, and leave all of _rank_function, _covers_1 , _covers_2, _zero and _backward_rule undefined. The only consequence should be that in this case some features will raise an error.

Moreover, I believe that the RSK growth diagrams aren't growth diagrams in the strict sense of the word: I think it makes more sense to say that they are destandardizations of growth diagrams on Young's lattice. Thus, I certainly do not want to be strict.

So, all of what follows is probably cosmetics.

1) should _rank_function, _covers_1 , _covers_2, _zero, _forward_rule and _backward_rule be staticmethods instead of attributes?

2) if these become methods, I think we should make them public, too, right?

3) it would be nice to be able to define a growth diagram completely interactively, by just specifying, for example, the forward rule. I tried:

sage: from growth import GrowthDiagramOnPartitions
sage: class MyG(GrowthDiagramOnPartitions):
....:     @staticmethod
....:     def _forward_rule(a, b, c, d):
....:         pass
....:     
sage: MyG._forward_rule = GrowthDiagramDomino._forward_rule
sage: MyG([1])
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
TypeError: _forward_rule() takes exactly 4 arguments (5 given)

so this doesn't work. Should we have a function growth_diagram(forward_rule=None, backward_rule=None) that returns a class? Or is there a more practical way to interactively redefine methods of a class?

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

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

1608624

fix typo in doc

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

Changed commit from 5099858 to 1608624

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

Changed commit from 1608624 to 71daf56

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

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

71daf56

fix corner cases

[fchapoton]

comment:39

sage -t --long src/sage/combinat/growth.py  # 16 doctests failed

[mantepse]

comment:40

Replying to @fchapoton:

sage -t --long src/sage/combinat/growth.py  # 16 doctests failed

Did you apply #21609 first?

[fchapoton]

comment:41

This is coming from a patchbot, see there. In principle, it applies the dependencies, I think.

[mantepse]

comment:42

Replying to @fchapoton:

This is coming from a patchbot, see there. In principle, it applies the dependencies, I think.

Well, the error message is precisely the one to be expected if the dependency is not applied. How can I check?

[fchapoton]

comment:43

Look at

https://patchbot.sagemath.org/log/21594/Ubuntu/14.04/x86_64/3.16.0-30-generic/petitbonum/2016-10-04%2016:59:58?short

Do you say that these errors are the ones coming from not applying the dependency ?

[mantepse]

comment:44

Replying to @fchapoton:

Look at

https://patchbot.sagemath.org/log/21594/Ubuntu/14.04/x86_64/3.16.0-30-generic/petitbonum/2016-10-04%2016:59:58?short

Do you say that these errors are the ones coming from not applying the dependency ?

Exactly.

[fchapoton]

comment:45

ok, then the bot is not pulling the dependency. I have no time to solve that.

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

Changed commit from 71daf56 to 294d5f8

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

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

294d5f8

implement equality

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

Changed commit from 294d5f8 to 8d7f857

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

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

8d7f857

fix grammar in documentation

[darijgr]

Changed branch from u/mantepse/growth_diagrams to public/ticket/21594

[darijgr]

Changed commit from 8d7f857 to 8598267

[darijgr]

comment:49

This looks like a really useful update. But the documentation is rather vague about how the various growth rules are defined :/ Martin, is there a single source whose notations you are following, or is it patchwork? Would you consider perhaps writing a mathematical exposition along with this patch? To me it's not immediately obvious even how your RSK-growth is defined. There are two ways to define growth rules for (semistandard) RSK: Either you work in Young's lattice, with only 0's and 1's in cells, after standardizing your two words into two permutations. Or you work in the directed graph whose vertices correspond to partitions and whose edges correspond to horizontal strips (of any length), and the cells can contain any nonnegative integers; the growth rule is a discrete analogue of the octahedron recurrence. Which of these two are you using?

[darijgr]

comment:50

PS. Seems like my commit hasn't been shown:

https://github.com/sagemath/sagetrac-mirror/commits/85982673ab2490dd6b845a90051d189c4140aa1b

[mantepse]

comment:51

Dear Darij!

Many thanks for your encouragement and the improvements of the documentation, especially for the x's!

I do not know of a single source containing all the known rules, the references are what I accumulated over the years. In fact, I'm quite sure I'm missing some.

However, for each rule I implemented, I gave a reference - as precisely as the article allows - in the corresponding methods _forward_rule and _backward_rule.

Replying to @darijgr:

There are two ways to define growth rules for (semistandard) RSK: Either you work in Young's lattice, with only 0's and 1's in cells, after standardizing your two words into two permutations. Or you work in the directed graph whose vertices correspond to partitions and whose edges correspond to horizontal strips (of any length), and the cells can contain any nonnegative integers; the growth rule is a discrete analogue of the octahedron recurrence. Which of these two are you using?

(That's a nice way to learn new stuff :-) I admit, I just implemented the rules (long ago, in 2008 or so) without worrying too much on the underlying dual graded graphs. In any case, as far as I can see the notion of dual graded graphs is too restrictive for RSK. So, what I assumed is that the growth rules from Christian's paper simply "destandardize" each entry of the matrix.

Is http://web.mit.edu/~shopkins/docs/rsk.pdf what I should be reading? I'm keen to learn more about that.

To clarify: with 'make semistandard extension generic' I meant that it might be good to have a procedure that standardizes the filling (in one of the 4 possible ways), and then applies the rules. A horizontal strip is then a list of vertices. In the RSK case, it is sufficient to remember the last shape of the horizontal strip, but I did not check under which conditions precisely this is true in the general case.

[mantepse]

comment:52

I just noticed that doing GrowthDiagramRSK? is not all that helpful, it only displays

   A class modelling Robinson-Schensted-Knuth insertion.

   EXAMPLES:

      sage: pi = Permutation([2,3,6,1,4,5])
      sage: G = GrowthDiagramRSK(pi)
      sage: G.P_symbol(), G.Q_symbol()
      ([[1, 3, 4, 5], [2, 6]], [[1, 2, 3, 6], [4, 5]])
      sage: RSK(pi)
      [[[1, 3, 4, 5], [2, 6]], [[1, 2, 3, 6], [4, 5]]]

which should not come as a surprise, but it did. Somehow I thought that the parent's documentation would be included...

(besides: instead some documentation for LazyImport is displayed, three times in fact, which is annoying and stupid)

So, what should I do to make sage display the documentation of the parent class GrowthDiagram? I certainly do not want to duplicate it in every subclass, it is always the same and rather long! automethod?

[fchapoton]

comment:53

from patchbot report:

please use python3-compatible syntax for print, namely print("stuff")

++                print shape1, shape2, shape3
++                print shape1.parent(), shape2.parent(), shape3.parent()
++                print shape1 == shape2
++                print shape2 == shape3
+python2-only print syntax inserted on 4 non-empty lines

and please do not use iteritems but items:

++        F = {(j,i): v for (i,j),v in self._filling.iteritems()}
++        F = {(max_row-i,max_col-j): v for (i,j),v in self._filling.iteritems()}
++            for ((i,j), v) in self._filling.iteritems():
++            for ((i,j), v) in sorted(self._filling.iteritems()):
++                    for (i, row) in filling.iteritems():
++                        for (j, v) in row.iteritems():
++                    F = {(i,j): v for ((i,j), v) in filling.iteritems()
+Python 3 incompatible code inserted on 8 non-empty lines

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

Changed commit from 8598267 to cdab727

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

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

cdab727

iteritems -> items, remove leftover print's

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

Changed commit from cdab727 to cd44d5e

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

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

cd44d5e

make documentation of `__init__` generic

[mantepse]

comment:56

One aestetic problem I still have is that

sage: GrowthDiagramRSK?

does not show the docstring of the __init__ method, because it is imported lazily. Doing

sage: from sage.combinat.growth import *

fixes this, but surely, this is not the way things ought to be?

[fchapoton]

comment:58

and do not use "bla.itervalues()" but

from six import itervalues

itervalues(bla)

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

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

1f7a19f

fix python 3 incompatibility concerning itervalues

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

Changed commit from cd44d5e to 1f7a19f

[mantepse]

comment:60

Any chance that this get's a review? Would be great...

[2bb26a75-819d-4439-bed5-64be5ed4fbe1]

comment:61

We're on it. We're quite new with this (this is our first review) but we're willing to read and test and comment! (I'm doing this with @sagetrac-etzanaki )

[2bb26a75-819d-4439-bed5-64be5ed4fbe1]

Changed keywords from none to days82

[fchapoton]

comment:65

+Missing doctests in combinat/growth.py: 35 / 40 = 87%

[mantepse]

comment:66

Replying to @fchapoton:

+Missing doctests in combinat/growth.py: 35 / 40 = 87%

I think they are not really missing, it's a misfeature of the coverage tool:

Missing doctests:
     * line 208: def __init__(self, filling=None, shape=None, labels=None)

This is the init of an abstract class.

Missing documentation:
     * line 1014: def __init__(self, filling=None, shape=None, labels=None)
     * line 1165: def __init__(self, filling=None, shape=None, labels=None)
     * line 1411: def __init__(self, filling=None, shape=None, labels=None)
     * line 1554: def __init__(self, filling=None, shape=None, labels=None)

These get their documentation set explicitely in the following lines.

[mantepse]

comment:67

ping?

[fchapoton]

comment:68

could you do one last thing:

-   arXiv:0705.2689 (2007)
+   :arxiv:`0705.2689` (2007)

then you can set to positive on my behalf.

[fchapoton]

Reviewer: Frédéric Chapoton

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

Changed commit from 1f7a19f to 0b566fa

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

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

0b566fa

format arxiv link correctly

[tscrim]

Changed reviewer from Frédéric Chapoton to Frédéric Chapoton, Travis Scrimshaw

[vbraun]

Changed branch from public/ticket/21594 to 0b566fa

[jdemeyer]

Changed commit from 0b566fa to none

[jdemeyer]

comment:73

This is not valid Python 3:

lambda (a,b): True

This should have been written as

lamdba ab: True

[mantepse]

comment:74

Thanks! I'm adding a fix to #22356. (currently recompiling)

[vbraun]

comment:75

Should be fixed in #22357 or a separate ticket...