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:  sage8.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: 
Description
Aside from the natural diagram basis for the Partition Algebra, there is an "orbit basis" which carries representationtheoretic 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
Branch:  → public/combinat/implement_orbit_basis25162 

comment:2 Changed 5 years ago by
Commit:  → 9d1b0b4c545940cc9e97b9782c9b874d804c809a 

comment:3 Changed 5 years ago by
Cc:  zabrocki added 

comment:4 Changed 5 years ago by
Commit:  9d1b0b4c545940cc9e97b9782c9b874d804c809a → 8b9dd14e93655c37a35a261fff6f5a207a76b7c4 

Branch pushed to git repo; I updated commit sha1. New commits:
8b9dd14  Implemented new "orbit basis" for partition algebras.

comment:5 Changed 5 years ago by
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.)
comment:6 Changed 5 years ago by
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
Commit:  8b9dd14e93655c37a35a261fff6f5a207a76b7c4 → 3e71dac1149f424222e4284d59b31c032e43f117 

Branch pushed to git repo; I updated commit sha1. New commits:
3e71dac  moved one_basis from DiagramAlgebra, one > id in one

comment:8 followup: 10 Changed 5 years ago by
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
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 Changed 5 years ago by
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:12 Changed 5 years ago by
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
Commit:  3e71dac1149f424222e4284d59b31c032e43f117 → f64c871195df24d7b5388ec2f515279a5edeb76b 

Branch pushed to git repo; I updated commit sha1. New commits:
aefa456  Merge branch 'public/combinat/implement_orbit_basis25162' of git://trac.sagemath.org/sage into public/combinat/implement_orbit_basis25162

3448e98  Merge branch 'public/combinat/fix_brauer_algebra_options24323' of git://trac.sagemath.org/sage into public/combinat/fix_brauer_algebra_options24323

9f484d4  Fix failing doctest.

52cf619  Merge branch 'public/combinat/fix_brauer_algebra_options24323' into public/combinat/implement_orbit_basis25162

f64c871  Refactoring and fixing bugs and various minor issues.

comment:14 Changed 5 years ago by
Authors:  Aaron Lauve, Mike Zabrocki → Aaron 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
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 (userlevel) 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 byproduct 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 followup: 17 Changed 5 years ago by
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.
comment:17 Changed 5 years ago by
Replying to alauve:
 regarding your third comment... You removed
to_orbit_basis
from parentPartitionAlgebra
but leftto_diagram_basis
within parentOrbitBasis
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 keepPartitionAlgebra
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 readsthecode (if they are looking at these things, they should already be doing that).
comment:18 followup: 22 Changed 5 years ago by
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
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
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
comment:22 Changed 5 years ago by
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
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^211*x+30)*OP{{4}, {3, 1}, {2, 4}, {1}, {2, 3}} + (x^29*x+20)*OP{{4}, {3, 1, 1}, {2, 4}, {2, 3}} + (x^29*x+20)*OP{{4}, {3, 1, 2, 3}, {2, 4}, {1}} + (x^29*x+20)*OP{{4, 1}, {3, 1}, {2, 4}, {2, 3}} + (x^27*x+12)*OP{{4, 1}, {3, 1, 2, 3}, {2, 4}} + (x^29*x+20)*OP{{4, 2, 3}, {3, 1}, {2, 4}, {1}} + (x^27*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
Commit:  f64c871195df24d7b5388ec2f515279a5edeb76b → b9197b9115cfcfd357b1c7be0843138ac1a35b7b 

Branch pushed to git repo; I updated commit sha1. New commits:
b9197b9  fix element constructor when set partition is a single part

comment:25 followup: 26 Changed 5 years ago by
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 Changed 5 years ago by
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
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
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
I have a few minutes now. Let me implement the product in the orbit basis.
comment:30 Changed 5 years ago by
Commit:  b9197b9115cfcfd357b1c7be0843138ac1a35b7b → 0d8e723156d240575aeb01fd2dfc0f7aff5ed152 

Branch pushed to git repo; I updated commit sha1. New commits:
0d8e723  began 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
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 multiplicationbycoercion 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
Commit:  0d8e723156d240575aeb01fd2dfc0f7aff5ed152 → 6bb56c5ae655e5ae58a266d99b719ac7e7ecd475 

Branch pushed to git repo; I updated commit sha1. New commits:
6bb56c5  Rewrote implementation of direct multiplication in orbit basis.

comment:33 Changed 5 years ago by
Commit:  6bb56c5ae655e5ae58a266d99b719ac7e7ecd475 → cc163202500c98a2b406b852759cf7a7f4cfadef 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
cc16320  Rewrote implementation of direct multiplication in orbit basis.

comment:34 Changed 5 years ago by
Commit:  cc163202500c98a2b406b852759cf7a7f4cfadef → 52c1fbf0970e55d5e29262a9bfdb2ed7644ca211 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
52c1fbf  Rewrote implementation of direct multiplication in orbit basis.

comment:35 Changed 5 years ago by
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) <ipythoninput75c92a56b0f000> 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/sitepackages/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
Commit:  52c1fbf0970e55d5e29262a9bfdb2ed7644ca211 → 5aac2621e4a784f0bfab5200494a599dee5cfa16 

