Implement northwest diagrams

[trevorkarn]

Implement a class for diagrams (collections of cells (i,j) indexed by the natural numbers), and a class for diagrams with the northwest property. A diagram has the northwest property if the fact that (i1, j1) and (i2,j2) are in the diagram implies that the cell (min(i1,i2), min(j1,j2)) are in the diagram.

Depends on #34339
Depends on #34343
Depends on #34345

CC: @tscrim

Component: combinatorics

Keywords: gsoc2022 northwest-diagram

Author: Trevor K. Karn

Branch/Commit: 382926c

Reviewer: Travis Scrimshaw

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

[trevorkarn]

Commit: 067c0ac

[trevorkarn]

Branch: u/tkarn/diagrams-34260

[trevorkarn]

New commits:

067c0ac

Initial commit

[sagetrac-git]

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

0f48031	Implement parent framework
a3607bb	Add parent/element framework of northwest diagrams

[sagetrac-git]

Changed commit from 067c0ac to a3607bb

[sagetrac-git]

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

cb70a0e	Add outside_corners to SkewPartition
04507c5	Clarify some of the language around corners'
9b0e5d1	Add backward_slide (and alias reverse_slide)
1842860	First draft of peelables algorithm

[sagetrac-git]

Changed commit from a3607bb to 1842860

[sagetrac-git]

Changed commit from 1842860 to 02c13a8

[sagetrac-git]

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

02c13a8

Peelable tableaux pass all tests

[sagetrac-git]

Changed commit from 02c13a8 to 6acca18

[sagetrac-git]

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

b2ebcd4	Initial commit
0b33095	Implement parent framework
f60a777	Add parent/element framework of northwest diagrams
b10eb7f	Add outside_corners to SkewPartition
3dbff65	Clarify some of the language around corners'
f705bb7	Add backward_slide (and alias reverse_slide)
0af7d20	First draft of peelables algorithm
b509204	Peelable tableaux pass all tests
6acca18	Fix bug in JDT

[sagetrac-git]

Changed commit from 6acca18 to ae3488a

[sagetrac-git]

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

0601fd2	Add outside_corners to SkewPartition
759a86b	Clarify some of the language around corners'
4fc7187	Add backward_slide (and alias reverse_slide)
8302a76	First draft of peelables algorithm
6a5ac12	Peelable tableaux pass all tests
438bbdf	Fix bug in JDT
ac4b36e	Add RotheDiagram
e4943d8	Add rothe_diagram, n_reduced_words, and Stanley symmetric function
f7fc288	Add documentation/examples
ae3488a	Add examples and documentation

[trevorkarn]

comment:8

There is currently an issue in ._test_category.

sage: from sage.combinat.diagram import Diagram
sage: D = Diagram([(0,0), (0,3)])
sage: D
[(0, 0), (0, 3)]
sage: D._test_category
<built-in method _test_category of Diagram object at 0x16d1fc4c0>
sage: D._test_category()
---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
Input In [6], in <cell line: 1>()
----> 1 D._test_category()

File ~/Applications/sage/src/sage/structure/element.pyx:722, in sage.structure.element.Element._test_category()
    720     # For usual Python classes, that should be done with
    721     # standard inheritance
--> 722     tester.assertTrue(isinstance(self, self.parent().category().element_class))
    723 else:
    724     # For extension types we just check that inheritance

File /usr/local/Cellar/[email protected]/3.9.13_1/Frameworks/Python.framework/Versions/3.9/lib/python3.9/unittest/case.py:688, in TestCase.assertTrue(self, expr, msg)
    686 if not expr:
    687     msg = self._formatMessage(msg, "%s is not true" % safe_repr(expr))
--> 688     raise self.failureException(msg)

AssertionError: False is not true

[tscrim]

comment:9

From a quick look, you are not passing a parent argument, which should be the first argument to any element __init__ method, and passing that up to Element.__init__. Mainly, these code blocks:

        ClonableArray.__init__(self, Diagrams(), cells, check=False)

        Diagram.__init__(self, cells, **kwargs)
        ClonableArray.__init__(self, NorthwestDiagrams(), cells, check=check)

I also don't like the double initialization of ClonableArray here. Diagram should properly handle everything, otherwise it is a code smell that strongly suggests they should not be subclasses (but they should be in this case; note that this is not universal).

Remove also the kwargs and make them explicit, mainly the check.

You should also use _repr_ (with 1 underscore).

[sagetrac-git]

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

942f976	PEP8 and example
ddfc6be	Fix __init__

[sagetrac-git]

Changed commit from ae3488a to ddfc6be

[trevorkarn]

comment:11

Thanks for the feedback!

Replying to @tscrim:

From a quick look, you are not passing a parent argument, which should be the first argument to any element __init__ method, and passing that up to Element.__init__. Mainly, these code blocks:

        ClonableArray.__init__(self, Diagrams(), cells, check=False)

        Diagram.__init__(self, cells, **kwargs)
        ClonableArray.__init__(self, NorthwestDiagrams(), cells, check=check)

Sorry, I'm confused. I thought that Diagrams() and NorthwestDiagrams() were those parent arguments. Am I misunderstanding what you are saying?

---

New commits:

942f976	PEP8 and example
ddfc6be	Fix __init__

---

New commits:

942f976	PEP8 and example
ddfc6be	Fix __init__

[tscrim]

comment:12

They are, but elements should take a parent argument first and pass that along. Imagine once you have NorthwestDiagrams given by some parameter. This will also fix the double initialization issue.

[trevorkarn]

comment:13

