Fully-commutative stable Grothendieck crystal

[sagetrac-wpoh]

Implementation of the crystal on fully-commutative decreasing factorizations in the 0-Hecke monoid. See https://arxiv.org/abs/1911.08732.

CC: @anneschilling @sagetrac-jppan @tscrim

Component: combinatorics

Keywords: crystal

Author: Jianping Pan, Wencin Poh, Anne Schilling

Branch/Commit: d6bfcd2

Reviewer: Travis Scrimshaw

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

[sagetrac-wpoh]

Branch: public/combinat/fc_stable_Grothendieck_crystal-30461

[sagetrac-wpoh]

Commit: 947ba35

[sagetrac-wpoh]

New commits:

947ba35

Add initial code

[sagetrac-git]

Changed commit from 947ba35 to 7eaf24d

[sagetrac-git]

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

7eaf24d

fixes to docs and missing attributes

[sagetrac-git]

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

1b433d5	Update documentation for Parent class
5dcfd53	Update documentation for DecreasingHeckeFactorization class
504dc16	Update documentation for Element class

[sagetrac-git]

Changed commit from 7eaf24d to 504dc16

[sagetrac-git]

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

83ba12f	Add FullyCommutativeStableGrothendieck to namespace
0bd15e5	Update documentation for helper functions
d0f2268	Add reference

[sagetrac-git]

Changed commit from 504dc16 to d0f2268

[sagetrac-git]

Changed commit from d0f2268 to 855037c

[sagetrac-git]

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

855037c

white spaces and other doc fixes

[sagetrac-git]

Changed commit from 855037c to b4a9a3d

[sagetrac-git]

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

b4a9a3d

Support (skew) shapes for Parent class

[sagetrac-git]

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

8cb5527

Minor documentation edits

[sagetrac-git]

Changed commit from b4a9a3d to 8cb5527

[sagetrac-git]

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

51104ee

merged with develop

[sagetrac-git]

Changed commit from 8cb5527 to 51104ee

[sagetrac-git]

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

bb65b4c

fixed doc tests and .m->.factors

[sagetrac-git]

Changed commit from 51104ee to bb65b4c

[sagetrac-git]

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

e86e6ea

more intuitive names

[sagetrac-git]

Changed commit from bb65b4c to e86e6ea

[sagetrac-git]

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

8e6f215

changed input of crystal to symmetric group elements

[sagetrac-git]

Changed commit from e86e6ea to 8e6f215

[fchapoton]

comment:13

Samll remarks.

Avoid having only TESTS:: in any non-underscored method, because the doc will be empty.

This

w.reduced_word()==[]

could be

not w.reduced_word()

which is faster.

+    Lists all words

should be

+    List all words

+    while len(queue) > 0:

could be

while queue:

[sagetrac-git]

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

6c66e7b

turn TESTS in module_generators to EXAMPELS; small edits to chapoton's remarks

[sagetrac-git]

Changed commit from bc82786 to daa7e1c

[tscrim]

comment:18

Looks good. Thank you for this addition.

Some additional comments to Frédéric's:

fully_commutative_stable_grothendieck.py is missing the file header information (module-level docstring, copyright, etc.).

You could have DecreasingHeckeFactorization inherit from SageObject (maybe tuple). Also, the inequality probably won't work (perhaps even some of the other inequalities). Using the _richcmp_ (there is a decorator to add this) would simplify this.

In the __repr__, why do you do the list cast here: repr(list(factor))[1:-1]?

Do you really expect this:

            if not isinstance(parent, FullyCommutativeStableGrothendieckCrystal):
                raise ValueError("parent should be an instance of FullyCommutativeStableGrothendieckCrystal")

It seems like it would be mostly useless.

It would be good to avoid going through the coercion framework and element constructor and just directly create the element:

-self.parent()(s)
+P = self.parent()
+P.element_class(P, s)

This is good for speed.

Error messages should start with a lowercase:

-raise ValueError("Each nonempty factor should be a strictly decreasing sequence")
+raise ValueError("each nonempty factor should be a strictly decreasing sequence")

This is a Python convention that we try to follow.

You don't need the list here (I think it is actually slightly slower):

-m = max([cell[0] for cell in cells])+1
+m = max(cell[0] for cell in cells) + 1