Branch pushed to git repo; I updated commit sha1. New commits:
5aac262  1. Modified getitem to use the same conversion scheme as element_constructor.

comment:37 followup: 39 Changed 5 years ago by
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
Commit:  5aac2621e4a784f0bfab5200494a599dee5cfa16 → 937226f27f62c98983b28dd79f5586cdd61bb9d3 

Branch pushed to git repo; I updated commit sha1. New commits:
937226f  Cleaned up old code and comments

comment:39 Changed 5 years ago by
comment:40 Changed 5 years ago by
Commit:  937226f27f62c98983b28dd79f5586cdd61bb9d3 → 0aa60231cda84b9d010e2aa5a0cac430f31801ab 

Branch pushed to git repo; I updated commit sha1. New commits:
0aa6023  Merged relevant changes from 9d1b0b4 into :trac:`25162`, which were removed in commit 9d1b0b4.

comment:41 Changed 5 years ago by
Status:  new → needs_review 

comment:42 Changed 5 years ago by
Commit:  0aa60231cda84b9d010e2aa5a0cac430f31801ab → 053aac428153ded3b31927d8a568d5838c2c55f6 

Branch pushed to git repo; I updated commit sha1. New commits:
877a1b0  Merge branch 'public/cleanup_diagrams25146' of git://trac.sagemath.org/sage into public/cleanup_diagrams25146

dd77d09  Better test for AbstractPartitionDiagrams.__init__ and some cleanup.

cef9946  Merge branch 'public/cleanup_diagrams25146' into public/combinat/implement_orbit_basis25162

2850224  Getting rid of duplicate code and streamlining implementation.

f677630  Simplifying code, trivial change of iteration order.

5e84063  Better __classcall_private__ implementations.

9cc4e1b  Merge branch 'public/cleanup_diagrams25146' into public/combinat/implement_orbit_basis25162

00dea1a  Using frozenset instead of Set for the base set; renamed to _set for consistency with SetPartitions_set.

053aac4  A little more cleanup.

comment:43 Changed 5 years ago by
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
Commit:  053aac428153ded3b31927d8a568d5838c2c55f6 → 39560019209ba19d7621ed7d15dd1083cd33b5f4 

comment:45 Changed 5 years ago by
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
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
Commit:  39560019209ba19d7621ed7d15dd1083cd33b5f4 → e77512d439852257024d1130762b476c0b4c42b5 

Branch pushed to git repo; I updated commit sha1. New commits:
e77512d  change OP > O, correct failing doctest

comment:48 Changed 5 years ago by
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 followup: 51 Changed 5 years ago by
Status:  needs_review → needs_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 k1 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
Commit:  e77512d439852257024d1130762b476c0b4c42b5 → 10fa9928d830d0165cbab1740b76c21c34a7da31 

Branch pushed to git repo; I updated commit sha1. New commits:
10fa992  pyflakes edits

comment:51 Changed 5 years ago by
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 k1 together.
Yes, this.
comment:52 Changed 5 years ago by
Commit:  10fa9928d830d0165cbab1740b76c21c34a7da31 → 1ccf8229e876613b4f798f6ddbc73420ea60a50e 

Branch pushed to git repo; I updated commit sha1. New commits:
1ccf822  change to_set_partition

comment:53 followup: 54 Changed 5 years ago by
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 Changed 5 years ago by
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
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
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
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
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
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
Commit:  1ccf8229e876613b4f798f6ddbc73420ea60a50e → f0e1a3cca1a04cf74b26717a147dd7d5b89f332c 

Branch pushed to git repo; I updated commit sha1. New commits:
f0e1a3c  additions to documentation, int(k+3/2)>ceil(k+1)

