Opened 5 years ago

Closed 5 years ago

#25162 closed enhancement (fixed)

Implement orbit basis for partition algebras

Reported by: alauve Owned by:
Priority: minor Milestone: sage-8.3
Component: combinatorics Keywords: IMA coding sprint, CHAs, set partitions, diagram algebras
Cc: darij, alauve, tscrim, ghseeli, s.r.doty, mantepse, zabrocki Merged in:
Authors: Aaron Lauve, Mike Zabrocki, Travis Scrimshaw Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 8481a77 (Commits, GitHub, GitLab) Commit: 8481a771ba2ff3326db6ce3eae00249846bfac86
Dependencies: #24323, #25146 Stopgaps:

Status badges

Description

Aside from the natural diagram basis for the Partition Algebra, there is an "orbit basis" which carries representation-theoretic meaning. At present, the Partition Algebra (indeed all diagram algebras) have only the diagram basis implemented. This ticket will implement the orbit basis following the model of PBWBasisOfFreeAlgebra in sage.algebras.free_algebra.

Change History (83)

comment:1 Changed 5 years ago by alauve

Branch: public/combinat/implement_orbit_basis-25162

comment:2 Changed 5 years ago by git

Commit: 9d1b0b4c545940cc9e97b9782c9b874d804c809a

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

179ce29Fixing options for Brauer diagrams and algebra.
64901e3additions to the documentation to explain the compact notation
1d651d5added element classes specfic to subclasses, methods to element classes, factor set partition methods
bcad2c4cleanup advice from Travis, added missing doctests, restored previous partition algebra iterator
737d383doc test +1/2 iterators, move max_block_size, remove unused import statement
783bca5max takes an iterator
d0c9fbdmove (restore) is_planar as a standalone function
15aa908added diagram algebras to the list of Subsets and set partitions doc, moved is_planar
9d1b0b4Began implementation of orbit basis for partition algebra.

comment:3 Changed 5 years ago by zabrocki

Cc: zabrocki added

comment:4 Changed 5 years ago by git

Commit: 9d1b0b4c545940cc9e97b9782c9b874d804c809a8b9dd14e93655c37a35a261fff6f5a207a76b7c4

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

8b9dd14Implemented new "orbit basis" for partition algebras.

comment:5 Changed 5 years ago by alauve

I should mention that I did quite a bit more than implement the orbit basis. I also worked towards implmenting coercion between different instances of SubPartitionAlgebra? classes.

e.g., one would like the following code to work, and it seems like now it does:

sage: R.<q> = QQ[]
sage: S2 = SymmetricGroupAlgebra(ZZ, 2)
sage: B2 = BrauerAlgebra(2, q, R)
sage: P = PartitionAlgebra(4, q, R)
sage: P(S2.an_element())
3*P{{-4, 4}, {-3, 3}, {-2, 1}, {-1, 2}} + P{{-4, 4}, {-3, 3}, {-2, 2}, {-1, 1}}
sage: P(B2.an_element())
3*P{{-4, 4}, {-3, 3}, {-2, -1}, {1, 2}} + 2*P{{-4, 4}, {-3, 3}, {-2, 1}, {-1, 2}} + 2*P{{-4, 4}, {-3, 3}, {-2, 2}, {-1, 1}}

However, I don't understand why coercion from the base ring doesn't work:

sage: R.<q> = QQ[]
sage: O2 = PartitionAlgebra(2, q, R).orbit_basis()
sage: P2 = PartitionAlgebra(2, q, R)
sage: O2(P2(13))
13*OP{{-2, -1, 1, 2}} + 13*OP{{-2, 2}, {-1, 1}}
sage: O2(13)  # this is wrong!!
13*OP{{-2, 2}, {-1, 1}}

(Mike should also check that multiplication in the Orbit basis performs as expected.)

Last edited 5 years ago by alauve (previous) (diff)

comment:6 Changed 5 years ago by tscrim

My guess is because DiagramAlgebra.one_basis() is defined for the orbit basis. IIRC, the conversion (technically, what you are doing is conversion) for scalars first tries to see if one_basis() is defined, and if so, then constructs an element as the term (self.one_basis(), scalar). This is done for speed reasons (it is faster than acting by multiplication). You probably need to add another ABC for the diagram algebra bases where 1 is not a basis element.

comment:7 Changed 5 years ago by git

Commit: 8b9dd14e93655c37a35a261fff6f5a207a76b7c43e71dac1149f424222e4284d59b31c032e43f117

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

3e71dacmoved one_basis from DiagramAlgebra, one -> id in one

comment:8 Changed 5 years ago by zabrocki

The problem was that one_basis was defined in DiagramAlgebra and you didn't want that method to exist in the orbit basis. I don't think it is right for unital_algebra to insist that the one of the basis is a single monomial.

comment:9 Changed 5 years ago by alauve

Great, thanks! (and I agree that unital_algebra should not assume that the unit is a single monomial.)

Will you be making other changes soon? I can tackle the doctest failures, but I think it's best to wait for zabrocki/tscrim/other to take a deeper look under the hood first.