(and in similar other places).

-for i in range(m)[::-1]:
+for i in range(m-1,-1,-1):

I believe you can do this:

-if p not in Permutations(avoiding=[3,2,1]):
+if p.has_pattern([3,2,1]):

to avoid the transient parent (and some extra unnecessary containment checks).

-if m == None or (len(_jumps(w))<=m-1):
+if m is None or len(_jumps(w)) <= m-1:

I think it would be good to avoid creating the tableau and then its conjugate in _is_valid_column_word:

            T = Tableau(L)
            return T.conjugate().is_semistandard()

I would just go through and check everything directly in L.

[sagetrac-git]

Changed commit from daa7e1c to 21e0fc6

[sagetrac-git]

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

21e0fc6

fix coding style from tscrim's remark

[tscrim]

comment:20

This can be simplified:

-            for i in range(len(L)-1):
-                for j in range(len(L[i+1])):
-                    if L[i+1][j]<L[i][j]:
-                        return False
-            return True
+            return not any(L[i+1][j] < L[i][j] for i in range(len(L)-1)
+                           for j in range(len(L[i+1])))

or

+            return all(L[i+1][j] >= L[i][j] for i in range(len(L)-1)
+                       for j in range(len(L[i+1])))

(Interestingly enough the latter is actually faster.)

[sagetrac-git]

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

2f035b2	Add heading
9da5f27	Merge branch 'public/combinat/fc_stable_Grothendieck_crystal-30461' of git://trac.sagemath.org/sage into t/30461/public/combinat/fc_stable_Grothendieck_crystal-30461
7cfec2e	Address the rest of tscrim's comments

[sagetrac-git]

Changed commit from 21e0fc6 to 7cfec2e

[sagetrac-wpoh]

comment:22

Thanks a lot for looking through the code, Travis. Appreciate the suggestions on syntax, speedups, SageMath-specific infrastructure, etc.

Replying to @tscrim:

You could have DecreasingHeckeFactorization inherit from SageObject (maybe tuple). Also, the inequality probably won't work (perhaps even some of the other inequalities). Using the _richcmp_ (there is a decorator to add this) would simplify this.

Thank you for the suggestions. I used the following guide for __richcmp__, do correct me if the syntax does not look right:
https://doc.sagemath.org/html/en/reference/structure/sage/structure/richcmp.html

In the __repr__, why do you do the list cast here: repr(list(factor))[1:-1]?

It was to have the __repr__ print
()(2, 1)(2)()(2)
rather than
()(2, 1)(2,)()(2,)
for factors with single values. That behavior has been changed now. I'm maintaining the list casting for the _latex_ method though as it looks prettier. =)

Do you really expect this:

            if not isinstance(parent, FullyCommutativeStableGrothendieckCrystal):
                raise ValueError("parent should be an instance of FullyCommutativeStableGrothendieckCrystal")

It seems like it would be mostly useless.

No, so this has been removed.

[tscrim]

comment:23

Replying to @sagetrac-wpoh:

Thanks a lot for looking through the code, Travis. Appreciate the suggestions on syntax, speedups, SageMath-specific infrastructure, etc.

Thank you for your changes.

Replying to @tscrim:

You could have DecreasingHeckeFactorization inherit from SageObject (maybe tuple). Also, the inequality probably won't work (perhaps even some of the other inequalities). Using the _richcmp_ (there is a decorator to add this) would simplify this.

Thank you for the suggestions. I used the following guide for __richcmp__, do correct me if the syntax does not look right:
https://doc.sagemath.org/html/en/reference/structure/sage/structure/richcmp.html

Looks good. Thanks. Can you add a test showing that the != works as expected?

In the __repr__, why do you do the list cast here: repr(list(factor))[1:-1]?

It was to have the __repr__ print
()(2, 1)(2)()(2)
rather than
()(2, 1)(2,)()(2,)
for factors with single values. That behavior has been changed now. I'm maintaining the list casting for the _latex_ method though as it looks prettier. =)

That is a good point; I forgot about the singletons. For the __repr__ it would make sense to do it like how you had before. Also, since DecreasingHeckeFactorization now inherits from SageObject, you should rename __repr__ -> _repr_.