comment:61 Changed 5 years ago by
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 HalversonRam (e.g. JucysMurphy 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
Commit:  f0e1a3cca1a04cf74b26717a147dd7d5b89f332c → a0cb892c909a8467bac4807e2ffc3bd576888cf8 

Branch pushed to git repo; I updated commit sha1. New commits:
a0cb892  differentiate the latex of the orbit and diagram bases

comment:63 Changed 5 years ago by
Commit:  a0cb892c909a8467bac4807e2ffc3bd576888cf8 → 1257b518cf0bec367dd5814bd24a74b1f2a01ca0 

Branch pushed to git repo; I updated commit sha1. New commits:
1257b51  doctest for diagram_basis, o>O, d>D, remove TODO

comment:64 Changed 5 years ago by
Status:  needs_work → needs_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 copypasted.
Otherwise I think this is ready to go.
comment:66 Changed 5 years ago by
Milestone:  sage8.2 → sage8.3 

comment:67 Changed 5 years ago by
Commit:  1257b518cf0bec367dd5814bd24a74b1f2a01ca0 → 80a670e01f129950fae557f928f6731d38af55c4 

Status:  positive_review → needs_review 
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
80a670e  deleted superfluous function; updated authors

comment:68 Changed 5 years ago by
Commit:  80a670e01f129950fae557f928f6731d38af55c4 → 564f36be796ad0f3fe480895f411513289904a5b 

Branch pushed to git repo; I updated commit sha1. New commits:
564f36b  added another author

comment:69 Changed 5 years ago by
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 doublechecked before setting to positive review?
comment:71 Changed 5 years ago by
Okay. If there's no objection, I shall move ticket status back to "positive review".
comment:72 Changed 5 years ago by
Status:  needs_review → positive_review 

comment:73 Changed 5 years ago by
Commit:  564f36be796ad0f3fe480895f411513289904a5b → 136244a75c6e6785e897d3ad3c2653507e2e1a71 

Status:  positive_review → needs_review 
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
e71d82a  Merge branch 'public/25146' of git://trac.sagemath.org/sage into public/25146

136244a  Merge branch 'public/combinat/implement_orbit_basis25162' of git://trac.sagemath.org/sage into public/combinat/implement_orbit_basis25162

comment:74 Changed 5 years ago by
Commit:  136244a75c6e6785e897d3ad3c2653507e2e1a71 → cb89aa3caf4d024a44dd3bb11f8d021d8d153d97 

Branch pushed to git repo; I updated commit sha1. New commits:
cb89aa3  Marking one test as long (> 2s on my laptop).

comment:75 Changed 5 years ago by
Status:  needs_review → positive_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
Status:  positive_review → needs_work 

Fails on 32bit:
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: (x6)*O{{4}, {3}, {2, 1}, {1, 4}, {2}, {3}} + (x5)*O{{4}, {3, 3}, {2, 1}, {1, 4}, {2}} + (x5)*O{{4, 3}, {3}, {2, 1}, {1, 4}, {2}} Got: (x6)*O{{4}, {3}, {2, 1}, {1, 4}, {2}, {3}} + (x5)*O{{4, 3}, {3}, {2, 1}, {1, 4}, {2}} + (x5)*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
Commit:  cb89aa3caf4d024a44dd3bb11f8d021d8d153d97 → 91996a1f507024941ec2356d45b8ec9d75263309 

comment:78 Changed 5 years ago by
Commit:  91996a1f507024941ec2356d45b8ec9d75263309 → 8481a771ba2ff3326db6ce3eae00249846bfac86 

Branch pushed to git repo; I updated commit sha1. New commits:
8481a77  Adding custom __hash__ to AbstractPartitionDiagram.

comment:79 Changed 5 years ago by
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) machinespecific outputorder 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
Status:  needs_work → needs_review 

comment:81 Changed 5 years ago by
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
Status:  needs_review → positive_review 

Yes, it is doing the comparison by the lex ordering of AbstractSetPartition
.
comment:83 Changed 5 years ago by
Branch:  public/combinat/implement_orbit_basis25162 → 8481a771ba2ff3326db6ce3eae00249846bfac86 

Resolution:  → fixed 
Status:  positive_review → closed 
Branch pushed to git repo; I updated commit sha1. New commits:
Fixing options for Brauer diagrams and algebra.
additions to the documentation to explain the compact notation
added element classes specfic to subclasses, methods to element classes, factor set partition methods
cleanup advice from Travis, added missing doctests, restored previous partition algebra iterator
doc test +1/2 iterators, move max_block_size, remove unused import statement
max takes an iterator
move (restore) is_planar as a standalone function
added diagram algebras to the list of Subsets and set partitions doc, moved is_planar
Began implementation of orbit basis for partition algebra.