comment:10 in reply to:  8 Changed 5 years ago by tscrim

Replying to zabrocki:

I don't think it is right for unital_algebra to insist that the one of the basis is a single monomial.

That is incorrect, unital algebras does not force you to implement one_basis. If you have implemented one_basis, then it has every right to assume 1 is a basis element. Otherwise you should just implement one().

comment:11 Changed 5 years ago by alauve

ah. that's more sensible.

comment:12 Changed 5 years ago by tscrim

I am currently doing a bunch of refactoring on this ticket (including merging in the fix on #24323).

comment:13 Changed 5 years ago by git

Commit: 3e71dac1149f424222e4284d59b31c032e43f117f64c871195df24d7b5388ec2f515279a5edeb76b

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

aefa456Merge branch 'public/combinat/implement_orbit_basis-25162' of git://trac.sagemath.org/sage into public/combinat/implement_orbit_basis-25162
3448e98Merge branch 'public/combinat/fix_brauer_algebra_options-24323' of git://trac.sagemath.org/sage into public/combinat/fix_brauer_algebra_options-24323
9f484d4Fix failing doctest.
52cf619Merge branch 'public/combinat/fix_brauer_algebra_options-24323' into public/combinat/implement_orbit_basis-25162
f64c871Refactoring and fixing bugs and various minor issues.

comment:14 Changed 5 years ago by tscrim

Authors: Aaron Lauve, Mike ZabrockiAaron Lauve, Mike Zabrocki, Travis Scrimshaw
Reviewers: Travis Scrimshaw

Okay, I have finished my refactoring and made the code as clean as I can make it. All doctests now pass and there is 100% coverage. I have also reviewed the code you wrote.

comment:15 Changed 5 years ago by tscrim

Some comments:

  • Never use a base except:; it catches far too much (including things like interrupts, or so I've been told).
  • The module_morphism is primarily expecting something that takes a basis element as input.
  • I have never really liked the (user-level) idiom of parent.to_foo(x), so I removed it. I am good with it being there to avoid reimplementation of boilerplate code, but beyond that, I think only the method at the element level should be exposed to the user.
  • I fixed the category issue of PropogatingIdeal as effectively a by-product of my refactoring.

There is likely more to be done to improve this file, but this is what is sufficient for the ticket at hand.

comment:16 Changed 5 years ago by alauve

Travis, Your changes look good to me. (Your comments are duly noted.)

  • regarding your third comment...

You removed to_orbit_basis from parent PartitionAlgebra but left to_diagram_basis within parent OrbitBasis

  • One mathematical quibble/query...

The orbit basis doesn't exist for many subalgebras of the partition algebra. Well, there could be something best known as 'orbit basis' for each subalgebra, but the formula for converting to diagram basis will not be the same as what appears around line 2339.

        PD = PartitionDiagrams(self._alg._k)
        one = self.base_ring().one()
        return self._from_dict({d: one for d in PD(diag).coarsenings()},
                               coerce=False, remove_zeros=False)

I'm not sure what's the best way to address this, but I'd be inclined to keep PartitionAlgebra in the name.

  • "Basis" versus "Algebra"...

The new name also doesn't have the word 'algebra' in it, which may be more likely to lead to confusion. Likewise, implementing DiagramBasis seems like a good idea, though I'm not sure about the name.

Last edited 5 years ago by alauve (previous) (diff)

comment:17 in reply to:  16 Changed 5 years ago by tscrim

Replying to alauve:

  • regarding your third comment... You removed to_orbit_basis from parent PartitionAlgebra but left to_diagram_basis within parent OrbitBasis

That was one of the first things I touched and a remnant of when I thought it could be necessary/useful. It can be removed.

  • One mathematical quibble/query... The orbit basis doesn't exist for many subalgebras of the partition algebra. Well, there could be something best known as 'orbit basis' for each subalgebra, but the formula for converting to diagram basis will not be the same as what appears around line 2339.
          PD = PartitionDiagrams(self._alg._k)
          one = self.base_ring().one()
          return self._from_dict({d: one for d in PD(diag).coarsenings()},
                                 coerce=False, remove_zeros=False)
    
    I'm not sure what's the best way to address this, but I'd be inclined to keep PartitionAlgebra in the name.

I don't really care since it is not anything (directly) exposed to the user. I think it is overly verbose to have it in the class name (the docstring differentiates IMO), but feel free to change it back.

(I think this file has gotten so big it is likely more manageable to be separated out into smaller pieces. In which case, sage.combinat.partition_algebra.OrbitBasis removes ambiguity, but that is a tangential.)

  • "Basis" versus "Algebra"... The new name also doesn't have the word 'algebra' in it, which may be more likely to lead to confusion. Likewise, implementing DiagramBasis seems like a good idea, though I'm not sure about the name.

These are all implemented as algebras in a particular basis. so IMO, there is no distinction between an algebra and a basis. I highly doubt this will cause any serious confusion/problems once someone reads-the-code (if they are looking at these things, they should already be doing that).

comment:18 Changed 5 years ago by zabrocki

It seems really slow. We might have to implement the multiplication directly on the orbit basis.

There seems to be something wrong here:

sage: O = PartitionAlgebra(2,x).orbit_basis()
sage: O[[1,-1],[2],[-2]]
OP{{-2}, {-1, 1}, {2}}
sage: O[[1,-1,2,-2]]
TypeError: 'sage.rings.integer.Integer' object is not iterable

comment:19 Changed 5 years ago by alauve

Hmm. I forgot about this use. This is handled in 'get item'? I may have to give up on idea of allowing user to enter a permutation as a list

Regarding speed, would it be bad practice to make coarse bonds a cached function? (Product in orbit basis is not known, right?)

comment:20 Changed 5 years ago by zabrocki

The product on the orbit basis is known. I'll have to find a reference/derivation and make sure that it is faster. We might want to cache coarsenings. It seems like if you are doing even one change of basis for a given k it will be doing repeating the same calculations.

from comment:17

I think this file has gotten so big it is likely more manageable to be separated out into smaller pieces.

+1 . Something to be done at a later date, plus improve the documentation.

comment:21 Changed 5 years ago by zabrocki

By the way, the commit from comment:2 deleted the changes from #25146

Last edited 5 years ago by zabrocki (previous) (diff)

comment:22 in reply to:  18 Changed 5 years ago by alauve

Replying to zabrocki:

There seems to be something wrong here:

sage: O = PartitionAlgebra(2,x).orbit_basis()
sage: O[[1,-1],[2],[-2]]
OP{{-2}, {-1, 1}, {2}}
sage: O[[1,-1,2,-2]]
TypeError: 'sage.rings.integer.Integer' object is not iterable

This bug is present even in development branch for PartitionAlgebra. Should perhaps be pushed to a separate ticket?

comment:23 Changed 5 years ago by zabrocki

I found a reference for the product on the orbit basis. See Lemma 4.3 in https://arxiv.org/pdf/1707.01410.pdf . I checked for example that Example 4.5 (2) agrees:

sage: P = PartitionAlgebra(4,x);O = P.orbit_basis()
sage: O[[1],[-1],[2,3],[4,-2],[-3,-4]]*O[[1],[2,-2],[3,4],[-1,-3],[-4]]
(x^2-11*x+30)*OP{{-4}, {-3, -1}, {-2, 4}, {1}, {2, 3}} + (x^2-9*x+20)*OP{{-4}, {-3, -1, 1}, {-2, 4}, {2, 3}} + (x^2-9*x+20)*OP{{-4}, {-3, -1, 2, 3}, {-2, 4}, {1}} + (x^2-9*x+20)*OP{{-4, 1}, {-3, -1}, {-2, 4}, {2, 3}} + (x^2-7*x+12)*OP{{-4, 1}, {-3, -1, 2, 3}, {-2, 4}} + (x^2-9*x+20)*OP{{-4, 2, 3}, {-3, -1}, {-2, 4}, {1}} + (x^2-7*x+12)*OP{{-4, 2, 3}, {-3, -1, 1}, {-2, 4}}
sage: %timeit O[[1],[-1],[2,3],[4,-2],[-3,-4]]*O[[1],[2,-2],[3,4],[-1,-3],[-4]]
1 loop, best of 3: 3.82 s per loop

comment:24 Changed 5 years ago by git

Commit: f64c871195df24d7b5388ec2f515279a5edeb76bb9197b9115cfcfd357b1c7be0843138ac1a35b7b

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

b9197b9fix element constructor when set partition is a single part

comment:25 Changed 5 years ago by zabrocki

That fix is quite easy so I don't think it should be a separate ticket and we should not be adding more bases and propagating this error. Let me point out a minor problem that perhaps should be on a separate ticket:

sage: P = PartitionAlgebra(4,x)
sage: P[[1,-1,2,-2]]
P{{-2, -1, 1, 2}}

I feel like we should element constructor for PartitionDiagrams(k) or check that the missing values are not there and raise an error. I think that the shorthand notation for blocks being left out is that they are all of size 1.

P{{-4}, {-3}, {-2, -1, 1, 2}, {3}, {4}}

comment:26 in reply to:  25 Changed 5 years ago by alauve

Replying to zabrocki:

Let me point out a minor problem that perhaps should be on a separate ticket:

sage: P = PartitionAlgebra(4,x)
sage: P[[1,-1,2,-2]]
P{{-2, -1, 1, 2}}

Hmm. This is the sort of thing I've tried to address with my work. See how it works with this alternate construction:

sage: P = PartitionAlgebra(4,x)
sage: P([[1,-1,2,-2]])
P{{-4, 4}, {-3, 3}, {-2, -1, 1, 2}}

sage: P([[-1,-2],[1],[2]])
P{{-4, 4}, {-3, 3}, {-2, -1}, {1}, {2}}

So... in the __getitem__ method, perhaps one could push to ._diag_to_Blst to solve the problem?

.

I feel like we should element constructor for PartitionDiagrams(k) or check that the missing values are not there and raise an error. I think that the shorthand notation for blocks being left out is that they are all of size 1.

P{{-4}, {-3}, {-2, -1, 1, 2}, {3}, {4}}

I would prefer that missing nodes come in as pairs, if possible, instead of adding singleton blocks, because this is how smaller partition algebras would embed into larger ones. I have tried to allow for singleton blocks in ._diag_to_Blst as well: i you want to add things as singletons, you can add a stray unpaired singleton. This is not documented well:

sage: P([[1,-1,2,-2]])
P{{-4, 4}, {-3, 3}, {-2, -1, 1, 2}}

sage: P([[1,-1,2,-2],[4]])
P{{-4}, {-3}, {-2, -1, 1, 2}, {3}, {4}}

sage: P([[-1,-2],[1],[2,3]])
P{{-4}, {-3}, {-2, -1}, {1}, {2, 3}, {4}}

comment:27 Changed 5 years ago by zabrocki

I'm not even sure how it is making those decisions based on your examples. I would have paired the 4 and -4 in the last one. Can you explain what it is doing?

I understand the reason for wanting to pair up for the Brauer algebra, but I don't know if that is particularly natural for the partition algebra or not. The problem arises if there are an odd number of vertices that are unpaired or if there are not the same number of positive as negative.

comment:28 Changed 5 years ago by alauve

The pairing that it tries to do is of the form (+i,-i) for all omitted nodes. If the omitted nodes cannot be so paired, then it brings in everything nodes as singletons.

(So the question about an even or odd number of omitted nodes doesn't quite enter into the story.) I note that this even works for putting P_n into P_{n+1/2} story, where one insists that (n+1) and -(n+1) always appear in the same block.

Here is the code, roughly:

        nodes = flatten(map(list, d))
        assert max(nodes) <= self._k
        if all([-i in nodes for i in nodes]):
            d = to_set_partition(d, self._k, through_strands=True)
        else:
            d = to_set_partition(d, self._k)
        return self[self._base_diagrams(d)]

Where, the optional argument 'through_strands' for the function to_set_partition brings omitted nodes in as pairs (i,-i). The default value is False.

comment:29 Changed 5 years ago by alauve

I have a few minutes now. Let me implement the product in the orbit basis.

comment:30 Changed 5 years ago by git

Commit: b9197b9115cfcfd357b1c7be0843138ac1a35b7b0d8e723156d240575aeb01fd2dfc0f7aff5ed152

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

0d8e723began implementing product in orbit basis... currently as _product_on_basis. Ran into a snag, and will not get back to it before Monday. Mike or Travis should feel free to fix it before then.

comment:31 Changed 5 years ago by tscrim

FYI - It is much faster to the partition algebra defined over, e.g., a polynomial ring rather than the symbolic ring.

When looking at the multiplication-by-coercion timings with %prun, about 1/3 of the time was spent constructing Set objects, 1/3 of the time (not necessarily disjoint) was spent in coarsenings, and at most 1/3 was spent in the other helper functions of diagram_algebras.py. However, the direct version takes almost no time. I will push momentarily a corrected version.

comment:32 Changed 5 years ago by git

Commit: 0d8e723156d240575aeb01fd2dfc0f7aff5ed1526bb56c5ae655e5ae58a266d99b719ac7e7ecd475

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

6bb56c5Rewrote implementation of direct multiplication in orbit basis.

comment:33 Changed 5 years ago by git

Commit: 6bb56c5ae655e5ae58a266d99b719ac7e7ecd475cc163202500c98a2b406b852759cf7a7f4cfadef

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

cc16320Rewrote implementation of direct multiplication in orbit basis.

comment:34 Changed 5 years ago by git

Commit: cc163202500c98a2b406b852759cf7a7f4cfadef52c1fbf0970e55d5e29262a9bfdb2ed7644ca211

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

52c1fbfRewrote implementation of direct multiplication in orbit basis.

comment:35 Changed 5 years ago by alauve

Thanks for catching my math mistake, Travis. I realized I miscoded the formula as I was walking to the train.

This wasn't the snag I hit, though. For some reason I couldn't even compose diagrams:

sage: P = PartitionAlgebra(3,x); PD = P.basis().keys()
sage: d1 = PD.random_element(); d2 = PD.random_element()
sage: d1.compose(d2)

the last line throwing some TypeError::

TypeError                                 Traceback (most recent call last)
<ipython-input-75-c92a56b0f000> in <module>()
----> 1 d1.compose(d2)

/Applications/sage/src/sage/combinat/diagram_algebras.py in compose(self, other)
    360         """
    361         (composite_diagram, loops_removed) = set_partition_composition(self._base_diagram, other._base_diagram)
--> 362         return (self.__class__(self.parent(), composite_diagram), loops_removed)
    363 
    364     def propagating_number(self):

/Applications/sage/local/lib/python2.7/site-packages/sage/misc/classcall_metaclass.pyx in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (build/cythonized/sage/misc/classcall_metaclass.c:1672)()
    331         else:
    332             # Fast version of type.__call__(cls, *args, **kwds)
--> 333             return (<PyTypeObject*>type).tp_call(cls, args, kwds)
    334 
    335     def __get__(cls, instance, owner):

/Applications/sage/src/sage/combinat/diagram_algebras.py in __init__(self, parent, d)
    240         """
    241         self._base_diagram = tuple(sorted(tuple(sorted(i)) for i in d))
--> 242         super(AbstractPartitionDiagram, self).__init__(parent, self._base_diagram)
    243 
    244     def check(self):

TypeError: super(type, obj): obj must be an instance or subtype of type

It seems to work now, so I don't know what classes I accidentally made d1 and d2. I'll play around a bit more to see if I can reproduce the error.

comment:36 Changed 5 years ago by git

Commit: 52c1fbf0970e55d5e29262a9bfdb2ed7644ca2115aac2621e4a784f0bfab5200494a599dee5cfa16

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

5aac2621. Modified getitem to use the same conversion scheme as element_constructor.

comment:37 Changed 5 years ago by zabrocki

What do we do about #25146 ? This branch is (partially) merged, but Aaron deleted those changes in 9d1b0b4

comment:38 Changed 5 years ago by git

Commit: 5aac2621e4a784f0bfab5200494a599dee5cfa16937226f27f62c98983b28dd79f5586cdd61bb9d3

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

937226fCleaned up old code and comments

comment:39 in reply to:  37 Changed 5 years ago by alauve

Replying to zabrocki:

What do we do about #25146 ? This branch is (partially) merged, but Aaron deleted those changes in 9d1b0b4

Well, since I caused the problem, I guess I should try to solve it. Will take a look now to see how easy are they to merge "by hand".

comment:40 Changed 5 years ago by git

Commit: 937226f27f62c98983b28dd79f5586cdd61bb9d30aa60231cda84b9d010e2aa5a0cac430f31801ab

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

0aa6023Merged relevant changes from 9d1b0b4 into :trac:`25162`, which were removed in commit 9d1b0b4.

comment:41 Changed 5 years ago by alauve

Status: newneeds_review

comment:42 Changed 5 years ago by git

Commit: 0aa60231cda84b9d010e2aa5a0cac430f31801ab053aac428153ded3b31927d8a568d5838c2c55f6

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

877a1b0Merge branch 'public/cleanup_diagrams-25146' of git://trac.sagemath.org/sage into public/cleanup_diagrams-25146
dd77d09Better test for AbstractPartitionDiagrams.__init__ and some cleanup.
cef9946Merge branch 'public/cleanup_diagrams-25146' into public/combinat/implement_orbit_basis-25162
2850224Getting rid of duplicate code and streamlining implementation.
f677630Simplifying code, trivial change of iteration order.
5e84063Better __classcall_private__ implementations.
9cc4e1bMerge branch 'public/cleanup_diagrams-25146' into public/combinat/implement_orbit_basis-25162
00dea1aUsing frozenset instead of Set for the base set; renamed to _set for consistency with SetPartitions_set.
053aac4A little more cleanup.

comment:43 Changed 5 years ago by tscrim

Here is an updated branch with my changes from #25146, as well as fixing what should be the only docstring issue, bring to full doctest coverage, and some misc fixes.

comment:44 Changed 5 years ago by git

Commit: 053aac428153ded3b31927d8a568d5838c2c55f639560019209ba19d7621ed7d15dd1083cd33b5f4

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

51b1a3aorbit basis more appropriate than Orbit basis in doc
3956001add documentation for the definition of the orbit basis

comment:45 Changed 5 years ago by zabrocki

I want to question the use of O+prefix for the orbit basis and propose that it be switched just to O or o. Is the double letter really necessary here? The expressions are already extremely long because the default display of set partitions has so many braces. I would prefer to have the default prefix be more compact. I computed an example the other day and I thought the OP prefix was heavy notation (but hey, the code worked as promised and has been very helpful!).

I also found it was misleading when I was looking at the to_orbit_basis in the SubPartitionAlgebra because then it generated a basis indexed by OB and I thought that this poorly indicated that this was not the orbit basis of the Brauer algebra, but instead the orbit basis of the partition algebra (I actually also find this strange behavior for ambient and lift but these are not new to this ticket).

Either way, I would just as soon have the display prefix for the basis be simply O. Are there objections to me changing it?

comment:46 Changed 5 years ago by alauve

O is fine by me.

Yes, the lift functionality is strange. I don't think it should keep the same letter as prefix, after lift, as it had before. But I decided not to mess with it. We could perhaps remove this method, but I thought there could be some use for it. Shall I work on improving the surrounding documentation?

comment:47 Changed 5 years ago by git

Commit: 39560019209ba19d7621ed7d15dd1083cd33b5f4e77512d439852257024d1130762b476c0b4c42b5

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

e77512dchange OP -> O, correct failing doctest

comment:48 Changed 5 years ago by chapoton

pyflakes says

src/sage/combinat/diagram_algebras.py:28: 'sage.categories.algebras.Algebras' imported but unused
src/sage/combinat/diagram_algebras.py:2801: local variable 'k' is assigned to but never used

comment:49 Changed 5 years ago by zabrocki

Status: needs_reviewneeds_work

I think that things left to do here are mostly improvements in the documentation and this embedding thing we started discussing in comment:25 . Before I make any changes I just want to review what should be the right thing to do. I think that P_k -> P_{k+1/2} -> P_{k+1} should be the same as P_{k} -> P_{k+1}. In which case it is appropriate (as you say) to connect k+1 and -k-1 together.

sage: P3 = PartitionAlgebra(3,x,prefix='P3'); P4 = PartitionAlgebra(4,x,prefix='P4')
sage: P2(P[[1,-2,2,-1]])
P4{{-4, 4}, {-3, 3}, {-2, -1, 1, 2}}

but

sage: P3 = PartitionAlgebra(3,x); Px = PartitionAlgebra(7/2,x,prefix='P3.5')
sage: Px(P3[[1,-2,2,-1]])
ValueError: {{-3, 3}, {-2, -1, 1, 2}} does not represent two rows of vertices of order 7/2
sage: Px(P4[[1,-2,2,-1]])
P3.5{{-4, 4}, {-3, 3}, {-2, -1, 1, 2}}

so I think that there is something wrong (probably minor).

comment:50 Changed 5 years ago by git

Commit: e77512d439852257024d1130762b476c0b4c42b510fa9928d830d0165cbab1740b76c21c34a7da31

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

10fa992pyflakes edits

comment:51 in reply to:  49 Changed 5 years ago by alauve

Replying to zabrocki:

I think that things left to do here are mostly improvements in the documentation and this embedding thing we started discussing in comment:25 . Before I make any changes I just want to review what should be the right thing to do. I think that P_k -> P_{k+1/2} -> P_{k+1} should be the same as P_{k} -> P_{k+1}. In which case it is appropriate (as you say) to connect k+1 and -k-1 together.

Yes, this.

comment:52 Changed 5 years ago by git

Commit: 10fa9928d830d0165cbab1740b76c21c34a7da311ccf8229e876613b4f798f6ddbc73420ea60a50e

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

1ccf822change to_set_partition

comment:53 Changed 5 years ago by zabrocki

See if you agree with this behavior. I didn't understand what it was doing before. There was a test pairing_is_possible which didn't always seem like the right thing to do. Before:

sage: P = PartitionAlgebra(3,x)
sage: P[[1]]
P{{-3}, {-2}, {-1}, {1}, {2}, {3}}

but I just made it pair the missing {i,-i} strands if it can. Now:

sage: P = PartitionAlgebra(3,x)
sage: P[[1]]
P{{-3, 3}, {-2, 2}, {-1}, {1}}

comment:54 in reply to:  53 Changed 5 years ago by alauve

Replying to zabrocki:

See if you agree with this behavior. I didn't understand what it was doing before. There was a test pairing_is_possible which didn't always seem like the right thing to do. Before:

sage: P = PartitionAlgebra(3,x)
sage: P[[1]]
P{{-3}, {-2}, {-1}, {1}, {2}, {3}}

but I just made it pair the missing {i,-i} strands if it can. Now:

sage: P = PartitionAlgebra(3,x)
sage: P[[1]]
P{{-3, 3}, {-2, 2}, {-1}, {1}}

My idea was to preserve the ability to bring things in with singletons. Try

P[[1],[-1]]

comment:55 Changed 5 years ago by zabrocki

My idea was to preserve the ability to bring things in with singletons. Try

P[[1],[-1]]

I did

sage: P = PartitionAlgebra(3,x)
sage: P[[1],[-1]]
P{{-3, 3}, {-2, 2}, {-1}, {1}}

This is what I expected. Is that not what you thought? Maybe I don't understand "bring things in with singletons."

comment:56 Changed 5 years ago by alauve

It is different from

P[[1]]

which is the one that brings things in as singletons. The idea was if your excluded nodes don't pair up, then bring the rest in as singletons. If you want the excluded nodes to come in as pairs (through strands), then exclude them in pairs.

comment:57 Changed 5 years ago by zabrocki

This is what I see now (and this is what I think should be):

sage: P[[1]]==P[[1],[-1]]
True

The idea was if your excluded nodes don't pair up, then bring the rest in as singletons. If you want the excluded nodes to come in as pairs (through strands), then exclude them in pairs.

The problem to me is that is not well documented and it is complex. I think it should follow a simple and consistent rule : "pair {i,-i} if they are not listed. Do this as much as possible and then fill in singletons."

What it was doing before was raising an error when I computed P[[1]] for P=PartitionAlgebra(5/2,x).

comment:58 Changed 5 years ago by alauve

That's fine with me. I was trying to preserve behavior as I found it as best as possible. But improving the documentation will not improve the situation much. It is complex.

comment:59 Changed 5 years ago by tscrim

Note that 3/2 == 1 in Python2 (with from __future__ import division/Python3, it becomes a floating point). IMO, if you really want to add 3/2, do it using QQ and then take the corresponding floor. Although a better approach to add 1 and then take ceil.

Also, if you want to change the "default" output, you can add the global options change to your ~/.sage/sage.init (or wherever your .sage directory is). Commands in this file are run on startup. Although for this to work, we would need a ticket to add a global option to SetPartition or to PartitionAlgebra.

comment:60 Changed 5 years ago by git

Commit: 1ccf8229e876613b4f798f6ddbc73420ea60a50ef0e1a3cca1a04cf74b26717a147dd7d5b89f332c

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

f0e1a3cadditions to documentation, int(k+3/2)->ceil(k+1)

comment:61 Changed 5 years ago by zabrocki

I agree that a global options is in order for SetPartition and PartitionAlgebra. A compact notation would be a nice feature. I think that there is a lot of work to do to implement the some results of Halverson-Ram (e.g. Jucys-Murphy elements, class type of a diagram, various flavors of generators, etc.). Plus reorganizing some of the code because the file has become quite huge. These are all items for followup tickets.

One of the nice features of the diagram algebra code is the latex of an expression. [BH2017] differentiates the latex of the diagram basis from the orbit basis by filled nodes so I added this for the latex of the orbit basis (although it switches BH convention in that orbit basis has filled nodes and diagram basis has not filled nodes).

Although a better approach to add 1 and then take ceil.

I went with this approach (in fact, I had it before).

comment:62 Changed 5 years ago by git

Commit: f0e1a3cca1a04cf74b26717a147dd7d5b89f332ca0cb892c909a8467bac4807e2ffc3bd576888cf8

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

a0cb892differentiate the latex of the orbit and diagram bases

comment:63 Changed 5 years ago by git

Commit: a0cb892c909a8467bac4807e2ffc3bd576888cf81257b518cf0bec367dd5814bd24a74b1f2a01ca0

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

1257b51doctest for diagram_basis, o->O, d->D, remove TODO

comment:64 Changed 5 years ago by zabrocki

Status: needs_workneeds_review

I deleted the "TODO: find a better name?". elementary_symmetric is a fine name and I would not recommend deprecating it now if there was one (and one can always add an alias if a better name comes along).

I added a doctest for diagram_algebra because the ones that were there I think must have been copy-pasted.

Otherwise I think this is ready to go.

comment:65 Changed 5 years ago by tscrim

Status: needs_reviewpositive_review

I agree. Thank you.

comment:66 Changed 5 years ago by tscrim

Milestone: sage-8.2sage-8.3

comment:67 Changed 5 years ago by git

Commit: 1257b518cf0bec367dd5814bd24a74b1f2a01ca080a670e01f129950fae557f928f6731d38af55c4
Status: positive_reviewneeds_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

80a670edeleted superfluous function; updated authors

comment:68 Changed 5 years ago by git

Commit: 80a670e01f129950fae557f928f6731d38af55c4564f36be796ad0f3fe480895f411513289904a5b

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

564f36badded another author

comment:69 Changed 5 years ago by alauve

Travis,

  • The function I deleted was one I added in an earlier revision within this branch. After Mike's changes, it's no longer needed. So I deleted it.
  • Not quite sure if the work I did is worthy of mention. Please feel free to yank the new line in the header.
  • It looks like all the changes from #25146 have been mixed in here. That ticket seems stable now. There are some differences, of course, but nothing that should affect a merge. Should this be double-checked before setting to positive review?
Last edited 5 years ago by alauve (previous) (diff)

comment:70 Changed 5 years ago by tscrim

All of the changes from #25146 have been merged in here.

comment:71 Changed 5 years ago by alauve

Okay. If there's no objection, I shall move ticket status back to "positive review".

comment:72 Changed 5 years ago by alauve

Status: needs_reviewpositive_review

comment:73 Changed 5 years ago by git

Commit: 564f36be796ad0f3fe480895f411513289904a5b136244a75c6e6785e897d3ad3c2653507e2e1a71
Status: positive_reviewneeds_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

e71d82aMerge branch 'public/25146' of git://trac.sagemath.org/sage into public/25146
136244aMerge branch 'public/combinat/implement_orbit_basis-25162' of git://trac.sagemath.org/sage into public/combinat/implement_orbit_basis-25162

comment:74 Changed 5 years ago by git

Commit: 136244a75c6e6785e897d3ad3c2653507e2e1a71cb89aa3caf4d024a44dd3bb11f8d021d8d153d97

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

cb89aa3Marking one test as long (> 2s on my laptop).

comment:75 Changed 5 years ago by tscrim

Status: needs_reviewpositive_review

Trivial rebase and marked one test as long. I'm allowing myself to set it back to a positive review.

comment:76 Changed 5 years ago by vbraun

Status: positive_reviewneeds_work

Fails on 32-bit:

File "src/sage/combinat/diagram_algebras.py", line 2228, in sage.combinat.diagram_algebras.PartitionAlgebra._element_constructor_
Failed example:
    A(S.an_element())
Expected:
    P{{-3, 3}, {-2, 2}, {-1, 1}} + P{{-3, 1}, {-2, 3}, {-1, 2}} + 3*P{{-3, 3}, {-2, 1}, {-1, 2}}
     + 2*P{{-3, 2}, {-2, 3}, {-1, 1}}
Got:
    P{{-3, 1}, {-2, 3}, {-1, 2}} + 3*P{{-3, 3}, {-2, 1}, {-1, 2}} + P{{-3, 3}, {-2, 2}, {-1, 1}} + 2*P{{-3, 2}, {-2, 3}, {-1, 1}}
**********************************************************************
File "src/sage/combinat/diagram_algebras.py", line 2234, in sage.combinat.diagram_algebras.PartitionAlgebra._element_constructor_
Failed example:
    A(B.an_element())
Expected:
    2*P{{-3, 1}, {-2, 2}, {-1, 3}} + 2*P{{-3, 1}, {-2, 3}, {-1, 2}}
     + 3*P{{-3, 1}, {-2, -1}, {2, 3}}
Got:
    2*P{{-3, 1}, {-2, 3}, {-1, 2}} + 2*P{{-3, 1}, {-2, 2}, {-1, 3}} + 3*P{{-3, 1}, {-2, -1}, {2, 3}}
**********************************************************************
File "src/sage/combinat/diagram_algebras.py", line 2371, in sage.combinat.diagram_algebras.PartitionAlgebra._coerce_map_from_
Failed example:
    A._coerce_map_from_(O3)(elt)
Expected:
    3*P{{-4, 4}, {-3, -2, -1, 1, 3}, {2}} - 3*P{{-4, 4}, {-3, -2, -1, 1, 2, 3}}
     + 2*P{{-4, 4}, {-3, -2, -1, 2, 3}, {1}}
Got:
    -3*P{{-4, 4}, {-3, -2, -1, 1, 2, 3}} + 2*P{{-4, 4}, {-3, -2, -1, 2, 3}, {1}} + 3*P{{-4, 4}, {-3, -2, -1, 1, 3}, {2}}
**********************************************************************
File "src/sage/combinat/diagram_algebras.py", line 2776, in sage.combinat.diagram_algebras.OrbitBasis.product_on_basis
Failed example:
    O[[1,-1],[2,-2],[3],[4,-3],[-4]] * O[[1,-2],[2],[3,-1],[4],[-3],[-4]]
Expected:
    (x-6)*O{{-4}, {-3}, {-2, 1}, {-1, 4}, {2}, {3}}
     + (x-5)*O{{-4}, {-3, 3}, {-2, 1}, {-1, 4}, {2}}
     + (x-5)*O{{-4, 3}, {-3}, {-2, 1}, {-1, 4}, {2}}
Got:
    (x-6)*O{{-4}, {-3}, {-2, 1}, {-1, 4}, {2}, {3}} + (x-5)*O{{-4, 3}, {-3}, {-2, 1}, {-1, 4}, {2}} + (x-5)*O{{-4}, {-3, 3}, {-2, 1}, {-1, 4}, {2}}
**********************************************************************
3 items had failures:
   1 of  29 in sage.combinat.diagram_algebras.OrbitBasis.product_on_basis
   1 of  17 in sage.combinat.diagram_algebras.PartitionAlgebra._coerce_map_from_
   2 of  39 in sage.combinat.diagram_algebras.PartitionAlgebra._element_constructor_
    [781 tests, 4 failures, 19.54 s]
----------------------------------------------------------------------
sage -t --long src/sage/combinat/diagram_algebras.py  # 4 doctests failed
----------------------------------------------------------------------

comment:77 Changed 5 years ago by git

Commit: cb89aa3caf4d024a44dd3bb11f8d021d8d153d9791996a1f507024941ec2356d45b8ec9d75263309

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

fbab6bbMerge branch 'public/combinat/implement_orbit_basis-25162' of git://trac.sagemath.org/sage into public/combinat/implement_orbit_basis-25162
91996a1Diagrams now do checks with __lt__.

comment:78 Changed 5 years ago by git

Commit: 91996a1f507024941ec2356d45b8ec9d752633098481a771ba2ff3326db6ce3eae00249846bfac86

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

8481a77Adding custom __hash__ to AbstractPartitionDiagram.

comment:79 Changed 5 years ago by tscrim

So it turns out AFAIK that no < comparison was returning True for the diagrams. This was because the abstract __lt__ check was checking the subclass SetPartition rather than AbstractSetPartition. However, I implemented a custom __lt__ to take advantage of the _base_diagram. To be honest, I am surprised we were not seeing (more) machine-specific output-order doctest failures.

I also implemented a custom hash to use _base_diagram for better speed and better compatibility with ==.

comment:80 Changed 5 years ago by tscrim

Status: needs_workneeds_review

comment:81 Changed 5 years ago by zabrocki

All tests pass on my machine, but so did the previous version. If you are confident that it fixes the problem, I'll say positive review.

comment:82 Changed 5 years ago by tscrim

Status: needs_reviewpositive_review

Yes, it is doing the comparison by the lex ordering of AbstractSetPartition.

comment:83 Changed 5 years ago by vbraun

Branch: public/combinat/implement_orbit_basis-251628481a771ba2ff3326db6ce3eae00249846bfac86
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.