I have a few more additional comments:

-return tuple(len(l) for l in self.value)[::-1]
+return tuple([len(l) for l in reversed(self.value)])

Yes, having the list here is strangely faster.

-if len(factor)>0:
+if factor:

Instead of using both Partition, Partitions, you can just use the global parent of all partitions _Partitions. Also, I thought SkewPartition would parse its inputs into a pair of partitions?

This is strange to me:

class Element(DecreasingHeckeFactorization, ElementWrapper):

Why inherit from both? Why not just wrap the DecreasingHeckeFactorization or inherit from Element instead of ElementWrapper since I believe the wrapping is basically done by DecreasingHeckeFactorization.

[sagetrac-git]

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

d10f11f	Add crystal to module_list
fce948d	Address further comments from Travis

[sagetrac-git]

Changed commit from 7cfec2e to fce948d

[sagetrac-wpoh]

comment:25

Thank you for the further comments. I've pushed all the changes according to the previous suggestions, except for the one on the Element class (see below).

Replying to @tscrim:

Replying to @tscrim:

You could have DecreasingHeckeFactorization inherit from SageObject (maybe tuple). Also, the inequality probably won't work (perhaps even some of the other inequalities). Using the _richcmp_ (there is a decorator to add this) would simplify this.

Thank you for the suggestions. I used the following guide for __richcmp__, do correct me if the syntax does not look right:
https://doc.sagemath.org/html/en/reference/structure/sage/structure/richcmp.html

Looks good. Thanks. Can you add a test showing that the != works as expected?

I've added a test in the __init__ for DecreasingHeckeFactorization.

Instead of using both Partition, Partitions, you can just use the global parent of all partitions _Partitions. Also, I thought SkewPartition would parse its inputs into a pair of partitions?

Both remarks make sense. The code looks better now.

This is strange to me:

class Element(DecreasingHeckeFactorization, ElementWrapper):

Why inherit from both? Why not just wrap the DecreasingHeckeFactorization or inherit from Element instead of ElementWrapper since I believe the wrapping is basically done by DecreasingHeckeFactorization.

The code was more or less adopted from affine_factorization.py in the combinat/crystal folder. The original intention is to inherit the methods (eg. weight) that come with DecreasingHeckeFactorization while having access to parent from ElementWrapper.

I am not so familiar with the difference between ElementWrapper and Element, but trying
for example

class Element(ElementWrapper):
    def __init__()
        # Do something to validate and process t into 
        # an instance of DecreasingHeckeFactorization u
        ElementWrapper.__init__(self, parent, u)

and making minor changes in e, f, bracketing in the same class somehow gives the following unexpected behavior for weight:

sage: S = SymmetricGroup(3+1)
sage: w = S.from_reduced_word([1, 3, 2])
sage: B = crystals.FullyCommutativeStableGrothendieck(w, 3, 2)
sage: h = B([[3, 1], [3], [3, 2]]); h
(3, 1)(3)(3, 2)
sage: h.weight()
(0, -1, 0) # expected (2, 1, 2)

[tscrim]

comment:26

Replying to @sagetrac-wpoh:

Thank you for the further comments. I've pushed all the changes according to the previous suggestions, except for the one on the Element class (see below).

Thank you.

This is strange to me:

class Element(DecreasingHeckeFactorization, ElementWrapper):

Why inherit from both? Why not just wrap the DecreasingHeckeFactorization or inherit from Element instead of ElementWrapper since I believe the wrapping is basically done by DecreasingHeckeFactorization.

The code was more or less adopted from affine_factorization.py in the combinat/crystal folder. The original intention is to inherit the methods (eg. weight) that come with DecreasingHeckeFactorization while having access to parent from ElementWrapper.

I am not so familiar with the difference between ElementWrapper and Element, but trying
for example

class Element(ElementWrapper):
    def __init__()
        # Do something to validate and process t into 
        # an instance of DecreasingHeckeFactorization u
        ElementWrapper.__init__(self, parent, u)

and making minor changes in e, f, bracketing in the same class somehow gives the following unexpected behavior for weight:

sage: S = SymmetricGroup(3+1)
sage: w = S.from_reduced_word([1, 3, 2])
sage: B = crystals.FullyCommutativeStableGrothendieck(w, 3, 2)
sage: h = B([[3, 1], [3], [3, 2]]); h
(3, 1)(3)(3, 2)
sage: h.weight()
(0, -1, 0) # expected (2, 1, 2)

Without seeing what your code is, I cannot comment. You can look at the ElementWrapper class and see what extra features it builds upon. However, from what you (and the code) are telling me, you do not want to wrap DecreasingHeckeFactorization but extend its functionality, which means it should subclass it. You wrap an object if you want it to behave differently than the corresponding class, but you need the data structure and/or some functionality. Right now your code is somehow in between and you might need to disentangle it a bit.

Actually, I am starting to wonder a bit why you need the separate class. If it inherits from Element(Wrapper), then it doesn't need the @richcmp_method decorator. Why do you need the DecreasingHeckeFactorization to not be a subclass of Element?

---

Some little nitpicks with style (it wouldn't stop a positive review, but it is good to follow):

-    k, D = max(w), {}
+    k = max(w)
+    D = {}

-if all(len(L[i])>=len(L[i+1]) for i in range(len(L)-1)):
+if all(len(L[i]) >= len(L[i+1]) for i in range(len(L)-1)):

-if p==r and q!=p and abs(p-q)==1:
+if p == r and q != p and abs(p-q) == 1:

-t = _apply_relations(v,position,move)
+t = _apply_relations(v, position, move)

and similar.

More micro-optimizations: For _applicable_relations, I would do:

    def _applicable_relations(word):
        """
        Return all positions where a relation can be applied on ``word``
        along with the type of relation.
        """
        L = []
        for i in range(len(word)-2):
            p, q, r = word[i:(i+2)+1]
            if abs(p-q) > 1:
                L += [[i,"pq=qp"]]
            elif abs(p-q) == 1:
                if p == r:  # p != q by the abs test
                    L += [[i,"pqp=qpq"]]
            elif r != p:  # We must have p == q
                L += [[i,"ppq=pqq"]]
            if q == r and r != p:
                L += [[i,"pqq=ppq"]]
        if abs(word[-2]-word[-1]) > 1:
           L += [[len(word)-2,"pq=qp"]]
        return L

The first is removing the unless if statements and pulling the last case outside of the loop. The second is removing redundant checks for the different relations.

I think this can be simplified:

-w[J[i]:J[i+1]][::-1]
+w[J[i+1]-1:J[i]-1:-1]

In _apply_relations(), do you need those checks? They are good for when debugging, but the first index errors will be thrown naturally by Python. The other errors checking the relations apply also feel more for debugging than a practical-use.

Your doc is not building because you need to make this change:

-Remove all bracketed letters between `i`th and `(i+1)`th entry.
+Remove all bracketed letters between `i`-th and `(i+1)`-th entry.

[sagetrac-git]

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

2eda370	Minor documentation edit
6823293	Add spaces in code
d3b135b	Minor fix
3509ec3	Let DecreasingHeckeFactorization inherit from Element

[sagetrac-git]

Changed commit from fce948d to 3509ec3

[sagetrac-wpoh]

comment:28

Thanks again for the further comments. I have pushed all the changes according to the suggestions.

Replying to @tscrim:

Actually, I am starting to wonder a bit why you need the separate class. If it inherits from Element(Wrapper), then it doesn't need the @richcmp_method decorator. Why do you need the DecreasingHeckeFactorization to not be a subclass of Element?

There are decreasing factorizations associated to non-fully commutative permutations, so I was hesitant to put it directly in the Element class of the parent class FullyCommutativeStableGrothendieck. However, writing DecreasingHeckeFactorization as a separate class and letting it inherit from Element does seem to work for our purposes, and I've added a parent class DecreasingHeckeFactorizations (with related methods) for the benefit of future explorations on non-fully commutative decreasing factorizations.

Also, I need __classcall_private__ for DecreasingHeckeFactorization to be called before the __init__ method so that the proper parent class is initialized, do let me know if using metaclass=InheritComparisonClasscallMetaclass is not appropriate.

In _apply_relations(), do you need those checks? They are good for when debugging, but the first index errors will be thrown naturally by Python. The other errors checking the relations apply also feel more for debugging than a practical-use.

You're right that they were there mainly for debugging. I've removed the error handling.

[sagetrac-git]

Changed commit from 3509ec3 to d6bfcd2

[sagetrac-git]

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

d6bfcd2

Fix documentation issues

[tscrim]

comment:30

Replying to @sagetrac-wpoh:

Thanks again for the further comments. I have pushed all the changes according to the suggestions.

Replying to @tscrim:

Actually, I am starting to wonder a bit why you need the separate class. If it inherits from Element(Wrapper), then it doesn't need the @richcmp_method decorator. Why do you need the DecreasingHeckeFactorization to not be a subclass of Element?

There are decreasing factorizations associated to non-fully commutative permutations, so I was hesitant to put it directly in the Element class of the parent class FullyCommutativeStableGrothendieck. However, writing DecreasingHeckeFactorization as a separate class and letting it inherit from Element does seem to work for our purposes, and I've added a parent class DecreasingHeckeFactorizations (with related methods) for the benefit of future explorations on non-fully commutative decreasing factorizations.

Making this into a separate Parent/Element is overkill IMO. You don't need it now and it makes the code much more complicated. What I was suggesting was simply having DecreasingHeckeFactorization be the element class for the crystal. Perhaps I was unclear about this. The crystal seems sufficient for the current purposes, and anything else you can add to the Hecke monoid elements.

Also, I need __classcall_private__ for DecreasingHeckeFactorization to be called before the __init__ method so that the proper parent class is initialized, do let me know if using metaclass=InheritComparisonClasscallMetaclass is not appropriate.

I don't see any reason why you should need this. It seems like you are fighting code that is trying to tell you to make it more simple. Have I missed something?

[anneschilling]

comment:31

Replying to @tscrim:

Replying to @sagetrac-wpoh:

Thanks again for the further comments. I have pushed all the changes according to the suggestions.

Replying to @tscrim:

Actually, I am starting to wonder a bit why you need the separate class. If it inherits from Element(Wrapper), then it doesn't need the @richcmp_method decorator. Why do you need the DecreasingHeckeFactorization to not be a subclass of Element?

There are decreasing factorizations associated to non-fully commutative permutations, so I was hesitant to put it directly in the Element class of the parent class FullyCommutativeStableGrothendieck. However, writing DecreasingHeckeFactorization as a separate class and letting it inherit from Element does seem to work for our purposes, and I've added a parent class DecreasingHeckeFactorizations (with related methods) for the benefit of future explorations on non-fully commutative decreasing factorizations.

Making this into a separate Parent/Element is overkill IMO. You don't need it now and it makes the code much more complicated. What I was suggesting was simply having DecreasingHeckeFactorization be the element class for the crystal. Perhaps I was unclear about this. The crystal seems sufficient for the current purposes, and anything else you can add to the Hecke monoid elements.

Sorry for the slow response. I could not compile Sage for a while due to Xcode12.

We need this for the insertion algorithm implemented in #30460 unless the insertion takes as input crystal elements rather than decreasing factorizations.

[tscrim]

comment:32

Replying to @anneschilling:

Replying to @tscrim:

Making this into a separate Parent/Element is overkill IMO. You don't need it now and it makes the code much more complicated. What I was suggesting was simply having DecreasingHeckeFactorization be the element class for the crystal. Perhaps I was unclear about this. The crystal seems sufficient for the current purposes, and anything else you can add to the Hecke monoid elements.

Sorry for the slow response. I could not compile Sage for a while due to Xcode12.

We need this for the insertion algorithm implemented in #30460 unless the insertion takes as input crystal elements rather than decreasing factorizations.

I don't see why the insertion could not take the crystal elements. So it still feels a little over-engineered, but it is good enough for now as the element class hierarchy doesn't have any duplication.

[tscrim]

Reviewer: Travis Scrimshaw

[anneschilling]

comment:33

Thank you for the review, Travis!

[tscrim]

comment:34

Replying to @anneschilling:

Thank you for the review, Travis!

No problem. Sorry it took a little longer for me to get to it. I will be on the lookout for when #30460 is ready.

[vbraun]

Changed branch from public/combinat/fc_stable_Grothendieck_crystal-30461 to d6bfcd2