Oh! That makes sense now. It also helps with some general confusion I had about when to use __classcall_private__ and other Parent/Element confusion. Thanks!

[sagetrac-git]

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

563e542

Fix kwargs, repr, and remove double .__init__ call

[sagetrac-git]

Changed commit from ddfc6be to 563e542

[sagetrac-git]

Changed commit from 563e542 to 7308381

[sagetrac-git]

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

7308381

Fix accidental check=False

[sagetrac-git]

Changed commit from 7308381 to 2a427f6

[fchapoton]

comment:71

needs to be rebased

[sagetrac-git]

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

90dd64c	Fix pyflakes issue
5d1f758	Fix pyflakes issue
4278363	Add .from_* methods to __element_constructor__
d7c74f4	Add diagram iterator
ae1d71a	Add tests and add a catch for subclasses
217c203	PositiveIntegers -> NonNegativeIntegers
192d2e0	Add unicode/ascii art
a4a9474	Add draft of `_latex_` and fix pretty_print/ascii_art string things
740651f	Fix latex and unicode/ascii art
b3a3783	!=None -> is not None

[sagetrac-git]

Changed commit from 849c8d3 to b3a3783

[trevorkarn]

comment:73

Rebased, but now a test fails.

[tscrim]

comment:74

My guess is somewhere there is a multiplication convention issue:

sage: p = Permutation([4,5,2,3,1])
sage: W = WeylGroup(['A',4])
sage: W.from_reduced_word(p.reduced_word()).stanley_symmetric_function()
56*m[1, 1, 1, 1, 1, 1, 1, 1] + 26*m[2, 1, 1, 1, 1, 1, 1] + 12*m[2, 2, 1, 1, 1, 1]
 + 5*m[2, 2, 2, 1, 1] + 2*m[2, 2, 2, 2] + 6*m[3, 1, 1, 1, 1, 1]
 + 3*m[3, 2, 1, 1, 1] + m[3, 2, 2, 1] + m[3, 3, 1, 1]
sage: W.from_reduced_word(reversed(p.reduced_word())).stanley_symmetric_function()
56*m[1, 1, 1, 1, 1, 1, 1, 1] + 30*m[2, 1, 1, 1, 1, 1, 1] + 16*m[2, 2, 1, 1, 1, 1]
 + 9*m[2, 2, 2, 1, 1] + 6*m[2, 2, 2, 2] + 10*m[3, 1, 1, 1, 1, 1] + 5*m[3, 2, 1, 1, 1]
 + 3*m[3, 2, 2, 1] + m[3, 3, 1, 1] + m[3, 3, 2] + 2*m[4, 1, 1, 1, 1] + m[4, 2, 1, 1] + m[4, 2, 2]

A very annoying subtlety to deal with (which we can usually just hand-wave away), but we have to deal with here. Actually, I suspect the former is the "correct" output doing:

sage: P5 = Permutations(5)
sage: p = P5([4,5,2,3,1])
sage: p.stanley_symmetric_function()
RecursionError
sage: P5.options.mult = 'r2l'
sage: p.stanley_symmetric_function()
56*m[1, 1, 1, 1, 1, 1, 1, 1] + 26*m[2, 1, 1, 1, 1, 1, 1] + 12*m[2, 2, 1, 1, 1, 1]
 + 5*m[2, 2, 2, 1, 1] + 2*m[2, 2, 2, 2] + 6*m[3, 1, 1, 1, 1, 1]
 + 3*m[3, 2, 1, 1, 1] + m[3, 2, 2, 1] + m[3, 3, 1, 1]

Although annoyingly this is different from p.to_permutation_group_element().stanley_symmetric_function(). It might just be a matter of documenting what convention you use as both are "correct."

One extra thing I noticed, you can pull out the inverse here to not redo it so many times:

+    winv = w.inverse()
     cells = [c for c in cartesian_product_iterator((range(N), range(N)))
-             if c[0]+1 < w.inverse()(c[1]+1) and c[1]+1 < w(c[0]+1)]
+             if c[0]+1 < winv(c[1]+1) and c[1]+1 < w(c[0]+1)]

[sagetrac-git]

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

1ff619c	Remove SSF
965b284	Fix w-inverse

[sagetrac-git]

Changed commit from b3a3783 to 965b284

[trevorkarn]

comment:76

I realized that the Stanley symmetric function things should be on #34335 instead (where they have the correct multiplication convention) so I removed them from this ticket. I think this is ready.

[tscrim]

comment:78

Tests are passing for me, but it might be good to wait for the patchbot one more time.

[tscrim]

Changed branch from u/tkarn/diagrams-34260 to u/tscrim/diagrams-34260

[tscrim]

comment:79

I made some changes to the doc and the unicode output. If my changes are good, back to a positive review.

---

New commits:

291d799

Some last reviewer changes to improve some doc and unicode art.

[tscrim]

Changed commit from 965b284 to 291d799

[trevorkarn]

comment:80

It looks like pyflakes is raising some warnings about unused variables. I'm changing/testing those now, but your changes LGTM.

[trevorkarn]

Changed commit from 291d799 to 382926c

[trevorkarn]

New commits:

382926c

Fix unused variable

[trevorkarn]

Changed branch from u/tscrim/diagrams-34260 to u/tkarn/diagrams-34260

[trevorkarn]

comment:82

All the tests pass on my end - I'll wait for patchbot.

[tscrim]

comment:83

Green bot.

[fchapoton]

comment:84

so what is this now waiting for ?

[trevorkarn]

comment:85

Nothing. Thanks Frédéric

[vbraun]

Changed branch from u/tkarn/diagrams-34260 to 382926c